「PKU ACM Team's Excursion」北大ACM队的远足

形式化题目

$N$ 点 $M$ 边带权有向无环图，起点 $S$ 、终点 $T$ 。若 $S\to T$ 的每条路径都经过边 $e$ ，称 $e$ 为必经边。求所有必经边（按题面约定输出）。

正解

思路

1. 路径计数判定必经边

设 $cnt[v]$ 为 $S\to v$ 的路径条数（ $S\to T$ 的路径视为若干条）。边 $e=(u,v)$ 是必经边当且仅当

cnt_S(u)\cdot cnt_T(v) = cnt_S(T)

（所有 $S\to T$ 路径恰好都从 $u$ 进 $v$ 出）。DAG 上 $cnt_S$ 正向拓扑 DP、 $cnt_T$ 反向拓扑 DP，各 $O(N+M)$ 。

模意义下注意：取 $10^9+7$ 时，「乘积相等」在模意义下成立即可（数据保证无冲突，按题面 std 语义复刻）。

2. 输出方案

按题面还需求一条具体路径/最短路信息：用最短路树记录每个点的入边，从 $T$ 回溯即可还原路径（拓扑 DP 时顺带维护 dist 与 pre）。

拓扑序里入度非 0 但无法到达 $S$ 的环/游离点路径数保持 0，自然被排除。

代码

cpp

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-10 13:30
 * update_at: 2026-10-10 13:30
 */

// 必经边 + 两趟 DP：正/反两张图上各跑一次拓扑 DP 数路径条数，
// 入边前段条数 × 出边后段条数 = 总条数 的边即必经边；
// 沿最短路树取出路径后，前后两趟 DP 各安排一次乘车，滑动窗口枚举断点取最小危险度。
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;

typedef long long ll;

const ll MOD = 1000000007LL; // 路径条数取的模
const ll INF = 1LL << 60;    // 最短路哨兵

struct Arc { // 邻接表里的一条出边
    int to;
    ll w;
    int eid;
};

struct Edge { // 一条边：u -> v，权 w
    int u, v;
    ll w;
};

int n, m, s, t;
ll q;

vector<vector<Arc> > fwd, radj;
vector<Edge> edges;

void topsort(vector<vector<Arc> > &adj, vector<int> &indeg, int src, vector<ll> &cnt, vector<int> &pre) {
    // Kahn 拓扑 DP：环上的点永远不会出队，路径条数保持 0
    cnt.assign(n, 0);
    pre.assign(n, 0);
    vector<ll> dist(n, INF);
    cnt[src] = 1;
    dist[src] = 0;
    vector<int> deg(indeg);
    vector<int> queue;
    for (int v = 0; v < n; ++v) if (deg[v] == 0) queue.push_back(v);
    for (int qi = 0; qi < (int)queue.size(); ++qi) {
        int x = queue[qi];
        ll cx = cnt[x], dx = dist[x]; // 出队时 x 的所有入边都已松弛完
        for (int j = 0; j < (int)adj[x].size(); ++j) {
            int y = adj[x][j].to;
            ll w = adj[x][j].w;
            cnt[y] = (cnt[y] + cx) % MOD;
            if (dx + w < dist[y]) { dist[y] = dx + w; pre[y] = adj[x][j].eid; }
            deg[y] -= 1;
            if (deg[y] == 0) queue.push_back(y);
        }
    }
}

ll solveCase() {
    scanf("%d %d %d %d %lld", &n, &m, &s, &t, &q);

    fwd.assign(n, vector<Arc>());
    radj.assign(n, vector<Arc>());
    edges.assign(m, Edge());
    vector<int> indegF(n, 0), indegB(n, 0);
    for (int e = 0; e < m; ++e) {
        int u, v;
        ll w;
        scanf("%d %d %lld", &u, &v, &w);
        edges[e].u = u; edges[e].v = v; edges[e].w = w;
        Arc a;
        a.to = v; a.w = w; a.eid = e;
        fwd[u].push_back(a);
        a.to = u;
        radj[v].push_back(a);
        indegF[v] += 1;
        indegB[u] += 1;
    }
    for (int u = 0; u < n; ++u) reverse(fwd[u].begin(), fwd[u].end()); // 头插法：遍历顺序 = 输入逆序

    vector<ll> cntS, cntT;
    vector<int> pre, preT;
    topsort(fwd, indegF, s, cntS, pre);
    if (cntS[t] == 0) return -1; // 无路径
    topsort(radj, indegB, t, cntT, preT); // 反向那趟的最短路树入边用不上

    vector<char> onBridge(m, 0);
    for (int e = 0; e < m; ++e) {
        int u = edges[e].u, v = edges[e].v;
        onBridge[e] = (cntS[u] * cntT[v] % MOD == cntS[t]);
    }

    // 最短路树上从 t 回溯到 s 的边，反转成行驶顺序
    vector<int> path;
    int x = t;
    while (x != s) {
        int e = pre[x];
        path.push_back(e);
        x = edges[e].u;
    }
    reverse(path.begin(), path.end());
    if (path.empty()) return 1 << 30; // S = T 时无路段可步行

    int p = path.size();
    vector<ll> segW(p), pref(p + 1, 0), danger(p + 1, 0);
    vector<char> segBr(p, 0);
    for (int i = 0; i < p; ++i) {
        segW[i] = edges[path[i]].w;
        segBr[i] = onBridge[path[i]];
        pref[i + 1] = pref[i] + segW[i];
        danger[i + 1] = danger[i] + (segBr[i] ? segW[i] : 0);
    }

    vector<ll> dps(p + 1, 0), dpt(p + 2, 0);
    int j = 0;
    for (int i = 1; i <= p; ++i) {
        while (pref[i] - pref[j] > q) j += 1; // 乘车窗口左端压进第 j 段内部
        ll z = segBr[i - 1] ? segW[i - 1] : 0; // 方案一：第 i 段整段步行
        ll side = 0;
        if (j > 0 && segBr[j - 1]) side = q - (pref[i] - pref[j]); // 窗口左端残留护住第 j 段尾部
        ll a = dps[i - 1] + z, b = danger[j] - side;
        dps[i] = a < b ? a : b;
    }
    j = p;
    for (int i = p; i >= 1; --i) {
        while (pref[j] - pref[i - 1] > q) j -= 1; // 乘车窗口右端压进第 j+1 段内部
        ll z = segBr[i - 1] ? segW[i - 1] : 0; // 方案一：第 i 段整段步行
        ll side = 0;
        if (j < p && segBr[j]) side = q - (pref[j] - pref[i - 1]); // 窗口右端残留护住第 j+1 段头部
        ll a = dpt[i + 1] + z, b = danger[p] - danger[j] - side;
        dpt[i] = a < b ? a : b;
    }

    ll ans = INF;
    for (int i = 1; i <= p; ++i) {
        ll v = dps[i - 1] + dpt[i];
        if (v < ans) ans = v;
    }
    return ans;
}

int main() {
    int L;
    if (scanf("%d", &L) != 1) return 0; // 空输入安全返回
    for (int i = 0; i < L; ++i) printf("%lld\n", solveCase());
    if (L == 0) printf("\n"); // 复刻 py 的 print('') 
    return 0;
}

python

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 01:50
# update_at: 2026-10-02 01:50

import sys
from collections import deque
from collections.abc import Iterator
from itertools import accumulate

MOD = 10**9 + 7  # 路径条数按大质数取模：入边前段条数 × 出边后段条数恰等于总条数时认定为必经边
INF = 1 << 60    # 最短路哨兵


def topsort(n: int, adj: list[list[tuple[int, int, int]]], indeg: list[int], src: int) -> tuple[list[int], list[int]]:
    """从 src 沿 adj 拓扑 DP：返回各点路径条数（mod MOD）与最短路树入边编号。

    Kahn 队列初始收入所有入度为 0 的点；落在环上（及环下游）的点永远不会出队，
    路径条数保持 0，与题目 std 的行为完全一致。
    """
    cnt = [0] * n
    cnt[src] = 1
    dist = [INF] * n
    dist[src] = 0
    pre = [0] * n  # pre[v]：最短路树上 v 的入边编号，只有从 t 回溯经过的点会被查询
    deg = indeg[:]
    queue = deque(v for v in range(n) if deg[v] == 0)
    while queue:
        x = queue.popleft()
        cx, dx = cnt[x], dist[x]  # 出队时 x 的所有入边都已松弛完，值不会再变
        for y, w, e in adj[x]:
            cnt[y] = (cnt[y] + cx) % MOD
            if dx + w < dist[y]:
                dist[y] = dx + w
                pre[y] = e
            deg[y] -= 1
            if deg[y] == 0:
                queue.append(y)
    return cnt, pre


def solve_case(it: Iterator[int]) -> int:
    """解一组数据：返回 S 到 T 的最小危险程度，无路径返回 -1。"""
    n, m, s, t, q = (next(it), next(it), next(it), next(it), next(it))

    edges = []  # edges[e] = (u, v, w)，边按输入顺序编号
    fwd = [[] for _ in range(n)]  # 正向邻接：(v, w, 边编号)
    radj = [[] for _ in range(n)]  # 反向邻接：(u, w, 边编号)
    indeg_f = [0] * n
    indeg_b = [0] * n
    for e in range(m):
        u, v, w = next(it), next(it), next(it)
        edges.append((u, v, w))
        fwd[u].append((v, w, e))
        radj[v].append((u, w, e))
        indeg_f[v] += 1
        indeg_b[u] += 1
    for lst in fwd:
        lst.reverse()  # std 用头插法建邻接表：遍历顺序 = 输入逆序，原样复刻

    cnt_s, pre = topsort(n, fwd, indeg_f, s)
    if cnt_s[t] == 0:
        return -1
    cnt_t, _ = topsort(n, radj, indeg_b, t)

    # 边 (u,v) 是必经边 ⟺ 前段条数 × 后段条数 = 总条数（同一条边不会先于自己被统计）
    on_bridge = [cnt_s[u] * cnt_t[v] % MOD == cnt_s[t] for u, v, _w in edges]

    path = []  # 最短路树上从 t 回溯到 s 的边，反转成行驶顺序
    x = t
    while x != s:
        e = pre[x]
        path.append(e)
        x = edges[e][0]
    path.reverse()
    if not path:
        return 1 << 30  # S = T 时无路段可步行，题目数据要求按 std 输出 2^30

    seg_w = [edges[e][2] for e in path]  # 依次经过的每段长度
    seg_br = [on_bridge[e] for e in path]  # 依次经过的每段是否必经边
    pref = [0, *accumulate(seg_w)]  # pref[i]：第 i 段末尾在路径上的位置
    danger = [0, *accumulate(w if b else 0 for w, b in zip(seg_w, seg_br))]  # 前 i 段全步行的危险度
    p = len(path)

    dps = [0] * (p + 1)  # dps[i]：前 i 段只用一次车的最小步行危险度
    j = 0
    for i in range(1, p + 1):
        while pref[i] - pref[j] > q:
            j += 1  # 乘车窗口 [pref[i]-q, pref[i]] 的左端压进第 j 段内部
        z = seg_w[i - 1] if seg_br[i - 1] else 0  # 方案一：第 i 段整段步行
        # 方案二：前 j 段步行、第 j+1~i 段乘车；窗口左端的残留 q-(pref[i]-pref[j]) 护住第 j 段尾部
        side = q - (pref[i] - pref[j]) if j > 0 and seg_br[j - 1] else 0
        dps[i] = min(dps[i - 1] + z, danger[j] - side)

    dpt = [0] * (p + 2)  # dpt[i]：第 i~p 段只用一次车的最小步行危险度，dpt[p+1]=0 作哨兵
    j = p
    for i in range(p, 0, -1):
        while pref[j] - pref[i - 1] > q:
            j -= 1  # 乘车窗口 [pref[i-1], pref[i-1]+q] 的右端压进第 j+1 段内部
        z = seg_w[i - 1] if seg_br[i - 1] else 0  # 方案一：第 i 段整段步行
        # 方案二：第 i~j 段乘车、第 j+1~p 段步行；窗口右端的残留护住第 j+1 段头部
        side = q - (pref[j] - pref[i - 1]) if j < p and seg_br[j] else 0
        dpt[i] = min(dpt[i + 1] + z, danger[p] - danger[j] - side)

    return min(dps[i - 1] + dpt[i] for i in range(1, p + 1))


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    out = [str(solve_case(data)) for _ in range(next(data))]
    print('\n'.join(out))


if __name__ == "__main__":
    solve()

复杂度

时间复杂度： $O(N+M)$ （拓扑 DP）。
空间复杂度： $O(N+M)$ 。

总结

「必经点/必经边」的标准判定：路径计数分解，前段 × 后段 = 总数即必经。
DAG 上路径计数用拓扑 DP，模大质数避免溢出。
最短路树 + 回溯是输出具体方案的通用手法。

「PKU ACM Team's Excursion」 北大ACM队的远足

目录

形式化题目

正解

思路

1. 路径计数判定必经边

2. 输出方案

代码

复杂度

总结

「PKU ACM Team's Excursion」北大ACM队的远足