题目传送门
/*
最短路:Floyd模板题
只要把+改为*就ok了,热闹后判断d[i][i]是否大于1
文件输入的ONLINE_JUDGE少写了个_,WA了N遍:)
*/
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <map>
#include <cmath>
#include <vector>
#include <set>
#include <queue>
using namespace std;
const int MAXN = 1e6 + ;
const int INF = 0x3f3f3f3f;
double d[][];
void Floyd_Warshall(int n)
{
for (int k=; k<=n; ++k)
{
for (int i=; i<=n; ++i)
{
for (int j=; j<=n; ++j)
{
if (d[i][j] < d[i][k] * d[k][j])
{
d[i][j] = d[i][k] * d[k][j];
}
}
}
}
for (int i=; i<=n; ++i)
{
if (d[i][i] > )
{
puts ("Yes"); return ;
}
}
puts ("No"); return ;
}
int main(void) //POJ 2240 Arbitrage
{
#ifndef ONLINE_JUDGE
freopen ("F.in", "r", stdin);
#endif
int n, num; int cas = ;
while (cin >> n && n)
{
for (int i=; i<=n; ++i)
{
for (int j=; j<=n; ++j)
{
if (i == j) d[i][j] = ;
else d[i][j] = ;
}
}
map<string, int> m;
string s, s1, s2;
for (int i=; i<=n; ++i)
{
cin >> s;
m[s] = i;
}
cin >> num;
for (int i=; i<=num; ++i)
{
double w;
cin >> s1 >> w >> s2;
d[m[s1]][m[s2]] = w;
}
cout << "Case " << ++cas << ": ";
Floyd_Warshall (n);
}
return ;
}