POJ 2240 Arbitrage

1797 ワード

元の通貨交換のテーマと似ていて、n中通貨とm中通貨の間の交換為替レートをあげて、富を増値させることができるかどうかを聞いています.ここでmapを使いました.Wrongは2回、1回の辺集配列が小さくなって、それからYes、No大文字と小文字が間違っていて、悲しいですね.朝のいい気分に影響します.Bellman-Ford.
コード:
#include<iostream>
#include<string>
#include<map>
#define maxn 40
using namespace std;
map<string,int> mp;
struct Edge
{
       int v,u;
       double w;
} e[1005];
int size,n;
double dist[maxn];
void AddEdge(int a,int b,double c)
{
     e[size].u=a;
     e[size].v=b;
     e[size].w=c;
     size++;
}
bool Bellman_Ford()
{
     int i,j;
     for( i=1; i<=n; i++){
          bool flag=false;
          for( j=0; j<size; j++){
               // cout<<e[j].u<<' '<<e[j].w<<endl;
               if( dist[e[j].u]*e[j].w>dist[e[j].v]){
                   dist[e[j].v]=dist[e[j].u]*e[j].w;
                   flag=true;
               }
          }
          if( !flag) break;
          if( i==n&&flag) return true;
     }
     return false;
}
int main()
{
    int m,ca,i;
    double c;
    string str1,str2;
    ca=0;
    while( cin>>n&&n){
           ++ca;
           mp.clear();
           for( i=1; i<=n; i++){
                cin>>str1;
                mp[str1]=i;
           }
           cin>>m;
           memset(e,0,sizeof(e));
           size=0;
           while( m--){
                  cin>>str1>>c>>str2;
                  AddEdge(mp[str1],mp[str2],c);
           }
          memset(dist,0,sizeof(dist));
                dist[1]=1;
           cout<<"Case "<<ca<<": ";
           if( Bellman_Ford())
               cout<<"Yes"<<endl;
           else
               cout<<"No"<<endl;
    } 
}