2013年8月18日

UVa 11015 - 05-2 Rendezvous

#include <cstdio>
#include <cstdlib>

int main() {
  int n, m, C = 1;
  while (scanf("%d%d", &n, &m) && n) {
    char name[99][99];
    int dis[99][99];
    for (int a = 1; a <= n; a++) {
      for (int b = 1; b <= n; b++) {
        dis[a][b] = (a == b ? 0 : 1e9);
      }
    }
    for (int a = 1; a <= n; a++) {
      scanf("%s", name[a]);
    }
    while (m--) {
      int a, b, d;
      scanf("%d%d%d", &a, &b, &d);
      dis[a][b] = dis[b][a] = d;
    }
    for (int k = 1; k <= n; k++) {
      for (int a = 1; a <= n; a++) {
        for (int b = 1; b <= n; b++) {
          if (dis[a][k] + dis[k][b] < dis[a][b]) {
            dis[a][b] = dis[a][k] + dis[k][b];
          }
        }
      }
    }
    int ans = 0, min = 1e9;
    for (int b = 1; b <= n; b++) {
      int sum = 0;
      for (int a = 1; a <= n; a++) {
        sum += dis[a][b];
      }
      if (sum < min) {
        min = sum;
        ans = b;
      }
    }
    printf("Case #%d : %s\n", C++, name[ans]);
  }
  return 0;
}

沒有留言:

張貼留言