【floyd神器】HDU 1217 Arbitrage

http://acm.hdu.edu.cn/showproblem.php?pid=1217

题意：给出各种钱之间的兑换机制，求不断兑换后是否可以产生利润？
对于第一个案例：start with 1 US dollar and buy 0.5 * 10.0 * 0.21 = 1.05 US dollars, making a profit of 5 percent

Sample Input
3
USDollar
BritishPound
FrenchFranc
3
USDollar 0.5 BritishPound
BritishPound 10.0 FrenchFranc
FrenchFranc 0.21 USDollar
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

Sample Output
Case 1: Yes
Case 2: No

#include <iostream>
#include <fstream>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <utility>
#include <stack>
#include <list>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
//#include <ctime>
#include <ctype.h>
using namespace std;
#define L long long
#define inf 0x3fffffff
#define M 1005

map<string, int> m;    //映射
double mon[35][35];

int main()
{
	double x;
	int n, i, k, j, cc = 1;
	string s, p;
	while (cin >> n, n)
	{
		for (i = 0; i < n; i++)
		{
			cin >> s;
			m[s] = i;    //把string映射为[0,n-1]的编号
		}
		cin >> k;
		memset (mon, 0, sizeof(mon));   //初始化
		while (k--)
		{
			cin >> s >> x >> p;
			mon[m[s]][m[p]] = x;    //从s号变为p号要乘以x
		}
        /*****************floyd神器*****************/
		for (i = 0; i < n; i++)
			for (j = 0; j < n; j++)
				for (k = 0; k < n; k++)    //floyd-构造所有情况的神器
					if (mon[j][k] < mon[j][i] * mon[i][k])
                      //就像路径，从j到k可以由j到i再到k
						mon[j][k] = mon[j][i] * mon[i][k]; //更新，所谓的松弛技术
        /*****************floyd神器*****************/
		for (i = 0; i < n; i++)
			if (mon[i][i] > 1.0)    //经过变换后>1.0说明获得利润
				break;
		printf ("Case %d: ", cc++);
		if (i < n)
			puts ("Yes");
		else puts ("No");
	}
	return 0;
}