#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; }
Hello, I am a CS student from Taiwan.
I am learing English and Programming.
I'll save source code of some problems or small programs without comments in this blog.
I would recommend you not to read solution from others before you solved the problem.
(這邊專門存放沒有任何註解的小程式/OJ題目程式碼)
2013年8月10日
UVa 10702 - Travelling Salesman
訂閱:
張貼留言 (Atom)
沒有留言:
張貼留言