2013年8月27日

UVa 11463 - Commandos

#include <cstdio>

int main() {
  int T, C = 1;
  scanf("%d", &T);
  while (T--) {
    int N, R;
    scanf("%d%d", &N, &R);
    int dis[100][100];
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < N; j++) {
        dis[i][j] = (i == j) ? 0 : 1e7;
      }
    }
    while (R--) {
      int u, v;
      scanf("%d%d", &u, &v);
      dis[u][v] = dis[v][u] = 1;
    }
    for (int k = 0; k < N; k++) {
      for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
          if (dis[i][j] > dis[i][k] + dis[k][j]) {
            dis[i][j] = dis[i][k] + dis[k][j];
          }
        }
      }
    }
    int s, d;
    scanf("%d%d", &s, &d);
    int ans = 0;
    for (int i = 0; i < N; i++) {
      if (dis[s][i] + dis[i][d] > ans) {
        ans = dis[s][i] + dis[i][d];
      }
    }
    printf("Case %d: %d\n", C++, ans);
  }
  return 0;
}

沒有留言:

張貼留言