首页 > 代码库 > poj2240Arbitrage最长路

poj2240Arbitrage最长路

  今天下午的痛。  很冲的和 Gxwar 说来题爽爽 ,然后就被这水题爽了一下午。

#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <climits>#include <string>#include <iostream>#include <map>#include <cstdlib>#include <list>#include <set>#include <queue>#include <stack>using namespace std;const double INF=10000000;double Map[44][44];double dis[44];int vis[100];int cnt[100];int n;int spfa(int x){    memset(cnt,0,sizeof(cnt));    for(int i =0 ;i<n;i++)        dis[i]=0;    dis[x]=1;vis[x]=1;    memset(vis,0,sizeof(vis));    queue<int> q;    q.push(x);    while(!q.empty()){        int cur=q.front() ;q.pop();        if(cnt[cur]>=n) return 1;        vis[cur]=0;        for(int i =0 ;i<n;i++)        if(Map[cur][i]){            if(dis[i]<dis[cur]*Map[cur][i]){                dis[i]=dis[cur]*Map[cur][i];                if(!vis[i]){                    vis[i]=1;                    cnt[i]++;                    q.push(i);                }            }        }    }    return 0;}int main(){    string a,c;double b;    int m;    int Icase=0;    map<string ,int>  str;    while(cin>>n,n){        for(int i=0;i<n;i++){            cin>>a; str[a]=i;        }        scanf("%d",&m);        for(int i =0;i<n;i++)            for(int j=0;j<n;j++)            Map[i][j]=0;        for(int i= 0;i< m;i++){            cin>>a>>b>>c;int t=str[a];int t1=str[c];            Map[t][t1]=b;        }        int flag=0;        for(int i= 0;i<n;i++){            if(spfa(i)){flag=1;break;};        }        printf("Case %d: ",++Icase);        if(flag) cout<<"Yes"<<endl;        else cout<<"No"<<endl;    }    return 0;}