首页 > 代码库 > 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;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。