最短路 floyd poj 2240 Arbitrage

思路：直接见图，floyd一遍之后看是否有自身大于一的。
注意是有向图
代码：
View Code
 1 #include <iostream>
 2 #include <map>
 3 #include <string>
 4 #include <stdio.h>
 5 using namespace std;
 6 map<string,int> st;
 7 string s1,s2;
 8 double mp[50][50];
 9 void init(int n)
10 {
11     int i,j;
12     for(i = 0;i < n;i++)
13     {
14         for(j = 0;j < n;j++)
15         mp[i][j] = 1;
16     }
17     return ;
18 }
19 int main()
20 {
21     int m,n,i,j,k;
22     double r;
23     int t = 0;
24     while(scanf("%d",&n) && n)
25     {
26         init(n);
27         for(i = 0;i < n;i++)
28         {
29             cin>>s1;
30             st[s1] = i;
31         }
32 
33         cin>>m;
34         while(m--)
35         {
36             cin>>s1>>r>>s2;
37             mp[st[s1]][st[s2]] = r;
38         }
39 
40         for(k = 0;k < n;k++)
41         {
42             for(j = 0;j < n;j++)
43             {
44                 for(i = 0;i < n;i++)
45                 if(mp[j][i] < mp[j][k]*mp[k][i])
46                 mp[j][i] = mp[j][k]*mp[k][i];
47             }
48         }
49 
50         int leap;
51         leap = 0;
52         for(i = 0;i < n;i++)
53         {
54             if(mp[i][i] > 1)
55             leap = 1;
56         }
57         printf("Case %d: ",++t);
58         if(leap)
59         puts("Yes");
60         else
61         puts("No");
62     }
63 
64     return 0;
65 }