这题和以往的求最短路的题目略微有点不一样，以往求的都是最小的，这题求的是大的，而且还是乘法。
我们求的时候初始化的时候就要进行相反的初始化了，把它们初始化为0，然后比较大的就更新。
因为这题的点少边多，所以spfa会比较好，我们对于每种货币都跑一遍，如果其中任何货币的从它到它的路，即d[start]大于1，就说明可以升值。
还有边是单向边，因为货币兑换在题目输入的意思是单向的。
d[start]的初始值为1，用map 的时候，记得清空，不然反复使用可能会错。
#include <cstdio>
#include <queue>
#include <map>
using namespace std;
map<string, int> mp;
double trip[35][35], d[35], k;
char s1[105], s2[105];
int n, m, c = 1;
int vis[35];
int SPFA(int s)
{
queue<int> q;
for (int i = 0; i < 35;i++)
vis[i] = d[i] = 0;
d[s] = 1.0;
vis[s] = 1;
q.push(s);
while (!q.empty()) {
int now = q.front();
q.pop();
vis[now] = 0;
for (int i = 1; i <= n;i++) {
if (d[now]*trip[now][i]>d[i]) {
d[i] = d[now] * trip[now][i];
if (d[s]>1.0)
return 1;
if (!vis[i]) {
q.push(i);
vis[i] = 1;
}
}
}
}
return 0;
}
int main()
{
while (scanf("%d",&n)&&n) {
mp.clear();
for (int i = 1; i <= n;i++) {
scanf("%s", s1);
mp[s1] = i;
}
scanf("%d", &m);
for (int i = 0; i < 35;i++)
trip[i][i] = 1.0;
for (int i = 0; i < m;i++) {
scanf("%s%lf%s", s1, &k, s2);
trip[mp[s1]][mp[s2]] = k;
}
int flag = 0;
for (int i = 1; i <= n;i++) {
if (SPFA(i)) {
flag = 1;
break;
}
}
printf("Case %d: %s
",c++,flag?"Yes":"No");
}
return 0;
}