const int MAXN = 110; int T, n, m, t, s, e, ee; int cost[MAXN], val[MAXN], dis[MAXN][MAXN]; int pt[MAXN], dp[MAXN][310]; bool cmp(int a, int b) { return val[a] < val[b]; } int main() { // freopen("in.txt", "r", stdin); int a, b, c; RI(T); FE(kase, 1, T) { scanf("%d%d%d%d%d", &n, &m, &t, &s, &e); s++; e++; cost[0] = val[0] = cost[n + 1] = val[n + 1] = 0; FE(i, 0, n + 1) { FF(j, 0, 310) dp[i][j] = -INF; pt[i] = i; } FE(i, 1, n) { FE(j, 1, n) dis[i][j] = INF; dis[i][i] = 0; } dp[0][0] = 0; FE(i, 1, n) RI(cost[i]); FE(i, 1, n) RI(val[i]); REP(i, m) { RIII(a, b, c); a++; b++; dis[a][b] = min(dis[a][b], c); dis[b][a] = min(dis[b][a], c); } FE(k, 1, n) FE(i, 1, n) FE(j, 1, n) dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]); FE(i, 1, n) { dis[0][i] = dis[s][i]; dis[i][n + 1] = dis[i][e]; } dis[0][n + 1] = dis[s][e]; sort(pt + 1, pt + n + 1, cmp); FE(i, 0, n) FE(j, i + 1, n + 1) { int a = pt[i], b = pt[j]; if (i > 0 && j <= n && val[a] == val[b]) continue; FE(k, 0, t) { if (k + dis[a][b] + cost[b] > t) break; int& next = dp[b][k + dis[a][b] + cost[b]]; next = max(next, dp[a][k] + val[b]); } } int ans = 0; FE(i, 0, t) { ans = max(ans, dp[n + 1][i]); } printf("Case #%d:\n%d\n", kase, ans); } return 0; }
2013 ACM-ICPC长沙赛区全国邀请赛——Travel in time,布布扣,bubuko.com
2013 ACM-ICPC长沙赛区全国邀请赛——Travel in time
原文:http://blog.csdn.net/wty__/article/details/25293235