#P1186. P1186 玛丽卡
P1186 玛丽卡
P1186 玛丽卡
提高+/省选- | 来源:洛谷 | 原题链接
题意
座城市、 条双向路(任意两城最多一条直连路)。 号是麦克、 号是玛丽卡。玛丽卡按最短路走,但恰有一条路在堵车(不知道是哪条)。保证堵任何一条路后 仍可达。求:堵车后最短路时间的最大值。
输入格式
第一行有两个用空格隔开的数 和 ,分别表示城市的数量以及城市间道路的数量。,。城市用数字 标识,麦克在城市 中,玛丽卡在城市 中。
接下来的 行中每行包含三个用空格隔开的数 。其中 ,。这些数字表示在 和城市 中间有一条双行道,并且在 分钟内就能通过。
输出格式
一行,写出用分钟表示的最长时间,在这段时间中,无论哪条路在堵车,玛丽卡应该能够到达麦克处,如果少于这个时间的话,则必定存在一条路,该条路一旦堵车,玛丽卡就不能够赶到麦克处。
输入输出样例
样例 1 输入
5 7
1 2 8
1 4 10
2 3 9
2 4 10
2 5 1
3 4 7
3 5 10
样例 1 输出
27
数据范围
,,;保证堵任何一条路后 仍连通。
提示
考点:删边最短路的经典优化——删掉不在当前最短路上的边,最短路不变,所以只需枚举最短路径上的边( 条),每条删掉后重跑 Dijkstra。易错点:① 回溯路径时记录边的编号而不是点(重边歧义);② 本题保证删任一条边仍连通,无需处理 -1;③ 朴素「每条边都删一次」是 次 Dijkstra,会超时。