poj 2240 Arbitrage ( bellman+map 判断 环）

本题面壁：

  1：数据的范围 （在第一次写代码马虎后，很不容易找出）

  2：思路清晰后在写代码。。。、

#include<iostream>
#include<cstdio>
#include<string>
#include<string.h>
#include<map>
#define N 35
using namespace std;
struct node
{
    int st,ed;
    double key;
}num[N*N];
int n,m;
int bellman(int s)
{
    double dist[N];
    for(int i=0;i<=n;i++) dist[i]=0;
    dist[s]=1;
    for(int k=1; k <= n; k++ )
    for(int j=0;j<m;j++)
    {
        int u=num[j].st,v=num[j].ed;
        if(dist[v] < dist[u]*num[j].key)
        dist[v]=dist[u]*num[j].key;
    }
    return dist[s]>1;
}
int main()
{
    int cs=1;
    while(scanf("%d%*c",&n),n)
    {
        map<string,int> p;
        for(int i=1;i<=n;i++)
        {
            string str;
            cin>>str;getchar();
            p[str]=i;
        }

        cin>>m;
        for(int i=0;i<m;i++)
        {
           char st[100],ed[100];double key;
           scanf("%s %lf %s%*c",st,&key,ed);
          // cout<<ed<<endl;
           num[i].st=p[st],num[i].ed=p[ed];
           num[i].key=key;
        }
        printf("Case %d: ",cs++);
        if(bellman(1)) puts("Yes");
        else puts("No");
    }
    return 0;
}