poj 1135 Domino Effect（最短路+枚舉）

經過無數的WA和PE終於AC。。

最短路的模板。

1)dis[i]表示i到源點1的最短路徑，代表每一張關鍵牌倒下的時間，並求出最大的最短路徑ans1。

2)枚舉任意兩邊，計算每一行倒下的時間，設每一行兩端的關鍵牌是i，j。那麼這一行完全倒下時間是(dis[i]+dis[j]+map[i][j])/2.0，並求出最大值ans2.

3)比較ans1與ans2，取較大者。

#include 
#include 
#include 
#define LL long long
#define _LL __int64

using namespace std;
const int maxn = 510;
const int INF = 0x3f3f3f3f;
int n,m;
int map[maxn][maxn];
int dis[maxn],vis[maxn],maxdis,maxpos;

void dijstra()
{
	memset(dis,INF,sizeof(dis));
	memset(vis,0,sizeof(vis));
	maxdis = -INF;
	vis[1] = 1;
	for(int i = 1; i <= n; i++)
		dis[i] = map[1][i];

	for(int i = 1; i < n; i++)
	{
		int min = INF,pos = 1;
		for(int j = 1; j <= n; j++)
		{
			if(!vis[j] && dis[j] < min)
			{
				min = dis[j];
				pos = j;
			}
		}
		if(min == INF) break;
		vis[pos] = 1;
		if(maxdis < min)
		{
			maxdis = min;
			maxpos = pos;
		}

		for(int j = 1; j <= n; j++)
		{
			if(!vis[j] && dis[j] > dis[pos] + map[pos][j])
				dis[j] = dis[pos] + map[pos][j];
		}
	}
}

void solve()
{
	int pl = -1,pr = -1;
	double ans2 = (double)maxdis;
	double ans1 = -INF;

    for(int i = 1; i <= n; i++)
    {
        for(int j = i+1; j <= n; j++)
        {
            if(map[i][j] != INF)
            {
                double res = ( dis[i]+dis[j] + map[i][j])/2.0;
                if(res > ans1)
                {
                    ans1 = res;
                    pl = i;
                    pr = j;
                }
            }
        }
    }

    if(ans1 > ans2)
        printf(The last domino falls after %.1f seconds, between key dominoes %d and %d.
,ans1,pl,pr);
    else printf(The last domino falls after %.1f seconds, at key domino %d.
,ans2,maxpos);
}

int main()
{
	int item = 1;
	while(~scanf(%d %d,&n,&m) && (n || m))
	{
		for(int i = 1; i <= n; i++)
		{
			for(int j = 1; j <= n; j++)
			{
				if(i == j) map[i][j] = 0;
				else map[i][j] = INF;
			}
		}
		int u,v,w;

		for(int i = 1; i <= m; i++)
		{
			scanf(%d %d %d,&u,&v,&w);
			map[u][v] = map[v][u] = w;
		}
		printf(System #%d
,item++);

		if(n == 1)
		{
			printf(The last domino falls after 0.0 seconds, at key domino 1.

);
			continue;
		}
		dijstra();
		solve();
		printf(
);
	}
	return 0;
}