2009-2-24-pku2240.txt

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

/*
题目大意：
跟昨天做的那个题目有点共同之处 都是把Floyd_Warshall换了一种用法 
在此题中就是更新边权乘积到最大值 最后找有没有边权乘积大于一的环
想到了就很简单

*/
#include<stdio.h>
#include<string.h>
const int MAX=35;
const double INF=1e100;
char s[MAX][105];
/*
多源最短路径，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])
					min[i][j]=min[i][k]*min[k][j],pre[i][j]=pre[k][j];
}
int Find(int n,char *string)
{
	int i;
	for(i=1;i<=n;i++)
		if(strcmp(s[i],string)==0)
			return i;
		return 0;
}
int main()
{
	int i,m,n,count=1;
	int pre[MAX][MAX];
	char s1[105],s2[105];
	double mat[MAX][MAX],min[MAX][MAX],distance;
	while(scanf("%d",&n),n)
	{
		getchar();
		for(i=1;i<=n;i++)
			scanf("%s",s[i]);
		scanf("%d",&m);
		getchar();
		memset(mat,0,sizeof(mat));
		for(i=1;i<=m;i++)
		{
			scanf("%s %lf %s",s1,&distance,s2);
			mat[Find(n,s1)][Find(n,s2)]=distance;
		}
		Floyd_Warshall(n,mat,min,pre);
		for(i=1;i<=n;i++)//用来检测是否有边权乘积大于一的环-->min[i][i]
		    if(min[i][i]>1.0)
			{
				printf("Case %d: Yes\n",count++);
					 goto loop;
			}
	     printf("Case %d: No\n",count++);
         loop:;
	}
	return 0;
}
/*
3
USDollar
BritishPound
FrenchFranc
3
USDollar 0.5 BritishPound
BritishPound 10.0 FrenchFranc
FrenchFranc 0.21 USDollar

3
USDollar
BritishPound
FrenchFranc
6
USDollar 0.5 BritishPound
USDollar 4.9 FrenchFranc
BritishPound 10.0 FrenchFranc
BritishPound 1.99 USDollar
FrenchFranc 0.09 BritishPound
FrenchFranc 0.19 USDollar

0


Case 1: Yes
Case 2: No
*/