“咚咚咚……”“查水表！”原来是查水表来了，现在哪里找这么热心上门的查表员啊！小明感动得热泪盈眶，开起了门……
妈妈下班回家，街坊邻居说小明被一群陌生人强行押上了警车！妈妈丰富的经验告诉她小明被带到了 $t$ 区，而自己在 $s$ 区。
该市有 $m$ 条大道连接 $n$ 个区，一条大道将两个区相连接，每个大道有一个拥挤度。小明的妈妈虽然很着急，但是不愿意拥挤的人潮冲乱了她优雅的步伐。所以请你帮她规划一条从 $s$ 至 $t$ 的路线，使得经过道路的拥挤度最大值最小。
第一行有四个用空格隔开的 $n$，$m$，$s$，$t$，其含义见【题目描述】。
接下来 $m$ 行，每行三个整数 $u, v, w$，表示有一条大道连接区 $u$ 和区 $v$，且拥挤度为 $w$。
*两个区之间可能存在多条大道*。
输出一行一个整数，代表最大的拥挤度。
3 3 1 3 1 2 2 2 3 1 1 3 3
2
对于 $30\%$ 的数据，保证 $n\leq 10$。
对于 $60\%$ 的数据，保证 $n\leq 100$。
对于 $100\%$ 的数据，保证 $1 \leq n\leq 10^4$，$1 \leq m \leq 2 \times 10^4$，$w \leq 10^4$，$1 \leq s, t \leq n$。且从 $s$ 出发一定能到达 $t$ 区。
小明的妈妈要从 $1$ 号点去 $3$ 号点，最优路线为 $1$->$2$->$3$。
#include <bits/stdc++.h> #define AC return 0 using namespace std; struct node { long long next, to, dis; } a[200010]; long long n, m, s, t, l = 0, r = 1, cnt, head[200010], ans[200010], spft[10000010]; bool b[200010]; inline void add(long long from, long long to, long long dis) // 邻接表存图 { a[++cnt].next = head[from]; a[cnt].to = to; a[cnt].dis = dis; head[from] = cnt; } int main() { cin >> n >> m >> s >> t; for (register int i = 1; i <= m; i++) { long long a, b, c; scanf("%lld%lld%lld", &a, &b, &c); add(a, b, c), add(b, a, c); } for (register int i = 1; i <= n; i++) ans[i] = 1e9; ans[s] = 0, spft[1] = s, b[s] = 1; do { l++; long long x = spft[l]; b[x] = 0; for (register int i = head[x]; i; i = a[i].next) { long long y = a[i].to, tt = max(ans[x], a[i].dis); if (ans[y] > tt) { ans[y] = tt; if (!b[y]) { spft[++r] = y; b[y] = 1; } } } } while (l < r); cout << ans[t] << endl; AC; }