2303. 营救
1000ms
256MB
简单
题目描述
在一张由 $n$ 个节点和 $m$ 条无向边构成的图上，每条边都有一个权值 $w$（代表拥挤度/风阻值）。
给定起点 $s$ 和终点 $t$，你需要规划一条从 $s$ 到 $t$ 的路径，使得该路径上所有边中**权值的最大值尽可能小**。请输出这个最小的最大权值。
输入格式
- 第一行包含四个正整数 $n, m, s, t$ ($1 \le n \le 10^4, \quad 1 \le m \le 2 \times 10^4, \quad 1 \le s, t \le n$)，其含义见题目描述。
- 接下来 $m$ 行，每行包含三个整数 $u, v, w$ ($1 \le u, v \le n, \quad w \le 10^4$)，表示有一条无向边连接节点 $u$ 和节点 $v$，其权值为 $w$。
- 图中可能存在重边（即两个节点之间存在多条边）。
输出格式
- 输出一行一个整数，代表路径上最大边权的最小值。
样例 1
输入 (Input)
3 3 1 3 1 2 2 2 3 1 1 3 3
输出 (Output)
2
- 对于 $30\%$ 的数据，保证 $n \le 10$。
- 对于 $60\%$ 的数据，保证 $n \le 100$。
- 对于 $100\%$ 的数据，保证 $1 \le n \le 10^4$，$1 \le m \le 2 \times 10^4$，$w \le 10^4$，$1 \le s, t \le n$。且数据保证从 $s$ 出发一定能到达 $t$。
- **样例解释**：
从 1 号点去 3 号点，有两条路径：
- 路径 1: $1 \to 3$，最大边权为 3。
- 路径 2: $1 \to 2 \to 3$，经过的边权分别为 2 和 1，最大边权为 2。
- 最小的最大边权为 2。
- **算法提示**：
本题是经典的**最小瓶颈路**问题。由于只需要求最大边权的最小值，我们可以借鉴 **Kruskal 最小生成树** 的思想：
1. 将所有边按照权值 $w$ **从小到大**进行排序。
2. 依次遍历排好序的边，使用**并查集（DSU）**将边的两个端点合并。
3. 每次合并后，立即检查起点 $s$ 和终点 $t$ 是否已经连通（即 `find(s) == find(t)`）。
4. 一旦连通，当前加入的这条边的权值 $w$ 就是我们要找的答案，直接输出并结束程序即可。
› 输入 stdin
CtrlShiftEnter
‹ 输出 stdout
错误 stderr
操作成功