#include"iostream"
using namespace std;
#define N 501
#define MAX 999999
float map[N][N],d[N];
int n;
void di(int v)
{
	  int i,j,u;
		  float temp=MAX;
		bool used[N]={false};
    for(i=1;i<=n;i++)
		d[i]=map[v][i];
	used[v]=true;
	for(i=1;i<n;i++)
	{
		u=v;temp=MAX;
		for(j=1;j<=n;j++)
		{
			if(!used[j]&&temp>d[j])
			{
				temp=d[j];
				u=j;
			}
		}
		used[u]=true;
		for(j=1;j<=n;j++)
		{
			if(!used[j]&&d[u]+map[u][j]<d[j])
				d[j]=d[u]+map[u][j];
		}
	}
}
int main()
{
   int i,j,m,a,b,t,s=1,rem1[N],t1,x;
   float rem[N],bestmax=0.0,l,max=0.0;
    while(scanf("%d%d",&n,&m))
	{   
		if(m==0&&n==0)
			break;
		if(n==1) 
		{ 
			printf("System #%d\nThe last domino falls after 0.0 seconds, at key domino 1.\n\n",s);
			s++;
			continue;
		}
		bestmax=0.0;
	     max=0.0;
	   for(i=1;i<=n;i++)
	   {  rem[i]=0.0;
		   for(j=1;j<=n;j++)
			   map[i][j]=max;
	   }
	   for(i=1;i<=m;i++)
	   {
		   scanf("%d%d%f",&a,&b,&l);
           map[a][b]=map[b][a]=l;
	   }
	   for(i=1;i<=n;i++)
		   map[i][i]=0;
	   di(1);
	   for(i=2;i<=n;i++)
		   if(max<d[i])
		   {
			   max=d[i];
			   t=i;
		   }
	   for(i=1,j=1;i<=n;i++)
	   {
		   if(map[t][i]!=MAX)
		   {
			   rem[j]=(float)(max+d[i]+map[t][i])/2;
			   rem1[j]=i;
			   j++;
		   }
	   }
	   for(i=1;i<j;i++)
	   {
		   if(bestmax<=rem[i])
		   {
			   bestmax=rem[i];
		       t1=rem1[i];
		   }
	   }
	   if(t>t1)
	   {
		   x=t1;
		   t1=t;
		   t=x;
	   }
	   if(max==bestmax)
	   {
		   printf("System #%d\nThe last domino falls after %.1f seconds, at key domino %d.\n",s,bestmax,t);
		   printf("\n");
	   }

	   if(bestmax!=max)
	   {
		   printf("System #%d\nThe last domino falls after %.1f seconds, between key dominoes %d and %d.\n",s,bestmax,t,t1);
		   printf("\n");
	   }
	   s++;
	}
	return 0;
}

• Re:求测试数据,能测的都过了，但还是不能ac啊! (26) luctionli 2010-08-06 20:35:38
• Re:求测试数据,能测的都过了，但还是不能ac啊! (2095) heting 2010-08-09 21:36:45
  • Re:求测试数据,能测的都过了，但还是不能ac啊! (0) AKnight 2012-09-28 16:47:31
  • Re:求测试数据,能测的都过了，但还是不能ac啊! (157) AKnight 2012-09-28 16:54:22