本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-01 15:07:56

本题题意明显，就是求次短路。

最开始的思路比较简单：找出最短路，删掉这些边，然后再跑一次最短路，但这也很明显是错的。

实际上，我们可以像维护最短路那样，维护一个次短路。设 $f(v)$ 是从源点出发到点 $v$ 的最短路，$g(v)$ 则是相同意义下的次短路。

对于每次在边 $<u, v, w>$ 上的松弛操作：

• 若可以更新最短路，即 $f(v) \gt f(u) + w$，那么 $g(v) \gets f(v)$，$f(v) \gets f(u) + w$

• 若最短路没法更新，但是可以用原最短路更新次短路，即 $f(v) \le f(u) + w$ 但 $g(v) \gt f(u) + w$，那么只更新次短路：$g(v) \gets f(u) + w$

• 如果能更新次短路，即 $g(v) \gt g(u) + w$，那么 $g(v) \gets g(u) + w$

上述三个操作是依次进行的。这样进行一次 SPFA 就可以了。