2013年8月18日

UVa 436 - Arbitrage (II)

#include <cstdio>
#include <string>
#include <map>
#include <algorithm>
using namespace std;

int main() {
  int n, C = 1;
  while (scanf("%d", &n) && n) {
    map<string, int> indexOf;
    for (int i = 0; i < n; i++) {
      char s[99];
      scanf("%s", s);
      indexOf[s] = i;
    }
    double change[30][30] = {};
    int m;
    scanf("%d", &m);
    while (m--) {
      char a[99], b[99];
      double arbitrage;
      scanf("%s%lf%s", a, &arbitrage, b);
      change[indexOf[a]][indexOf[b]] = arbitrage;
    }
    bool find = false;
    for (int k = 0; k < n && !find; k++) {
      for (int a = 0; a < n && !find; a++) {
        for (int b = 0; b < n; b++) {
          change[a][b] = max(change[a][b], change[a][k] * change[k][b]);
        }
        if (change[a][a] > 1.0) {
          find = true;
        }
      }
    }
    printf("Case %d: %s\n", C++, find ? "Yes" : "No");
  }
  return 0;
}

沒有留言:

張貼留言