P2865 [USACO06NOV] Roadblocks G & 次短路

__ryp__ · 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 就可以了。