poj2240 Floyd

   这题也是求正权回路的，但和之前那题用Bellman-ford的不一样，因为这个是不知道源点的。所以用Floyd可以求出所有节点的最短路径，然后判断a[i][i]是否大于1即可。反之，如果知道了确定的源节点，那么我们用Bellman-ford的话会更方便。具体他们的区别，请看这里。

//Floyd
#include <iostream>
#include <fstream>
#include <map>
#include <string>using namespace std;
#define LEN 35
#define INF 10000double a[LEN][LEN],rate;
int n,m;
map<string,int>name;void Floyd()
{int k,i,j;for(k=1; k<=n; k++){for(i=1; i<=n; i++){for(j=1; j<=n; j++){if(a[i][j]<a[i][k]*a[k][j])a[i][j]=a[i][k]*a[k][j];}}}
}int main()
{int i,k=1;char str[50],str1[50],str2[50];freopen("acm.txt","r",stdin);while( scanf("%d",&n)!=EOF && n){    memset(a,1,sizeof(a));for(i=1; i<=n; i++){cin>>str;name[str]=i;//    a[i][i]=1;
    }scanf("%d",&m);for(i=1; i<=m; i++){cin>>str1>>rate>>str2;int m,n;a[name[str1]][name[str2]]=rate;}Floyd();for(i=1; i<=n; i++){if( a[i][i]>1 ){printf("Case %d: Yes\n",k);break;}}if(i>n)printf("Case %d: No\n",k);k++;}return 0;
}