CF1163F Indecisive Taxi Fee(线段树+图论)

做法

这里的修改是暂时的

找到一条最短路径(E)，需要考虑的是将最短路径上的边增大

每个点考虑与(1/n)的最短路径在E上前缀/后缀的位置，设(L_i,R_i)

考虑每条边((u,v))，(u)和(v)分别在(E)上连(L)或(R)，相对于一个桥的形状，桥跨过的边则说明不经过那些边的最短路径

考虑是连续的区间，用线段树统计

将边增大，答案为(min()原最短路径，不经过该边的最短路径())