2013年8月18日

UVa 10171 - Meeting Prof. Miguel...

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

int main() {
  int n;
  while (scanf("%d", &n) && n) {
    int y[26][26], o[26][26];
    for (int a = 0; a < 26; a++) {
      for (int b = 0; b < 26; b++) {
        y[a][b] = o[a][b] = 1e7;
      }
    }
    for (int a = 0; a < 26; a++) {
      y[a][a] = o[a][a] = 0;
    }
    for (int i = 0; i < n; i++) {
      char age[9], dir[9], X[9], Y[9];
      int d;
      scanf("%s%s%s%s%d", age, dir, X, Y, &d);
      int a = *X - 'A', b = *Y - 'A';
      if (*dir == 'B') {
        if (*age == 'Y') {
          y[a][b] = min(y[a][b], d);
          y[b][a] = min(y[b][a], d);
        } else {
          o[a][b] = min(o[a][b], d);
          o[b][a] = min(o[b][a], d);
        }
      } else {
        if (*age == 'Y') {
          y[a][b] = min(y[a][b], d);
        } else {
          o[a][b] = min(o[a][b], d);
        }
      }
    }
    for (int k = 0; k < 26; k++) {
      for (int a = 0; a < 26; a++) {
        for (int b = 0; b < 26; b++) {
          y[a][b] = min(y[a][b], y[a][k] + y[k][b]);
          o[a][b] = min(o[a][b], o[a][k] + o[k][b]);
        }
      }
    }
    char X[9], Y[9];
    scanf("%s%s", X, Y);
    int a = *X - 'A', b = *Y - 'A', ans = 1e7;
    for (int meet = 0; meet < 26; meet++) {
      ans = min(ans, y[a][meet] + o[b][meet]);
    }
    if (ans == 1e7) {
      puts("You will never meet.");
    } else {
      printf("%d", ans);
      for (int meet = 0; meet < 26; meet++) {
        if (y[a][meet] + o[b][meet] == ans) {
          printf(" %c", meet + 'A');
        }
      }
      puts("");
    }
  }
  return 0;
}

沒有留言:

張貼留言