#P1396. P1396 营救
P1396 营救
P1396 营救
普及/提高- | 来源:洛谷 | 原题链接
题意
城市分 个区, 条双向大道(可能有重边)连接两区,每条有拥挤度 。妈妈要从区 走到区 ,希望路线经过道路的拥挤度最大值最小。输出这个最小值。
输入格式
第一行有四个用空格隔开的 ,,,,其含义见【题目描述】。
接下来 行,每行三个整数 ,表示有一条大道连接区 和区 ,且拥挤度为 。
两个区之间可能存在多条大道。
输出格式
输出一行一个整数,代表最大的拥挤度。
输入输出样例
样例 1 输入
3 3 1 3
1 2 2
2 3 1
1 3 3
样例 1 输出
2
数据范围
,,,;从 出发一定能到达 。
提示
考点:Dijkstra 变体——把松弛条件 dist[u]+w < dist[v] 改成 max(dist[u],w) < dist[v]。易错点:重边要都存进邻接表(不能用「每对点只存一条」预处理);等价做法还有 Kruskal 按边权排序加边直到 连通、或二分答案。