1437.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1437 on 2006-01-10 at 23:53:47 */ 
#include <cstdio>
#include <cmath>
#include <map>
#include <algorithm>
using namespace std;

const int MAX = 32;
const double INF = 2e10;
const double eps = 1e-4;

struct cmp {
	bool operator ()(const char* s1, const char* s2) const {
		return strcmp(s1, s2) < 0;
	}
};

int main()
{
	int i, j, k, t;
	double buy[MAX][MAX], d;
	char coin[MAX][MAX], na[MAX], nb[MAX];
	int n, m;
	map<const char*, int, cmp> dict;
	
	for(t = 1; scanf("%d", &n) != EOF && n != 0; t++) {
		dict.clear();
		for(i = 0; i < n; i++) {
			buy[i][i] = 0;
			for(j = i+1; j < n; j++) buy[i][j] = buy[j][i] = INF;
		}
		for(i = 0; i < n; i++) scanf("%s", coin[i]), dict[coin[i]] = i;
		scanf("%d", &m);
		for(i = 0; i < m; i++) {
			scanf("%s %lf %s", na, &d, nb);
			int o1 = dict.find(na)->second, o2 = dict.find(nb)->second;
			buy[o1][o2] = -log10(d);
		}
		bool rich = false;
		for(k = 0; k < n && !rich; k++)
			for(i = 0; i < n && !rich; i++)
				for(j = 0; j < n && !rich; j++) {
					buy[i][j] = min(buy[i][j], buy[i][k]+buy[k][j]);
					if(buy[i][i] < -eps) rich = true;
				}
		printf("Case %d: %s\n", t, rich ? "Yes" : "No");
	}
	
	return 0;
}