hdu 1217 汇率 Floyd

题意：给几个国家，然后给这些国家之间的汇率。判断能否通过这些汇率差进行套利交易。

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

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
",iCase);
60         else printf("Case %d: No
",iCase);
61     }
62     return 0;
63 }

View Code