Arbitrage(floyd)

 1 #include <stdio.h>
 2 #include <string.h>
 3 const int INF=1<<28;
 4 double dis[50][50];
 5 char str[102][202];
 6 int n,m;
 7 
 8 void init()
 9 {
10     for (int i = 0; i <= n; i ++)
11     {
12         for (int j = 0; j <= n; j ++)
13         {
14             dis[i][j] = 1;
15         }
16     }
17 }
18 int Deal(char *s)
19 {
20     for (int i = 1; i <= n; i ++)
21     {
22         if (!strcmp(s,str[i]))
23             return i;
24     }
25     return 0;
26 }
27 void floyd()
28 {
29     for (int k = 1; k <= n; k ++)
30     {
31         for (int i = 1; i <= n; i ++)
32         {
33             for (int j = 1; j <= n; j ++)
34             {
35                 if (dis[i][j] < dis[i][k]*dis[k][j])
36                     dis[i][j] = dis[i][k]*dis[k][j];
37             }
38         }
39     }
40 
41 }
42 int main()
43 {
44     int o = 0;
45     while(~scanf("%d%*c",&n)&&n)
46     {
47         ++o;
48         char ss[202],ss1[202];
49         double rate;
50         init();
51         for (int i = 1; i <= n; i ++)
52         {
53             scanf("%s",str[i]);
54         }
55         scanf("%d%*c",&m);
56         while(m--)
57         {
58             scanf("%s",ss);
59             int i = Deal(ss);
60             scanf("%lf",&rate);
61             scanf("%s",ss1);
62             int j = Deal(ss1);
63             dis[i][j] = rate;
64         }
65         floyd();
66         int flag = 0;
67         for (int i = 1; i <= n; i ++)
68         {
69             if (dis[i][i] > 1)
70                 flag = 1;
71         }
72         if (flag)
73             printf("Case %d: Yes
",o);
74         else
75             printf("Case %d: No
",o);
76     }
77     return 0;
78 }
View Code