2009-2-23-pku2472.txt

数据结构中的单元最短路径算法的题目和源代码！其中所有的题目都能在PKU上找的到！

/*
题目大意：
每一条边表示从Ii->j的概率!
求从第一点开始能到最后一点n的最大概率！

这算是一道比较简单的题目，很容易转化成最长路径问题，接着就可以用Floyd-Warshall算法轻松解决。
转化的方法是，将路径的长度除以一百，变成小数，再将Floyd-Warshall中的加法变成乘法，就可以轻松解决。
*/
#include<stdio.h>
#include<string.h>
const int MAX=105;
const int INF=100005;
/*
多源最短路径，floyd_warshall算法，复杂度0(n^3)
求出所有点对之间的最短路径，传入图的大小和邻接阵
返回各个点间最短距离min[][]和路径pre[][],pre[i][j]记录i到j最短路径上j的父节点
可更改路权类型，路权必须非负！
*/
void Floyd_Warshall(int n,double mat[][MAX],double min[][MAX],int pre[][MAX])
{
	int i,j,k;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			min[i][j]=mat[i][j],pre[i][j]=(i==j)?-1:i;
	for(k=1;k<=n;k++)
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
				if(min[i][k]*min[k][j]>min[i][j])//变成乘法是这个题目的关键之处！1->2的概率为0.75 2->3的概率为0.10 则1->2->3的概率为0.75*0.10
					min[i][j]=min[i][k]*min[k][j],pre[i][j]=pre[k][j];
}

int main()
{
	int i,n,st,ed,distance,m;
	double mat[MAX][MAX],min[MAX][MAX];
	int pre[MAX][MAX];
	while(scanf("%d",&n),n)
	{
		memset(mat,0,sizeof(mat));//将mat[][]开始初始化为INF，这个很重要！, 求最大路径初始化为0 !
		scanf("%d",&m);
		for(i=1;i<=m;i++)
		{
			scanf("%d%d%d",&st,&ed,&distance);
			mat[st][ed]=0.01*distance;
			mat[ed][st]=0.01*distance;
		}
		Floyd_Warshall(n,mat,min,pre);
		printf("%.6lf percent\n",min[1][n]*100.0);
	}
	return 0;
}
/*
5 7
5 2 100
3 5 80
2 3 70
2 1 50
3 4 90
4 1 85
3 1 70
0


61.200000 percent
*/