警告

本 Blog 仅供蒟蒻 tiger0132 复习用。本蒟蒻

不对其内容正确性做任何保证。

若发现 Bug 请在评论区反馈。本蒟蒻欢迎一切形式的贡献。

点击屏幕以关闭。

(修锅中)「HNOI 2014」道路堵塞 - 最短路 + 线段树

题意

题解有锅,待补锅

传送门:洛谷 P3238 - 道路堵塞

给你一张边带权的有向图和图上的一条点数为 \(L\) 的最短路。对于 \(i \in [1, L]\),求断掉第 \(i\) 条边后,求 \(1 \to n\) 的最短距离。

解法

\(dis_i = \operatorname{dist}(1 \to i), dis'_i = \operatorname{dist}(i \to n)\)。它们显然可以用两边最短路预处理出来。

\(e_i (i \in [1, L+1])\) 为最短路上经过的点,即最短路的第 \(i\) 条边为 \(e_i \to e_{i+1}\)

对于每一条边 \(u \xrightarrow{w} v\),经过它的最短路长度显然是 \(dis_u + w + dis'_v\)

显然,经过它的最短路为 \(1 \to e_2 \to \cdots \to e_a \to \cdots \to u \to v \to \cdots \to e_b \to \cdots \to n\)

那么对于最短路中区间 \([a, b)\) 中的边被删除之后,都可以由一条长为 \(dis_u + w + dis'_v\) 的路径替代。

那么我们相当于对 \([a, b)\)\(\min\)

所以我们可以枚举每一条不在最短路中的边,然后线段树区间取 \(\min\),最后输出每个点的答案。

复杂度可以保证。

代码