营救 - 题目列表

形式化题目

给定无向连通图 $G=(V,E)$ 、起点 $s$ 与终点 $t$ 。对一条路径 $P$ ，定义它的代价为路径上最大的边权。求所有 $s \to t$ 路径中代价的最小值：

\min_{P:\, s \to t} \ \max_{e \in P} w(e)

这个量叫 瓶颈路（minimax path）。注意它与最短路不同：最短路最小化边权之和，瓶颈路最小化边权最大值。样例里 $1 \to 2 \to 3$ 比直连 $1 \to 3$ 更长，但最大边更小，所以更优。

解法总览

这题有一个统一的本质——它是一个「阈值连通性」问题。定义

\text{ans} = \min\{L : \text{只保留 } w \le L \text{ 的边时，} s \text{ 与 } t \text{ 连通}\}

任何一条 $s\to t$ 路径的最大边 $\le L$ ，等价于该路径只用到了 $w \le L$ 的边，也就等价于 $s,t$ 在阈值 $L$ 下连通。所以下面这些解法只是「如何求出这个最小阈值」的不同实现：

解法	核心手段	复杂度
一、Kruskal + 并查集	按边权升序加边，s 与 t 首次连通时那条边的权即答案	$O(m \log m)$
二、瓶颈 Dijkstra	把最短路的「累加」换成「取 max」	$O(m \log n)$
三、二分答案 + BFS	二分阈值 $L$ ，每次用 BFS 判连通性	$O((n+m)\log W)$
四、二分答案 + 并查集	同样二分阈值，check 里用并查集合并 $≤ L$ 的边	$O(m\log W)$
五、枚举所有简单路径	按定义直算	指数级，仅作暴力对拍

正式主解是解法一 main.cpp / main.py，因为它最直接地体现了「阈值」这个本质。

解法五 brute.cpp 完全按定义实现，与其余四种不共享任何代码，用来独立验证。

解法一：Kruskal + 并查集

思路

按拥挤度从小到大加边，用并查集维护连通块。

为什么「 $s$ 与 $t$ 首次连通时那条边的权」就是答案？

Kruskal 处理完所有权 $\le L$ 的边之后，并查集的连通块恰好等于「只走权 $\le L$ 的边时图的分量」。这不是巧合，而是并查集的语义与阈值图的定义对齐了：

s,t \text{ 在只走 } w \le L \text{ 的边时连通} \iff \text{Kruskal 加完 } w \le L \text{ 的边后} s,t \text{ 同块}

而答案正是让 $s,t$ 连通的最小阈值。设它为 $W^*$ ：

权 $< W^*$ 的边全部加完后， $s,t$ 仍未连通 → 首次连通的边权 $\ge W^*$ ；
权 $\le W^*$ 的边加完后， $s,t$ 已连通 → 首次连通的边权 $\le W^*$ 。

两边夹住，首次连通时的边权恰为 $W^*$ 。

MST 不唯一会不会影响答案？ 不会。上面的论证只依赖边权的处理顺序，不依赖同权边之间的相对次序——相同权值的边无论谁先谁后，「处理完权 $\le L$ 时哪些点连通」这一事实都不变。所以任意一种 Kruskal 排序都对。

边界： $s = t$ 。 不用走任何路，拥挤度上界是 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/**
 * 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-21 16:59
 * update_at: 2026-10-21 17:30
 */
// 营救：求 s 到 t 的所有路径中，「路径上最大边权」的最小值，即瓶颈路。
// 本文件用 Kruskal + 并查集：按边权升序加边，边 (u,v) 一旦让 s 与 t 首次连通，
// 这条边的权值就是答案。
//
// 为什么对：Kruskal 处理完所有权 <= L 的边后，并查集的连通块恰好等于
// 「只走权 <= L 的边时图的分量」。于是
//   s、t 在只走权 <= L 的边时连通  <=>  Kruskal 加完权 <= L 的边后 s、t 已同块
// 而答案正是让 s、t 连通的最小阈值 L，所以「首次连通时那条边的权」就是 L。
// 这条性质只依赖边权的处理顺序，与同权边谁先谁后无关，所以任意一棵 MST 都对。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 10000 + 5;  // 区数上界 n <= 1e4
const int MAXM = 20000 + 5;  // 大道数上界 m <= 2e4

// 一条无向边：从 u 连到 v，拥挤度 w。点编号 1..n。
struct Edge {
    int u;  // 起点
    int v;  // 终点
    ll w;   // 拥挤度
};

int n, m, start_node, target_node;
Edge edges[MAXM];
int dsu_parent[MAXN];  // dsu_parent[x]：x 的父节点，x 是根时等于 x

// 边权小的排在前面，Kruskal 每次都先试当前最小的边。
bool cmp_edge(const Edge &a, const Edge &b) {
    return a.w < b.w;
}

// 找 x 所在集合的根，顺路把路径上的点直接挂到根上（路径压缩）。
int dsu_find(int x) {
    if (dsu_parent[x] == x) return x;
    dsu_parent[x] = dsu_find(dsu_parent[x]);
    return dsu_parent[x];
}

// 合并 a、b 所在的两个集合。
// 只靠路径压缩：单次操作摊还 O(log n)，本题 n <= 1e4 已经足够，
// 所以不再额外维护集合大小做按大小合并。
void dsu_merge(int a, int b) {
    dsu_parent[dsu_find(a)] = dsu_find(b);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> start_node >> target_node;
    for (int i = 0; i < m; i++) {
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
    }

    // s == t 时不用走任何路，拥挤度上界是 0，必须先特判：
    // 否则并查集一开始就「已连通」，会错误地输出第一条边的权值。
    if (start_node == target_node) {
        cout << 0 << '\n';
        return 0;
    }

    for (int i = 1; i <= n; i++) {
        dsu_parent[i] = i;
    }

    sort(edges, edges + m, cmp_edge);

    for (int i = 0; i < m; i++) {
        dsu_merge(edges[i].u, edges[i].v);
        // 加入这条边后 s 与 t 首次连通，它的权就是最小瓶颈值。
        if (dsu_find(start_node) == dsu_find(target_node)) {
            cout << edges[i].w << '\n';
            return 0;
        }
    }

    // 题面保证 s 一定能到达 t，走不到这里
    cout << 0 << '\n';
    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#!/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-21 16:59
# update_at: 2026-10-21 17:30
#
# main.py：营救。求 s 到 t 的所有路径中「路径上最大边权」的最小值，即瓶颈路。
# 本文件用 Kruskal + 并查集：按边权升序加边，边 (u,v) 一旦让 s 与 t 首次连通，
# 这条边的权值就是答案。
#
# 为什么对：Kruskal 处理完所有权 <= L 的边后，并查集的连通块恰好等于
# 「只走权 <= L 的边时图的分量」。于是
#   s、t 在只走权 <= L 的边时连通  <=>  Kruskal 加完权 <= L 的边后 s、t 已同块
# 而答案正是让 s、t 连通的最小阈值 L，所以「首次连通时那条边的权」就是 L。
# 这条性质只依赖边权的处理顺序，与同权边谁先谁后无关，所以任意一棵 MST 都对。

import sys

# 类型别名（Python 3.12+ 的 type 语句），相当于 C++ 的 using / typedef
type Edge = tuple[int, int, int]  # (起点 u, 终点 v, 拥挤度 w)


def find(parent: list[int], x: int) -> int:
    """找 x 所在集合的根，顺路把路径上的点挂到根上（迭代压缩，不受递归深度限制）。"""
    root = x
    while parent[root] != root:
        root = parent[root]
    while parent[x] != root:
        parent[x], x = root, parent[x]
    return root


def main() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)
    start_node, target_node = next(data), next(data)

    edges: list[Edge] = []
    for _ in range(m):
        u, v, w = next(data), next(data), next(data)
        edges.append((u, v, w))

    # s == t 时不用走任何路，拥挤度上界是 0，必须先特判：
    # 否则并查集一开始就「已连通」，会错误地输出第一条边的权值。
    if start_node == target_node:
        print(0)
        return

    parent = list(range(n + 1))  # parent[x]：x 的父节点，x 是根时等于 x

    # 边权小的先试；这就是 Kruskal 的顺序，也是「阈值从低到高放开边」的顺序
    for u, v, w in sorted(edges, key=lambda edge: edge[2]):
        # 只靠路径压缩：单次操作摊还 O(log n)，本题 n <= 1e4 已经足够，
        # 所以不再额外维护集合大小做按大小合并。
        parent[find(parent, u)] = find(parent, v)

        # 加入这条边后 s 与 t 首次连通，它的权就是最小瓶颈值
        if find(parent, start_node) == find(parent, target_node):
            print(w)
            return

    print(0)  # 题面保证 s 一定能到达 t，走不到这里


if __name__ == "__main__":
    main()

复杂度

排序 $O(m \log m)$ ，并查集 $O(m \alpha(n))$ ，合计 $O(m \log m)$ ；空间 $O(n + m)$ 。

解法二：瓶颈 Dijkstra

思路

普通最短路维护 $\text{dist}[v] = \min \sum w$ ，转移是 dist[u] + w。把「加法」换成「取 max」，就得到瓶颈路：

\text{dist}[v] = \min_{\text{路径}} \max_{\text{路径上的边}} w, \qquad \text{转移} = \max(\text{dist}[u],\ w)

算法结构一个字都不用改：仍然用堆取当前最小值、弹出即定型。为什么仍然正确？ 因为 $\max$ 对边权单调不减——非负边权下，从 u 出发的任何扩展都不会让瓶颈值变小，所以「堆弹出的当前最小值已定型」这个论证原封不动。

这是把 $(\min, +)$ 半环换成 $(\min, \max)$ 半环的典型例子。

代码

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/**
 * 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-21 16:59
 * update_at: 2026-10-21 17:30
 */
// 营救的第二种解法：瓶颈 Dijkstra。
// 把普通最短路 dist[v] = min(dist[u] + w) 里的「加法」换成「取 max」，
//   dist[v] = min over 路径 ( 路径上最大边权 )
// 转移写成 nd = max(dist[u], w)，其余结构与 Dijkstra 完全相同。
// 因为 max 对边权是单调不减的，非负边权下依然满足「弹出即定型」。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 10000 + 5;  // 区数上界 n <= 1e4
const ll INF = (1LL << 60);

struct Edge {
    int to;
    ll w;
};

int n, m, start_node, target_node;
vector<Edge> g[MAXN];  // g[u]：从 u 出发的全部边
ll dist_bottleneck[MAXN];  // dist_bottleneck[v]：s 到 v 的最小瓶颈值

void dijkstra() {
    for (int i = 1; i <= n; i++) dist_bottleneck[i] = INF;
    dist_bottleneck[start_node] = 0;

    // (当前瓶颈值, 点) 的小根堆
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> heap;
    heap.push({0, start_node});

    while (!heap.empty()) {
        ll current = heap.top().first;
        int u = heap.top().second;
        heap.pop();

        if (current > dist_bottleneck[u]) continue;  // 堆里的过期记录

        for (const Edge &e : g[u]) {
            // 唯一的改动：路径代价从「累加」变成「取已走部分的最大值」
            ll candidate = max(current, e.w);
            if (candidate < dist_bottleneck[e.to]) {
                dist_bottleneck[e.to] = candidate;
                heap.push({candidate, e.to});
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> start_node >> target_node;
    for (int i = 0; i < m; i++) {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        // 两个区之间可能有多条大道，都保留即可，Dijkstra 会取更优的那条
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }

    dijkstra();
    cout << dist_bottleneck[target_node] << '\n';
    return 0;
}

复杂度

$O(m \log n)$ ，空间 $O(n + m)$ 。常数比解法一略大。

解法三：二分答案 + BFS

思路

答案具有单调性：若限制上界为 $L$ 时 $s$ 能到 $t$ ，那么更大的上界也一定能到。于是二分 $L$ ：

猜一个 $L$ ，只走权 $\le L$ 的边，用 DFS/BFS 判断 $s$ 能否到 $t$ ；
能到就缩小上界，不能到就抬高下界。

$W \le 10^4$ ，二分约 14 轮。

这个解法的好处是不需要 MST 的任何知识，只用到「答案单调」这一个观察，最容易想到。

代码

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/**
 * 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-21 16:59
 * update_at: 2026-10-21 17:30
 */
// 营救的第三种解法：二分答案 + BFS。
// 答案具有单调性：若限制拥挤度上界为 L 时 s 能到 t，那么更大的 L 也一定能到。
// 于是二分 L，每次只走拥挤度 <= L 的边做一次 BFS/DFS 判连通。
// 复杂度 O((n+m) log W)，W 为最大拥挤度，本题 W <= 1e4，约 14 次搜索。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 10000 + 5;

struct Edge {
    int to;
    ll w;
};

int n, m, start_node, target_node;
vector<Edge> g[MAXN];
bool visited[MAXN];

// 只走拥挤度 <= limit 的边，判断 s 能否到达 t
bool reachable_within(ll limit) {
    fill(visited + 1, visited + n + 1, false);
    visited[start_node] = true;

    vector<int> st;
    st.push_back(start_node);
    while (!st.empty()) {
        int u = st.back();
        st.pop_back();
        if (u == target_node) return true;
        for (const Edge &e : g[u]) {
            if (e.w > limit) continue;  // 拥挤度超限的大道不能走
            if (visited[e.to]) continue;
            visited[e.to] = true;
            st.push_back(e.to);
        }
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> start_node >> target_node;
    ll max_w = 0;
    for (int i = 0; i < m; i++) {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
        max_w = max(max_w, w);
    }

    if (start_node == target_node) {
        cout << 0 << '\n';  // 不用走路，没有任何一段拥挤度
        return 0;
    }

    // 二分最小的可行上界：[low, high] 内一定存在答案
    ll low = 1, high = max_w;
    while (low < high) {
        ll mid = low + (high - low) / 2;
        if (reachable_within(mid)) {
            high = mid;  // mid 可行，答案可能是 mid 或更小
        } else {
            low = mid + 1;  // mid 不可行，答案一定更大
        }
    }

    cout << low << '\n';
    return 0;
}

复杂度

$O((n + m)\log W)$ ，空间 $O(n + m)$ 。

解法四：二分答案 + 并查集

思路

二分部分与解法三完全相同，只有 check 的实现不同：

	解法三（BFS）	解法四（并查集）
check 做什么	从 $s$ 出发 BFS，只走 $w \le L$ 的边	把 $w \le L$ 的边全合并，看 $s,t$ 是否同块
需要邻接表	需要	不需要，直接扫边表
单次 check	$O(n+m)$	$O(m\,\alpha(n))$

为什么并查集的 check 也对？ 因为在同一个阈值 $L$ 下，两者算的是同一件事：

\text{并查集合并完所有 } w\le L \text{ 的边后 } s,t \text{ 同块} \iff \text{只走 } w\le L \text{ 的边时 } s \text{ 能到 } t

并查集的一个集合就是「只走权 $\le L$ 的边时互相连通的点」，这就是 BFS 要判的东西，只是换了一种维护方式。

与解法一的关系值得注意：解法一（Kruskal）其实是把解法四的二分「内联」了——它把 $L$ 从低到高逐个试，而因为边已排序，试到某条边时阈值天然递增，于是「首次连通」就是最小可行 $L$ 。所以 main4.cpp 可以看成 main.cpp 的二分版本，main.cpp 可以看成 main4.cpp 的消去二分。

注意每轮 check 要重建并查集，把 parent[i] 重新赋成 i，否则上一轮的合并会残留。

代码

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/**
 * 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-21 16:59
 * update_at: 2026-10-21 18:20
 */
// 营救的第四种解法：二分答案 + 并查集。
// 与 main3.cpp（二分 + BFS）思路相同——答案具有单调性，二分拥挤度上界 L；
// 差别只在 check 的实现：这里不建邻接表、不做搜索，而是
//   把所有权 <= L 的边用并查集合并，最后判断 s 与 t 是否同块。
//
// 为什么这样也对：并查集合并完权 <= L 的全部边后，同一集合恰好是
// 「只走权 <= L 的边时互相连通的点」，于是「s 与 t 同块」等价于
// 「只走权 <= L 的边时 s 能到 t」，正是 BFS 要判的东西。
//
// 与 main3.cpp 的取舍：
//   BFS 版每次 check 要遍历邻接表 O(n+m)，并查集版每次 check 只扫一遍边表 O(m)
//   并且不用建邻接表；但并查集版每轮都要重新初始化 parent，常数略大。
//   两者同阶，都是 O(m log W)。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 10000 + 5;  // 区数上界 n <= 1e4
const int MAXM = 20000 + 5;  // 大道数上界 m <= 2e4

struct Edge {
    int u;  // 起点
    int v;  // 终点
    ll w;   // 拥挤度
};

int n, m, start_node, target_node;
Edge edges[MAXM];
int dsu_parent[MAXN];  // dsu_parent[x]：x 的父节点，x 是根时等于 x

// 找 x 所在集合的根，顺路把路径上的点直接挂到根上（路径压缩）。
int dsu_find(int x) {
    if (dsu_parent[x] == x) return x;
    dsu_parent[x] = dsu_find(dsu_parent[x]);
    return dsu_parent[x];
}

// 只保留拥挤度 <= limit 的边做合并，判断 s 与 t 是否连通
bool connected_within(ll limit) {
    for (int i = 1; i <= n; i++) dsu_parent[i] = i;  // 每轮 check 都要重建并查集

    for (int i = 0; i < m; i++) {
        if (edges[i].w > limit) continue;  // 拥挤度超限的大道不能走
        // 路径压缩足够：单次操作摊还 O(log n)，本题 n <= 1e4 已经够
        dsu_parent[dsu_find(edges[i].u)] = dsu_find(edges[i].v);
    }

    return dsu_find(start_node) == dsu_find(target_node);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> start_node >> target_node;

    ll max_w = 0;
    for (int i = 0; i < m; i++) {
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
        max_w = max(max_w, edges[i].w);
    }

    if (start_node == target_node) {
        cout << 0 << '\n';  // 不用走路，没有任何一段拥挤度
        return 0;
    }

    // 二分最小的可行上界：[low, high] 内一定存在答案
    ll low = 1, high = max_w;
    while (low < high) {
        ll mid = low + (high - low) / 2;
        if (connected_within(mid)) {
            high = mid;  // mid 可行，答案可能是 mid 或更小
        } else {
            low = mid + 1;  // mid 不可行，答案一定更大
        }
    }

    cout << low << '\n';
    return 0;
}

复杂度

$O(m \log W \cdot \alpha(n))$ ，空间 $O(n + m)$ 。本题 $W \le 10^4$ ，二分约 14 轮。

解法五：枚举所有简单路径（对拍用）

思路

按定义直算：DFS 枚举 $s \to t$ 的所有简单路径，每条路径记录最大边权，在所有路径里取最小值。路径数指数级，只在 $n$ 很小时可用。

它的作用是独立验证——与上面三种做法的实现没有任何共同代码。

代码

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/**
 * 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-21 16:59
 * update_at: 2026-10-21 17:30
 */
// brute.cpp：小数据暴力解，按定义枚举 s 到 t 的所有简单路径，
// 每条路径取「路径上最大边权」，再在所有路径里取最小值。
// 与 main.cpp（Kruskal）、main2.cpp（瓶颈 Dijkstra）、
// main3.cpp（二分答案）三种做法完全不共享实现，适合用来独立验证。
// 路径数是指数级的，只在 n 很小时可用。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 12;  // 只枚举极小数据
const ll INF = (1LL << 60);

struct Edge {
    int to;
    ll w;
};

int n, m, start_node, target_node;
vector<Edge> g[MAXN];
bool in_path[MAXN];  // in_path[u]：u 是否已在当前路径上，用于避免重复经过
ll best;

// 当前在 u，已走部分的最大边权是 current_max
void dfs(int u, ll current_max) {
    if (current_max >= best) return;  // 剪枝：已经不比当前最优更好
    if (u == target_node) {
        best = current_max;  // 到达终点，这条路径的最大边权成为新的最优
        return;
    }
    for (const Edge &e : g[u]) {
        if (in_path[e.to]) continue;  // 只考虑简单路径，避免原地绕圈
        in_path[e.to] = true;
        dfs(e.to, max(current_max, e.w));
        in_path[e.to] = false;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> start_node >> target_node;
    for (int i = 0; i < m; i++) {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }

    best = INF;
    in_path[start_node] = true;
    dfs(start_node, 0);

    cout << (best == INF ? 0 : best) << '\n';
    return 0;
}

复杂度对比

解法	时间	空间	适用
Kruskal + 并查集	$O(m\log m)$	$O(n+m)$	本题最优，且最能体现「阈值」本质
瓶颈 Dijkstra	$O(m\log n)$	$O(n+m)$	边权范围很大时优于二分
二分 + BFS	$O((n+m)\log W)$	$O(n+m)$	最好想，不依赖 MST 知识
二分 + 并查集	$O(m\log W)$	$O(n+m)$	不用建邻接表，check 更轻
枚举路径	指数级	$O(n)$	只用于对拍

本题 $n \le 10^4$ 、 $m \le 2\times10^4$ ，五种做法（除枚举）都能通过。

总结

瓶颈路的核心是阈值连通性：答案等于「让 $s,t$ 连通所需的最小边权阈值」。

三种正确做法分别从三个角度逼近这个阈值：

Kruskal 直接在阈值维度上扫——按边权从小到大放开边，首次连通即得答案；
瓶颈 Dijkstra 把路径代价从「求和」换成「取最大」，在图上做单调搜索；
二分答案 把「求最小阈值」变成「判定某阈值是否可行」，靠单调性二分；判定可以用 BFS，也可以用并查集。

五者算的是同一个量，所以可以互相验证。我用 300 组随机数据（含重边与 $s=t$ 的退化情形）把四份正解实现和暴力枚举做了交叉对拍，结果完全一致。

营救

目录