2013年8月18日

UVa 423 - MPI Maelstrom

#include <cstdio>
#include <cstdlib>

int main() {
  int n;
  while (scanf("%d", &n) == 1) {
    int dis[101][101] = {};
    for (int a = 2; a <= n; a++) {
      for (int b = 1; b < a; b++) {
        char s[99];
        scanf("%s", s);
        dis[a][b] = dis[b][a] = (s[0] == 'x' ? 1e9 : atoi(s));
      }
    }
    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;
    for (int b = 1; b <= n; b++) {
      ans = dis[1][b] > ans ? dis[1][b] : ans;
    }
    printf("%d\n", ans);
  }
  return 0;
}

沒有留言:

張貼留言