> #include <stdio.h>
> #include <memory.h>
> #define true  1
> #define false 0
> #define I  0
> #define N  100
> 
> double cost[N][N];
> double dist[N],max;
> int v0,v1;
> 
> void main()
> {
> 	int final[N],i,v,w,n,m;
> 	while(1)
> 	{
> 		scanf("%d",&n);
> 		if(n==0)break;
> 		scanf("%d",&m);
> 		v0=0;v1=n-1;
> 		memset(cost,0,sizeof(double)*n*n);
> 		for(i=0;i<m;i++)
> 		{
> 			int x,y,rate;
> 			scanf("%d%d%d",&x,&y,&rate);
> 			x--;y--;
> 			if(cost[x][y]!=0)
> 				if(rate<cost[x][y]*100)continue;
> 			cost[x][y]=(double)rate/100;
> 			cost[y][x]=(double)rate/100;
> 		}
> 		for(v=0;v<n;v++)
> 		{
> 			final[v]=false;
> 			dist[v]=cost[v0][v];
> 		}
> 		final[v0] = true;
> 
> 		while(1)
> 		{
> 			max=0;
> 			for(w=0;w<n;w++)
> 			{
> 				if(!final[w]&&dist[w]>max)
> 				{
> 					max=dist[w];
> 					v=w;
> 				}
> 			}
> 			final[v]=true;
> 			if(final[v1]==true)break;
> 			for(w=0;w<n;w++)
> 			{
> 				if(!final[w]&&dist[v]*cost[v][w]>dist[w])
> 				{
> 					dist[w]=dist[v]*cost[v][w];
> 				}
> 			}
> 		}
> 		printf("%.6lf percent\n",dist[v1]*100);
> 	}
> 
> }

• Re:这题难道不是DIJ? (6) fmlwlh 2006-07-29 16:45:27
  • Floyd???Dijkstra吧.... (10) qywyh_scut 2006-08-22 20:17:26
• Re:这题难道不是DIJ? (17) Eli_love 2009-11-22 00:48:18