poj 2240 bellman

[cpp]

//求一個回路，從一種貨幣兌換一圈回到自身，看一路上匯率之積是否大於1  
//擴展常規的最短路bellman,算到dist(n)，就是算到回路  
maxdist(k)[v] = max{maxdist(k-1)[v],maxdist(k-1)[u]*C(u,v)} 
 
#include <iostream>  
#include <cstring>  
#include <cstdio>  
#define maxn 50  
#define maxm 1000  
 
using namespace std; 
 
struct exchange 
{ 
  int ci,cj; 
  double cij; 
}ex[maxm]; 
 
char name[maxn][20],a[20],b[20]; 
 
double x; 
int n,m; 
 
double maxdist[maxn]; 
int flag; 
int kase = 0; 
 
int readcase() 
{ 
  scanf("%d",&n); 
  if(n == 0) 
    return 0; 
  for(int i = 0; i < n; i++) 
    scanf("%s",name[i]); 
  scanf("%d",&m); 
  for(int i = 0; i < m; i++) 
    { 
      int q,w; 
      scanf("%s %lf %s",a,&x,b); 
      for(q = 0; strcmp(a,name[q]);q++) 
    ; 
      for(w = 0; strcmp(b,name[w]);w++) 
    ; 
      ex[i].ci = q; 
      ex[i].cj = w; 
      ex[i].cij = x; 
    } 
  return 1; 
} 
 
 
void bellman(int v0) 
{ 
  flag = 0; 
  memset(maxdist,0,sizeof(maxdist)); 
  maxdist[v0] = 1; 
  for(int k = 1; k <= n; k++)  //1---n  
    { 
      for(int i = 0; i < m; i++) 
    { 
      if(maxdist[ex[i].ci]*ex[i].cij > maxdist[ex[i].cj]) 
        maxdist[ex[i].cj] = maxdist[ex[i].ci]*ex[i].cij; 
    } 
    } 
  if(maxdist[v0] > 1.0) 
    flag = 1; 
} 
 
int main() 
{ 
  while(readcase()) 
    { 
      for(int i = 0; i < n; i++) 
    { 
      bellman(i); 
      if(flag) 
        break; 
    } 
      if(flag) 
    printf("Case %d: Yes\n",++kase); 
      else 
    printf("Case %d: No\n",++kase); 
    } 
}