poj 2240

回転:http://blog.sina.com.cn/s/blog_803 d 08 c 00100 xql.html
bellman-fordアルゴリズムでやります.一方の配列を宣言してからdist【i】は両替できるソース通貨の数を表しています.初期化の時、ソースを1として、他の点を0として、緩和関数を設定すると、起点が両替できる数より少ない場合、終点で両替できる数に金利を掛けて更新します.

#include <iostream>
#include <cstdio>
#include <string.h>
using namespace std;
int n,m ;
struct point
{
      int s,e;
      double rate ;
} edge[1000] ;
double dist[1000] ;
int bellman ()
{
      for (int i=1 ; i<=n ; i++) dist[i] = 0 ;
      dist[1] = 1 ;
      for (int i=1 ; i<n ; i++){
            for (int j=1 ; j<=m ; j++){
                  if (dist[edge[j].e]<dist[edge[j].s]*edge[j].rate){
                        dist[edge[j].e] = dist[edge[j].s]*edge[j].rate ;
                  }
            }
      }
      for (int i=1 ; i<=m ; i++){
            if (dist[edge[i].e] <dist[edge[i].s]*edge[i].rate ) return 1 ;
      }
      return 0 ;
}
int main()
{
      int casenum=0 ;
      while (scanf("%d",&n),n){
            casenum++ ;
            char moneyname[40][40] ;
            for (int i=1 ; i<=n ; i++){
                  scanf("%s",moneyname[i]) ;
            }
            char first[40],last[40] ;
            double rate ;
            scanf("%d",&m) ;
            for (int i=1 ; i<=m ; i++){
                  int f,l ;
                  scanf("%s%lf%s",first,&rate,last) ;
                  for (int j=1 ; j<=n ; j++){
                        if (strcmp(first,moneyname[j])==0) f=j ;
                        if (strcmp(last,moneyname[j])==0) l=j ;
                  }
                  edge[i].s = f ;
                  edge[i].e = l ;
                  edge[i].rate = rate ;
            }
            if (bellman()) printf("Case %d: Yes
",casenum) ;
            else printf("Case %d: No
",casenum) ;
      }
    return 0;
}