#include<iostream>
#include<math.h>
#include<stdlib.h>
using namespace std;
int n,m;
const int N=505;
const int M=0x3fffffff;
int mat[N][N];
int d[N];
bool visit[N];
void dijk()
{
	for(int i=1;i<=n;i++)
		d[i]=M;
	memset(visit,0,sizeof(visit));
	d[1]=0;
	visit[1]=true;
	for(int i=1;i<=n-1;i++)
	{
		int next=0;
		int min=0x7fffffff;
		for(int j=1;j<=n;j++)
		{
			if(visit[j])
			{
				for(int k=1;k<=n;k++)
				{
  					
   					if(k!=j&&!visit[k]&&mat[j][k]>0)
					{
						if(d[k]>d[j]+mat[j][k])
							d[k]=d[j]+mat[j][k];
						if(d[k]<min)
						{
							min=d[k];
							next=k;
						}
					}
				}
			}
		}
		visit[next]=true;
	}
	//以上是dijkstra处理。
	//下面是枚举
	double ans=0;
	int pos=0,posa=0,posb=0;
	for(int i=1;i<=n;i++)
	{
		if(d[i]>=ans)
			ans=d[i],pos=i;
	}
	bool flag=false;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(mat[i][j]!=0&&d[j]>=d[i])
			{
				if(d[j]<d[i]+mat[i][j])
				{
					double tmp=((double(mat[i][j]-(d[j]-d[i])))/2.0+d[j]);
					if(tmp>ans)
					{
						ans=tmp;
						if(i<j)
							posa=i,posb=j;
						else
							posa=j,posb=i;
						flag=true;
					}
				}
			}
	if(!flag)
		printf("The last domino falls after %.1f seconds, at key domino %d.\n",ans,pos);
	else
		printf("The last domino falls after %.1f seconds, between key dominoes %d and %d.\n",ans,posa,posb);
}
int main()
{
	
	int cases=0;
	while(scanf("%d%d",&n,&m),n!=0||m!=0)
	{
		for(int i=1;i<=m;i++)
		{
			int a=0,b=0;
			scanf("%d%d",&a,&b);
			scanf("%d",&mat[a][b]);
			mat[b][a]=mat[a][b];
		}
		printf("System #%d\n",++cases);
		dijk();
		printf("\n");
	} 
	return 0;
}

• Re:吐血了都，测试数据都过了为什么还是wa啊，求神人相救。 (47) 64162451 2011-08-02 02:14:13
  • Re:吐血了都，测试数据都过了为什么还是wa啊，求神人相救。 (51) 1004131114 2015-09-02 15:08:02
    • Re:吐血了都，测试数据都过了为什么还是wa啊，求神人相救。 (6) 1004131114 2015-09-02 15:08:26