删边最短路笔记

· · 算法·理论

板子题 CF1163F

删边最短路顾名思义就是对每条边算出删掉这条边之后这张图的最短路

首先如果这条边不在原图最短路上那么这条边的答案显然就是原图最短路

不然的话 我们有一条最短路上的边删掉之后的最短路 不可能去拐两个并联那样的东西 所以我们去枚举每条非最短路边

经过这条边的最短路一定经过了某个原图最短路的前缀和后缀

这个前后缀实际上就是在 1 为根的最短路树和 n 为根的最短路树和 n/1 的 lca，这东西能树上递推求的

然后就相当于对中间这段没经过的最短路 和经过这条边的最短路的区间取个 min

吉老师线段树。。额

根本不用阿 反正只有最后查询一次 直接标记永久化扔结点上最后 dfs 一次就行了

复杂度线对哦哦哦哦哦

写了近 4k 一遍过了 十分的爽爽爽爽爽爽