PKU 2240 Arbitrage
http://poj.org/problem?id=2240
通貨の両替で、利益を上げることが出来るかどうかを判定しろというような問題。
ワーシャルフロイド。
偉大なアルゴリズムだと思います。
double co[40][40]; main(){ int n; int ca=0; while(cin>>n,n){ ++ca; map<string,int>stoi; memset(co,0,sizeof(co)); rep(i,n){ co[i][i]=1; string st; cin>>st; stoi[st]=i; } int t; cin>>t; rep(i,t){ string a,b; double p; cin>>a>>p>>b; co[stoi[a]][stoi[b]]=p; } rep(k,n) rep(i,n)rep(j,n){ co[i][j]=max(co[i][j],co[i][k]*co[k][j]); } bool ok=false; rep(i,n)ok|=co[i][i]>1.0; cout<<"Case "<<ca<<": "; if(ok)cout<<"Yes"<<endl; else cout<<"No"<<endl; } }