给出一个n个点m条边的有向无环图。
问从1到n，在距离不超过k的情况下最多经过多少点，并输出一个方案。

SPFA + dp
dp[i][j]表示第i个点经过j条边的最小值

然后二维标记，直接跑SPFA

#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9 + 9;
const int maxn = 1e5 + 5;
int head[maxn][2], tot[2];
const int maxm = 5050;
int dp[maxm][maxm];
bool vis[maxm][maxm];
int pre[maxm][maxm];
struct Edge {
    int u, v, w, next;
}edge[maxn][2];
int n, m, k;
struct node {
    int u, c;
    node(int uu, int cc) {
        u = uu; c = cc;
    }
};
void init() {
    memset(head, -1, sizeof(head)); tot[0] = 1; tot[1] = 1;
}
void add(int u, int v, int w, int i) {
    edge[tot[i]++][i].u = u; edge[tot[i]][i].v = v; 
    edge[tot[i]][i].w = w; edge[tot[i]][i].next = head[u][i];
    head[u][i] = tot[i];
}

void spfa(int s) {
    queue<node> que;
    que.push(node(1, 0));
    vis[1][0] = 1; dp[1][0] = 0;
    while (!que.empty()) {
        node t = que.front(); que.pop();
        int u = t.u;
        vis[u][t.c] = 0;
        for (int i = head[u][0]; i != -1; i = edge[i][0].next) {
            int to = edge[i][0].v;
            if (dp[t.u][t.c] + edge[i][0].w <= k && dp[to][t.c + 1] > dp[t.u][t.c] + edge[i][0].w) {
                dp[to][t.c + 1] = dp[t.u][t.c] + edge[i][0].w;
                pre[to][t.c + 1] = u;
                if (!vis[to][t.c + 1]) {
                    que.push(node(to, t.c + 1));
                    vis[to][t.c + 1] = 1;
                }
            }
        }
    }
}
int ans[maxn], t;
void dfs(int u, int c) {
    if (pre[u][c] == 0) {
        if (u == 1) {
            cout << u << " ";
        }
        return ;
    }
    dfs(pre[u][c], c - 1);
    cout << u << " ";
}
int main() {

    int u, v, w; 
    init();
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            dp[i][j] = inf;
        }
    }
    for (int i = 1; i <= m; i++) {
        scanf("%d%d%d", &u, &v, &w); 
        add(u, v, w, 0); add(v, u, w, 1);
    }
    spfa(1);
    int s = 0;
    for (int i = n-1; i >= 1; i--) {
        if (dp[n][i] <= k) {
            s = i; break;
        }
    }
    cout << s + 1 << endl;
    dfs(n, s);
    return 0;
}