题目描述
难度分:$1800$
输入$n(2 \leq n \leq 5000)$,$m(1 \leq m \leq 5000)$,$maxT(1 \leq maxT \leq 10^9)$。
然后输入$m$条边,每条边输入$v$,$w$,$t(1 \leq t \leq 10^9)$,表示有一条边权为$t$的有向边连接$v$和 $w$。节点编号从$1$开始。
保证输入的是一个有向无环图,并且没有重边。
求出从$1$到$n$的一条路径,要求路径长度(边权之和)不超过$maxT$,在满足该条件的前提下,路径上的节点数最多。
输出两行,第一行是路径上的节点个数,第二行按顺序输出路径上的节点编号(第一个数必须是$1$,最后一个数必须是 $n$)。
保证至少有一条满足要求的路径。
输入样例$1$
4 3 13
1 2 5
2 3 7
2 4 8
输出样例$1$
3
1 2 4
输入样例$2$
6 6 7
1 2 2
1 3 3
3 6 3
2 4 2
4 6 2
6 5 1
输出样例$2$
4
1 2 4 6
输入样例$3$
5 5 6
1 3 3
3 5 3
1 2 2
2 4 3
4 5 2
输出样例$3$
3
1 3 5
算法
动态规划
由于本题的图是一个有向无环图,因此直接从节点$1$开始BFS
,在图上进行动态规划就可以。
状态定义
$f[i][j]$表示从节点$1$开始,经过$j$个节点(包括起点和终点)能到节点$i$的最小路径边权和。
状态转移
遍历当前节点$u$的出边,假设下一个节点为$v$,状态转移方程为
$f[v][j+1]=\min_{u_i}f[u_i][j]+w$
其中$u_i$是$v$的前驱节点,在状态转移的过程中记录$v$的状态是从哪个前驱节点$u$转移过来的,便于最后从$n$节点开始反推出具体方案。即$pre[v][j]=u$,表示$f[v][j]$是从$f[u][j-1]$转移过来的。
遍历$f[n]$,只要$f[n][i] \leq maxT$,就说明从$1$到$n$的路径节点数可以达到$i$,维护$i$的最大值就可以得到第一问的答案。再从节点$n$开始利用$pre$数组倒推出具体方案存入$ans$数组,然后逆序输出就可以了。
复杂度分析
时间复杂度
DP
的过程本质上是对图进行了一次遍历,时间复杂度为$O(n+m)$;计算最大节点数的过程由于一共只有$n$个节点,且图为有向无环图,所以时间复杂度是$O(n)$;最后还原方案从$n$开始,利用$pre$数组进行倒推,最多倒推$n$步,时间复杂度也是$O(n)$。因此算法整体的时间复杂度为$O(n+m)$。
空间复杂度
空间瓶颈在于DP
数组$f$和前驱节点数组$pre$,它们的规模都是$O(n^2)$,这也是整个算法的额外空间复杂度。
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 5001, INF = 1e9;
vector<PII> graph[N];
int n, m, maxT, pre[N][N], f[N][N];
void solve() {
// 从起点开始DP
memset(f, 0x3f, sizeof f);
memset(pre, 0, sizeof(pre));
f[1][1] = 0;
queue<PII> q;
q.push({1, 1});
while(!q.empty()) {
auto&t = q.front();
q.pop();
int u = t.first, cnt = t.second;
for(auto&pir: graph[u]) {
int v = pir.first, w = pir.second;
if((long long)f[u][cnt] + w < f[v][cnt + 1]) {
f[v][cnt + 1] = f[u][cnt] + w;
pre[v][cnt + 1] = u;
q.push({v, cnt + 1});
}
}
}
int step;
for(int i = 1; i <= n; i++) {
if(f[n][i] <= maxT) {
step = i;
}
}
printf("%d\n", step);
// 反推状态转移
vector<int> ans;
int cur = n;
while(step > 0) {
ans.push_back(cur);
cur = pre[cur][step];
step--;
}
int sz = ans.size();
for(int i = sz - 1; ~i; i--) {
printf("%d ", ans[i]);
}
puts("");
}
int main() {
scanf("%d%d%d", &n, &m, &maxT);
for(int i = 1; i <= n; i++) {
graph[i].clear();
}
for(int i = 0; i < m; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
graph[u].push_back({v, w});
}
solve();
return 0;
}