2013年8月16日

UVa 544 - Heavy Cargo

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

int main() {
  int n, r, C = 1;
  while (scanf("%d%d", &n, &r) && n) {
    map<string, int> indexOf;
    int load[200][200] = {}, citiesNum = 0;
    while (r--) {
      char c1[99], c2[99];
      int a, b, l;
      scanf("%s%s%d", c1, c2, &l);
      if (indexOf.count(c1)) {
        a = indexOf[c1];
      } else {
        a = citiesNum;
        indexOf[c1] = citiesNum++;
      }
      if (indexOf.count(c2)) {
        b = indexOf[c2];
      } else {
        b = citiesNum;
        indexOf[c2] = citiesNum++;
      }
      load[a][b] = load[b][a] = l;
    }
    for (int k = 0; k < citiesNum; k++) {
      for (int a = 0; a < citiesNum; a++) {
        for (int b = 0; b < citiesNum; b++) {
          if (load[a][k] && load[k][b]) {
            load[a][b] = max(load[a][b], min(load[a][k], load[k][b]));
          }
        }
      }
    }
    char c1[99], c2[99];
    scanf("%s%s", c1, c2);
    printf("Scenario #%d\n", C++);
    printf("%d tons\n\n", load[indexOf[c1]][indexOf[c2]]);
  }
  return 0;
}

沒有留言:

張貼留言