POJ 2240 Arbitrage（floyd）

题意：好吧，又是一个换钱的题：套利是利用货币汇率的差异进行的货币转换，例如用1美元购买0.5英镑，1英镑可以购买10法郎，一法郎可以购买0.21美元，所以0.5*10*0.21 = 1.05，从中获利百分之五，所以需要编写一个程序，在进行完转换之后能不能获利，如果能就输出Yes，反之No；

样例解释：

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为结束，第一行是一个整数n代表着下面n种货币可以进行转换，再是一个整数m，下面m行代表着m次的转换

思路：用最短路稍微一修改思路即可

 1 #include <cstdio>
 2 #include <cstring>
 3 #include<iostream>
 4 #include<stdlib.h>
 5 #include<algorithm>
 6 using namespace std;
 7 const int oo = 1<<28;
 8 const int maxn = 1001;
 9 double map[maxn][maxn];
10 int n, m,i,j,k,a,b,cnt = 0;
11 char sh[maxn][maxn];
12 char sh1[maxn],sh2[maxn];
13 void floyd()
14 {
15     for(k = 0; k < n; k++)
16     {
17         for(i = 0; i < n; i++)
18         {
19             for(j = 0; j < n; j++)
20             {
21                 if(map[i][k]*map[k][j] > map[i][j])
22                 {
23                     map[i][j] = map[i][k]*map[k][j];
24                 }
25             }
26         }
27     }
28     int flag = 0 ;
29     for(i = 0 ; i < n ; i++)
30     {
31         if(map[i][i] > 1.0)
32         {
33             flag = 1 ;
34             break;
35         }
36     }
37     if(flag)
38         printf("Case %d: Yes
",cnt);
39     else
40         printf("Case %d: No
",cnt);
41 }
42 
43 int main()
44 {
45     double t;
46     while(scanf("%d",&n)&&n)
47     {
48         cnt++;
49         memset(map,oo,sizeof(map));
50         for(i = 0 ; i < n ; i++)
51         {
52             scanf("%s",sh[i]);
53             map[i][i] = 1.0 ;
54         }
55         scanf("%d",&m);
56         for(i = 0 ; i <m ; i++)
57         {
58             scanf("%s %lf %s",sh1,&t,sh2);
59             for(j = 0 ; j < n ; j++)
60             {
61                 if(strcmp(sh1,sh[j]) == 0)
62                 {
63                     //a = j ;
64                     break;
65                 }
66             }
67             for(k = 0 ; k < n ; k++)
68             {
69                 if(strcmp(sh2,sh[k]) == 0)
70                 {
71                     //b = k ;
72                     break ;
73                 }
74             }
75             map[j][k] = t;
76         }
77         floyd();
78     }
79     return 0;
80 }

View Code