[USACO06NOV] Roadblocks G 题解

思路

题目要求的是严格大于最短路长度的最小路线长度，因此两条等长最短路不能直接作为第一短和第二短。由于所有边权均为正数，可以为每个点维护两个不同的最小到达距离：最短距离和严格更大的次短距离。

从点 $1$ 开始使用优先队列。取出状态 $(d,u)$ 后枚举与 $u$ 相连的道路，得到新距离 $d+w$。如果它小于当前最短距离，就把原最短距离下移为次短距离；如果它严格大于最短距离且小于当前次短距离，就更新次短距离。只有这两个距离需要继续扩展，因为其他更长状态不可能改善任一点的前两种不同距离。

允许重复经过道路或点不会破坏这个过程。正边权保证优先队列按距离弹出状态时，所有后续扩展只会更长；回溯路线也会自然作为某个更长状态进入队列。

还可以独立验证答案。分别求出点 $1$ 到各点的最短距离 $d_1$，以及点 $N$ 到各点的最短距离 $d_N$。对每条无向边的两个方向 $(u,v)$，考察 $d_1(u)+w(u,v)+d_N(v)$。其中严格大于全局最短路的最小值就是答案：任何更长路线都至少含有一个不能继续保持全局最短距离的有向边，而替换该边前后的部分为最短路只会使路线更短。

在 $N\le 300$ 时，也可先用 Floyd 算法求全源最短路，再枚举每条有向边使用同一判定式，得到一个结构独立的平方以上做法。

做法

1. 将每条道路加入无向邻接表。
2. 初始化每个点的最短距离和次短距离为无穷大，令点 $1$ 的最短距离为零。
3. 用优先队列按当前距离从小到大扩展状态。
4. 对每次松弛结果，分别处理“刷新最短距离”和“刷新严格次短距离”两种情况；等于最短距离的结果不进入次短距离。
5. 输出点 $N$ 的次短距离。

复杂度

小规模 Floyd 做法的时间复杂度为 $O(N^3+R)$，空间复杂度为 $O(N^2)$。

满分做法的时间复杂度为 $O(R\log N)$，空间复杂度为 $O(N+R)$。