#include <stdio.h>
int path[512][512];
int maxnum = 9999999;
int d[512], flag[512];
int main()
{
	int n, m, i, j, temp, a, b, dis, w, min, k;
	int target1, target2, num = 1, max1, max2;
	double h, sum;
	while(scanf("%d %d", &n, &m) == 2)
	{
		if(n == 0 && m == 0)break;
		for(i = 0; i <= n; i++)
		{
			for(j = 0; j <= n; j++)
				path[i][j] = maxnum;
			d[i] = maxnum;
			flag[i] = 0;
		}
		for(i = 0; i < m; i++)
		{
			scanf("%d %d %d", &a, &b, &dis);
			path[a][b] = dis;
			path[b][a] = dis;
		}
		d[1] = 0;
		for(i = 1, w = 0; i <= n; i++)
		{
			temp = maxnum;
			for(j = 1; j <= n; j++)
			if(!flag[j] && d[j] < maxnum)
			{
				temp = d[j];
				min = j;
				break;
			}
			if(temp == maxnum)break;
			for(j = 1; j <= n; j++)
			{
				flag[min] = 1;
				if(!flag[j] && path[min][j] + d[min] < d[j])
				{
					d[j] = d[min] + path[min][j];
				}
				if(d[j] != maxnum)
				{
					if(w < d[j])
					w = d[j];
				}
			}
		}
		for(i = 2, sum = 0, k = 0, target1 = 1; i <= n; i++)
		{
			if(d[i] != maxnum)
			{
				for(j = 1; j <= n; j++)
				{
					if(path[i][j] != maxnum)
					{
						max1 = d[i] > d[j] ? d[i] : d[j];
						max2 = d[i] < d[j] ? d[i] : d[j];
						if(max2 + path[i][j] > max1)
						{
							h = max1 - max2;
							h = (path[i][j] - h)*0.5;
							h = h + max1;
							if(sum < h)
							{
							sum = h;
							k = 1;
							target1 = i < j ? i : j;
							target2 = i > j ? i : j;
							}
						}
						else if(max2 + path[i][j] == max1)
						{
							if(sum < d[i])
							{
								k = 0;
								sum = max1;
								target1 = i;
							}
						}
					}
				}
			}
		}
		if(num != 1)putchar('\n');
		if(k == 0)printf("System #%d\nThe last domino falls after %.1lf seconds, at key domino %d.\n", num++, sum, target1);
		else printf("System #%d\nThe last domino falls after %.1lf seconds, between key dominoes %d and %d.\n", num++, sum, target1, target2);
	}
}

• Re:Dijkstra+枚举....有错么..代码附上，先谢谢了~ (38) czcomt 2008-11-27 19:38:25