[CF1163F] 删边后的最短路

问题#

如何在任删除一条边后求解图中从 $S$ 到 $T$ 的最短路？

方法#

考虑求出图中的最短路 $P$。

如果待删除的边本身不在最短路上，则不会给结果带来任何影响。如果删除了最短路上的边，需要继续讨论。

考虑一条不经过最短路 $P$ 某条边的最短路 $P'$。这条路线如果和 $P$ 有交点，就会以 $P$ 的前缀/后缀作为 $P'$ 的一部分（否则 $P$ 就不是最短路）。

• 上侧路线 5 直接以 $S$ 和 $T$ 作为两端。
• 下侧路线因为经过 $P$，会和 $P$ 共享一段前缀和后缀。

路线 $P'$ 一定是一段绕路经过了图中原本不属于 $P$ 的某条边 $E$（一定得是边）所形成的新路线。如果 $P'$ 分别在 $L$ 和 $R$ 处和 $P$ 接驳，那么 $P$ 上 $L$ 到 $R$ 之间的边无论存在与否都对 $P'$ 没有影响，即，$P'$ 可以作为删除其中任意一条边后的备选答案之一。区间修改单点查询最小值可以用线段树维护。

最后，还需要保证从 $P$ 上分叉出去的两条到达 $E$ 左右顶点的路同样是最短的。这可以通过分别以 $S$ 和 $T$ 求最短路得到。