> #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啊! (0) AKnight 2012-09-28 16:47:31
• Re:求测试数据,能测的都过了，但还是不能ac啊! (157) AKnight 2012-09-28 16:54:22