题意：套利，一个US币换取0.5 British pound，而1 British pound 换取10.0 French francs,同一时候 1 French franc buys 0.21 US dollar. 那么1
US dollar 能够换取 0.5 * 10.0 * 0.21 = 1.05 US dollars ，通过一系列换取得到1.05US币，那么就能够从中获取利润，问：给出一些货币，以及兑换率，问能否够从中获利

题解：这里能够用最短路的方法解决：我们在边的结构体 加入兑换率，然后松弛过程中，不同于最短路的取小，我们要让它获利就要取大，那么我们在spfa之前的dis初始化的时候，我们就所有memset为0，dis[src]
源点就赋值 1.这样我们就能够依照上面的方式松弛操作，然后推断是否构成负环。。假设能够，那么意思就是dis 会越来越大，spfa 用cnt[i]表示 i 入队的次数，i的入队次数大于 顶点数就说明构成负环

上马：

#include <iostream>

#include <map>

#include <string>

#include <cstring>

#include <queue>

using namespace std;

#define MAX 35

int N,M;

struct Edge{

    int to,next;

    double rate;

}edge[MAX*MAX];

int head[MAX];

void add(int u,int v,double rate,int i)

{

    edge[i].to = v;

    edge[i].rate = rate;

    edge[i].next = head[u];

    head[u] = i;

}

double dis[MAX];

int cnt[MAX];

bool flag[MAX];

bool spfa()

{

    memset(flag,false,sizeof(flag));

    memset(cnt,0,sizeof(cnt));

    memset(dis,0,sizeof(dis));

    dis[0] = 1;

    flag[0] = true;

    cnt[0] = 1;

    queue<int> q;

    q.push(0);

    while(!q.empty())

    {

        int u = q.front(); q.pop();

        flag[u] = false;

        for(int i = head[u]; i != -1; i = edge[i].next)

        {

            int v = edge[i].to;

            double rate = edge[i].rate;

            if(dis[v] < dis[u]*rate){

                dis[v] = dis[u]*rate;

                if(!flag[v]){

                    q.push(v);

                    flag[v] = true;

                    cnt[v] ++;

                }

            }

            if(cnt[v] > N) return true;

        }

    }

    return false;

}

int main()

{

    string a,b;

    double rate;

    int cas = 1;

    while(cin >> N)

    {

        if(!N) break;

        map<string,int>m;

        for(int i = 0; i < N; i ++) {

            cin >> a;

            m[a] = i;

        }

        cin >> M;

        memset(head,-1,sizeof(head));

        for(int i = 0; i < M; i ++){

            cin >> a >> rate >> b;

            int u = (*m.find(a)).second;

            int v = (*m.find(b)).second;

            add(u,v,rate,i);

        }

        cout << "Case " << cas++ << ": ";

        if(spfa()) cout << "Yes" <<endl;

        else cout << "No" <<endl;

    }

    return 0;

}