题意:给几个国家,然后给这些国家之间的汇率。判断能否通过这些汇率差进行套利交易。
Floyd的算法可以求出任意两点间的最短路径,最后比较本国与本国的汇率差,如果大于1,则可以。否则不可以。
有向图 一个点到另一点的花费为权值相乘 求乘积的最大值 从点i出发 再回到点i的花费如果大于1 就可以
Sample Input
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
Sample Output
Case 1: Yes
Case 2: No
1 # include <iostream> 2 # include <cstdio> 3 # include <cstring> 4 # include <string> 5 # include <algorithm> 6 # include <cmath> 7 # include <map> 8 # define LL long long 9 using namespace std ; 10 11 map<string,int>name; 12 const int MAXN = 35 ; 13 double dis[MAXN][MAXN]; 14 int n ; 15 16 void floyed()//节点从1~n编号 17 { 18 int i,j,k; 19 for(k=1;k<=n;k++) 20 for(i=1;i<=n;i++) 21 for(j=1;j<=n;j++) 22 if(dis[i][k]*dis[k][j] > dis[i][j]) 23 dis[i][j]=dis[i][k]*dis[k][j]; 24 25 } 26 27 int main() 28 { 29 //freopen("in.txt","r",stdin) ; 30 int i,m,j; 31 string str1,str2; 32 double w; 33 int iCase=0; 34 while(scanf("%d",&n),n) 35 { 36 iCase++; 37 for(i=1;i<=n;i++) 38 { 39 cin>>str1 ; 40 name[str1]=i; 41 } 42 for(i=1;i<=n;i++) 43 for(j=1;j<=n;j++) 44 { 45 if(i==j)dis[i][j]=1; 46 else dis[i][j]=0; 47 } 48 scanf("%d",&m); 49 while(m--) 50 { 51 cin>>str1>>w>>str2; 52 dis[name[str1]][name[str2]]=w; 53 } 54 floyed(); 55 bool flag=false; 56 for(i=1;i<=n;i++) 57 if(dis[i][i]>1) 58 {flag=true;break;} 59 if(flag) printf("Case %d: Yes\n",iCase); 60 else printf("Case %d: No\n",iCase); 61 } 62 return 0; 63 }