浅谈一类最短路问题

P2685 [TJOI2012] 桥

首先求出一个最短路树，显然只能删除树上的边才对答案有影响。

最短路树有很多，任意求一个可以吗？可以，因为删除一条边后就可以走另一个最短路树了。

枚举删除哪一条边并不好计算。考虑最后我们最短路一定是 \(1\to l_x\to x\to y\to r_y\to n\) 的样子，所以我们考虑枚举不在最短路树上的边 \((x,y)\)，找到最短路树上对应的 \((l_x,r_x)\)，更新答案。

最后查询单点最小值即可。

如何预处理 \(l,r\) 数组？按照一定的顺序加入最短路中的每个点，每次都 bfs 更新所有点即可，由于每个点只会更新一次，故复杂度均摊线性。

[ABC375G] Road Blocked 2

建出最短路图。

一种方法是对最短路方案计算，考虑一条边是否有 \(c1_x\times c2_y = c(1,n)\)，由于需要取模估计需要调参。

另外一种方法就是判断最短路图上这条边是否为割边。