#P1186. P1186 玛丽卡

P1186 玛丽卡

P1186 玛丽卡

提高+/省选- | 来源:洛谷 | 原题链接

题意

nn 座城市、mm 条双向路(任意两城最多一条直连路)。11 号是麦克、nn 号是玛丽卡。玛丽卡按最短路走,但恰有一条路在堵车(不知道是哪条)。保证堵任何一条路后 1→n1\to n 仍可达。求:堵车后最短路时间的最大值。

输入格式

第一行有两个用空格隔开的数 NN 和 MM,分别表示城市的数量以及城市间道路的数量。1≤N≤10001 \le N \le 1000,1≤M≤N×(N−1)/21 \le M \le N \times (N - 1)/2。城市用数字 1∼N1 \sim N 标识,麦克在城市 11 中,玛丽卡在城市 NN 中。

接下来的 MM 行中每行包含三个用空格隔开的数 A,B,VA,B,V。其中 1≤A,B≤N1 \le A, B \le N,1≤V≤10001 \le V \le 1000。这些数字表示在 AA 和城市 BB 中间有一条双行道,并且在 VV 分钟内就能通过。

输出格式

一行,写出用分钟表示的最长时间,在这段时间中,无论哪条路在堵车,玛丽卡应该能够到达麦克处,如果少于这个时间的话,则必定存在一条路,该条路一旦堵车,玛丽卡就不能够赶到麦克处。

输入输出样例

样例 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

数据范围

1≤N≤10001\le N\le 1000,1≤M≤N(N−1)21\le M\le \frac{N(N-1)}{2},1≤V≤10001\le V\le 1000;保证堵任何一条路后 1→n1\to n 仍连通。

提示

考点:删边最短路的经典优化——删掉不在当前最短路上的边,最短路不变,所以只需枚举最短路径上的边(≤N−1\le N-1 条),每条删掉后重跑 Dijkstra。易错点:① 回溯路径时记录边的编号而不是点(重边歧义);② 本题保证删任一条边仍连通,无需处理 -1;③ 朴素「每条边都删一次」是 O(M)O(M) 次 Dijkstra,会超时。

五、进阶

蜀ICP备2025119001号-1