#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);
	}

}

• 这题难道不是DIJ? (1144) Essence_me 2005-09-07 01:04:37
  • 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