2013年8月10日

UVa 10702 - Travelling Salesman

#include <stdio.h>

int main() {
  int C, S, E, T;
  while (scanf("%d%d%d%d", &C, &S, &E, &T) && C) {
    int i, j, earn[101][101] = {}, price[1001][101] = {};
    for (i = 1; i <= C; i++) {
      for (j = 1; j <= C; j++) {
        scanf("%d", &earn[i][j]);
        if (i == S) {
          price[1][j] = earn[i][j];
        }
      }
    }
    int isEnd[101] = {};
    for (i = 0; i < E; i++) {
      scanf("%d", &j);
      isEnd[j] = 1;
    }
    int max = 0, t;
    for (t = 2; t <= T; t++) {
      for (i = 1; i <= C; i++) {
        for (j = 1; j <= C; j++) {
          if (price[t - 1][i] + earn[i][j] > price[t][j]) {
            price[t][j] = price[t - 1][i] + earn[i][j];
            if (isEnd[j] && price[t][j] > max) {
              max = price[t][j];
            }
          }
        }
      }
    }
    printf("%d\n", max);
  }
  return 0;
}

沒有留言:

張貼留言