#P1396. P1396 营救

P1396 营救

P1396 营救

普及/提高- | 来源:洛谷 | 原题链接

题意

城市分 nn 个区,mm 条双向大道(可能有重边)连接两区,每条有拥挤度 ww。妈妈要从区 ss 走到区 tt,希望路线经过道路的拥挤度最大值最小。输出这个最小值。

输入格式

第一行有四个用空格隔开的 nn,mm,ss,tt,其含义见【题目描述】。

接下来 mm 行,每行三个整数 u,v,wu, v, w,表示有一条大道连接区 uu 和区 vv,且拥挤度为 ww。

两个区之间可能存在多条大道。

输出格式

输出一行一个整数,代表最大的拥挤度。

输入输出样例

样例 1 输入

3 3 1 3
1 2 2
2 3 1
1 3 3

样例 1 输出

2

数据范围

1≤n≤1041\le n\le 10^4,1≤m≤2×1041\le m\le 2\times10^4,w≤104w\le 10^4,1≤s,t≤n1\le s,t\le n;从 ss 出发一定能到达 tt。

提示

考点:Dijkstra 变体——把松弛条件 dist[u]+w < dist[v] 改成 max(dist[u],w) < dist[v]。易错点:重边要都存进邻接表(不能用「每对点只存一条」预处理);等价做法还有 Kruskal 按边权排序加边直到 s,ts,t 连通、或二分答案。

蜀ICP备2025119001号-1