2013年8月16日

UVa 10048 - Audiophobia

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

int main() {
  int C, S, Q, Case = 1;
  bool first = true;
  while (scanf("%d%d%d", &C, &S, &Q) && C) {
    if (!first) {
      puts("");
    }
    first = false;
    int intensity[101][101];
    for (int a = 1; a <= C; a++) {
      for (int b = 1; b <= C; b++) {
        intensity[a][b] = 1e9;
      }
    }
    while (S--) {
      int a, b, i;
      scanf("%d%d%d", &a, &b, &i);
      intensity[a][b] = intensity[b][a] = i;
    }
    for (int k = 1; k <= C; k++) {
      for (int a = 1; a <= C; a++) {
        for (int b = 1; b <= C; b++) {
          intensity[a][b] = min(intensity[a][b], max(intensity[a][k], intensity[k][b]));
        }
      }
    }
    printf("Case #%d\n", Case++);
    while (Q--) {
      int a, b;
      scanf("%d%d", &a, &b);
      if (intensity[a][b] != 1e9) {
        printf("%d\n", intensity[a][b]);
      } else {
        puts("no path");
      }
    }
  }
  return 0;
}

沒有留言:

張貼留言