套汇是指利用货币汇兑率的差异将一个单位的某种货币转换为大于一个单位的同种货币。例如，假定1 美元可以买0.7 英镑，1 英镑可以买9.5 法郎，且1 法郎可以买到0.16美元。通过货币兑换，一个商人可以从1 美元开始买入，得到0.7×9.5×0.16=1.064美元，从而获得6.4%的利润。 给定n 种货币c1 ,c2 ,... ,cn的有关兑换率，试设计一个有效算法，用以确定是否存在套汇的可能性。
输入
含多个测试数据项。每个测试数据项的第一行中只有1 个整数n (1< =n< =30)，表示货币总数。其后n行给出n种货币的名称。接下来的一行中 有1 个整数m，表示有m种不同的货币兑换率。其后m行给出m种不同的货币兑换率，每行有3 个数据项ci ， rij 和cj ，表示货币ci 和cj的兑换率为 rij。文件最后以数字0 结束。
输出
对每个测试数据项j，如果存在套汇的可能性则输出“Case j Yes”， 否则输出“Case j No”。
样例输入
3 USDollar BritishPound FrenchFranc 3 USDollar 0.5 BritishPound BritishPound 10.0 FrenchFranc FrenchFranc 0.21 USDollar3 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
对Floyd算法的简单应用，代码如下:
#include<iostream>
#include<cstring>
#include<cmath>
#include<map>
#include<utility>
using namespace std;
#define INF 0x3f3f3f3f
#define MAX 45
double path[MAX][MAX];
map<string,int>ratemap;
bool Floyd(int n)
{for(int k=0;k<n;k++){for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(path[i][j]<path[i][k]*path[k][j])path[i][j]=path[i][k]*path[k][j];}}}for(int i=0;i<n;i++){if(path[i][i]>1)return true;}return false;
}
int main()
{int n,m,count=1;string nameA,nameB,name;double rate;while(cin>>n&&n){memset(path,0,sizeof(path));for(int i=0;i<n;i++){cin>>name;pair<string,int>a(name,i);ratemap.insert(a);path[i][i]=1;}cin>>m;for(int i=0;i<m;i++){cin>>nameA>>rate>>nameB;path[ratemap[nameA]][ratemap[nameB]]=rate;}if(Floyd(n)) cout<<"Case "<<count<<" Yes"<<endl;else cout<<"Case "<<count<<" No"<<endl;count++;ratemap.clear();
}
return 0;
}