HDU 1217 Arbitrage題意是說給你N種貨幣以及，貨幣與貨幣之間的M種匯率，
讓你判斷是否存在經(jīng)過若干次貨幣的兌換使得某種貨幣的
價(jià)值大于原來本身的價(jià)值，比如所：美元：美元 = 1 ： 1；
題意就是讓你判斷，在當(dāng)前的貨幣兌換率的基礎(chǔ)上，能不能
使 美元 ： 美元 > 1 : 1; 利用Floyd算法即可搞定，代碼如下：
1 #include<iostream>
2 #include<queue>
3 #include<cstring>
4 #define size 40
5 #define inf 0
6 using namespace std;
7 char s1[100],s2[100],str[40][100];
8 double map[size][size], dir[size], x;
9 int n, m, k, a, b, flag = 1;
10
11 int tree(char s[])
12 {
13 for(int a=0;a<n;a++)
14 if(strcmp(s,str[a])==0)return a;
15 }
16
17 int main()
18 {
19 while(scanf("%d", &n), n)
20 {
21 int c,d,e;
22 k=0;
23 for(a=0;a<n;a++)
24 {
25 scanf("%s", &str[a]);
26 }
27 scanf("%d", &m);
28 for(a=0;a<size;a++)
29 for(b=0;b<size;b++)
30 map[a][b]=0;
31 while(m--)
32 {
33 scanf("%s %lf %s", &s1, &x, &s2);
34 a=tree(s1);
35 b=tree(s2);
36 map[a][b]=x;
37 }
38 for(c=0;c<n;c++)
39 for(d=0;d<n;d++)
40 for(e=0;e<n;e++)
41 if(map[d][c]*map[c][e]>map[d][e])
42 {
43 map[d][e]=map[d][c]*map[c][e];
44 if(map[0][0]>1)break;
45 }
46 if(map[0][0]>1)
47 cout<<"Case "<<flag<<": Yes"<<endl;
48 else
49 cout<<"Case "<<flag<<": No"<<endl;
50 flag++;
51 }
52 }