/*我的WA代码：结点从1开始计，maxn为最大结点数,
n为结点数，manint是无穷大, c[i][j] i到j的权，pre[]记录父结点,dist[i]源点到i的最短路径，s[]表示左边的集合*/
#include <iostream>
#include <stdio.h>
using namespace std;

const int maxn = 102;
int manint = 99999999;
double c[maxn][maxn],dist[maxn];
int prev[maxn],n;
double ans;
void dijkstra(int v)//原点是v 
{
		bool s[maxn];  register int i,j;
		
		for(i=1;i<=n;i++)
		{
			dist[i] = c[v][i];
			s[i] = 0;
			if(dist[i]==manint)//v to i没有边
				prev[i] = 0;
			else
				prev[i] = v; 
		}
		s[v] = 1; dist[v] = 0;
		for(i=1;i<n;i++)
		{
			double temp = manint;
			int u = v;
			for(j=1;j<=n;j++)
				if(!s[j]&&dist[j]>=0&&dist[j]<temp)
				{
					u = j;
					temp = dist[j];
				}
			s[u] = 1;
			for(j=1;j<=n;j++)
				if(!s[j]&&c[u][j]<manint)
				{
					double newdist = dist[u] + c[u][j];
					if(newdist < dist[j])
					{
						dist[j] = newdist;
						prev[j] = u;
					}
				}
		}
}

int main()
{
	register int i,j;
	int edges;
	int a,b;
	double percent;
	while(cin>>n&&n)
	{
		for(i=0;i<=n;i++)
			for(j=0;j<=n;j++)
				c[i][j]=manint;
		cin>>edges;
		for(i=1;i<=edges;i++)
		{
			cin>>a>>b>>percent;
			c[a][b]=c[b][a]=1-percent/100;
		}
		dijkstra(1);
		ans=1.0;
		int k=n;
		while(k!=1)
		{
			ans*=(1-c[k][prev[k]]);
		   k=prev[k];
		}
		printf("%.6lf percent\n",ans*100);
	}
	return 0;
}

• 这里用dijkstra 需要小心，因为是概率，所以要相乘。 (0) zhb_msqx 2007-09-13 12:00:00