题意：
各国的汇率兑换..
给出各国之间汇率兑换的比例，然后问你是否可以通过不断地兑换最后挣钱..
譬如美金兑换英镑 是0.5
英镑兑换法币是 10
法币兑换美金是 0.21
所以通过1美金兑换成0.5英镑然后兑换成0.5*10 = 5的法币再兑换成5*0.21的美金就可以得到1.05的美金就可以挣钱了~
思路：
这个跟最短路的意思其实是一样的..
不过是看看最后的dis[1][1]是否大于1
Tips：
这题由题意可以发现最后的结果是由G[1][i]*G[i][j]*G[j][k]*..G[..][1]得到的..
这里因为是乘运算..所以其实和最短路中的负权路是一样的..
所以的所以不能用floyd而应该用spfa或者是floyd..
Code：
1 #include <stdio.h> 2 #include <iostream> 3 #include <cstring> 4 #include <map> 5 using namespace std; 6 #define INF 0x11111111 7 8 const int MAXN = 35; 9 10 int n; 11 double G[MAXN][MAXN]; 12 double dis[MAXN][MAXN]; 13 14 int main() 15 { 16 // freopen("in.txt", "r", stdin); 17 int m, iCase = 1; 18 double a; 19 string str, str1; 20 map<string, int> M; 21 while (cin >> n) { 22 if (n == 0) break; 23 M.clear(); 24 memset(G, INF, sizeof(G)); 25 for (int i = 1; i <= n; ++i) { 26 cin >> str; 27 M[str] = i; 28 } 29 cin >> m; 30 while (m--) { 31 cin >> str >> a >> str1; 32 G[M[str]][M[str1]] = a; 33 } 34 35 for (int k = 1; k <= n; ++k) 36 for (int i = 1; i <= n; ++i) 37 for (int j = 1; j <= n; ++j) { 38 if (G[i][k] != INF && G[k][j] != INF && k != j && k != j && G[i][j] < G[i][k]*G[k][j]) 39 G[i][j] = G[i][k]*G[k][j]; 40 } 41 cout << "Case " << iCase++ << ": "; 42 if (G[1][1] > 1) puts("Yes"); 43 else puts("No"); 44 45 } 46 return 0; 47 }