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;
  }
}