POJ 2240 Arbitrage

/* bellman，加上map，判断是否有负权回路即可
* */

#include<iostream>
#include<string>
#include<map>
using namespace std;
#define MAX 1000
#define INF 999999
#define EPS 1e-8
struct Node{
    int u,v;
    double val;
}node[MAX];
int nv,ne,start;
double dist[MAX];
int bellman()
{
    int i,j,flag;
    double tmp;
    for(i=1;i<=nv;++i)
        dist[i] = -1;
    dist[start] = 1;
    for(i=1;i<nv;++i)
    {
        flag = 0;
        for(j=1;j<=ne;++j)
        {
            if(dist[node[j].u]==INF)
                continue;
            tmp = dist[node[j].u]*node[j].val;
            if(tmp>dist[node[j].v]+EPS)
            {
                dist[node[j].v] = tmp;
                flag = 1;
            }
        }
        if(flag == 0) return 0 ;
        
    }
    for(i=1;i<=ne;++i)
        if(dist[node[i].u]!=INF&&dist[node[i].u]*node[i].val>dist[node[i].v]+EPS)
            return 1;
    return 0;
}
int main()
{
    int i,j,cnt=0;
    double val;
    char a[100],b[100];
    map<string,int> name;
    while(1)
    {
        scanf("%d",&nv);
        if(!nv) break;
        name.clear();
        int flag =0 ;
        ++cnt;
        for(i=1;i<=nv;++i)
        {
            scanf("%s",a);
            name[string(a)] = i;
        }
        scanf("%d",&ne);
        for(i=1;i<=ne;++i)
        {
            scanf("%s%lf%s",&a,&val,&b);
            node[i].u = name[string(a)];
            node[i].v = name[string(b)];
        //    if(node[i].v==node[i].u&&val>1)
        //        flag = 1;
            node[i].val = val;
        }
        start = 1;
        printf("Case %d: ",cnt);
        if(flag == 1)
            printf("Yes\n");
        else if(bellman())
            printf("Yes\n");
        else
            printf("No\n");
    }
    return 0;
}