2013年8月15日

UVa 10099 - The Tourist Guide

#include <cstdio>

int min(int a, int b) {
  return a < b ? a : b;
}

int main() {
  int N, R, C = 1;
  while (scanf("%d%d", &N, &R) && N) {
    int max[101][101] = {};
    while (R--) {
      int C1, C2, P;
      scanf("%d%d%d", &C1, &C2, &P);
      max[C1][C2] = max[C2][C1] = P;
    }
    for (int k = 1; k <= N; k++) {
      for (int a = 1; a <= N; a++) {
        for (int b = 1; b <= N; b++) {
          if (max[a][k] && max[k][b] && max[a][b] < min(max[a][k], max[k][b])) {
            max[a][b] = min(max[a][k], max[k][b]);
          }
        }
      }
    }
    int S, D, T;
    scanf("%d%d%d", &S, &D, &T);
    max[S][D]--;
    printf("Scenario #%d\nMinimum Number of Trips = %d\n\n", C++, T / max[S][D] + ((T % max[S][D]) > 0));
  }
  return 0;
}

沒有留言:

張貼留言