题目描述

难度分:$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;
}