Codeforces #374 721C. Journey
传送门：http://codeforces.com/problemset/problem/721/C
题目翻译
一个没有环N个点M条边的图，经过每条边需要时间。求在T的时间内，如何从1走到N，并且经过最多的点。输出方案。
题解
首先没有环，所以我们不用担心一条路径从自己有更新了自己。所以我们可以直接用DP推。 F[i][j] 已经经过了i个点，当前在点j的最小时间。 用M条边，更新F[i][x] -> F[i+1][x]
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
//while(true) RP++; #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define LL long long using namespace std; const int Maxn = 5000; int n, m, T; struct Edge { int u,v,t; }; Edge e[Maxn + 5]; int DP[Maxn + 5][Maxn + 5]; int pre[Maxn + 5][Maxn + 5]; void dfs(int pos,int x,bool isEnd){ if (pos == 0) return ; dfs(pos - 1,pre[pos][x], false); if (isEnd) printf("%d\n",x); else printf("%d ", x); } int main() { scanf("%d%d%d", &n, &m, &T); for (int i = 1; i <= m; i++) scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].t); memset(DP, -1, sizeof(DP)); DP[1][1] = 0; int Ans = 0; for (int i = 2; i <= n; i++) { for (int j = 1; j <= m; j++) { if (DP[i - 1][e[j].u] != -1) { if (DP[i - 1][e[j].u] + e[j].t <= T) { if (DP[i][e[j].v] == -1 || DP[i][e[j].v] > DP[i - 1][e[j].u] + e[j].t) { DP[i][e[j].v] = DP[i - 1][e[j].u] + e[j].t; pre[i][e[j].v] = e[j].u; if (e[j].v == n && Ans < i) Ans = i; } } } } } printf("%d\n",Ans); dfs(Ans,n,true); return 0; } |
原文链接：Codeforces #374 721C. Journey
WNJXYKの博客 版权所有，转载请注明出处。
还没有任何评论，你来说两句吧!