题解 P1491 【集合位置 】

· · 题解

次短路模版题。首先找出一条最短路，之后一次去掉一条最短路上的边，对于每一次去掉一条边后的图都跑一次最短路，其中最小的答案就是次短路。

为什么要去掉最短路上的一条边呢？因为次短路和最短路必然至少有一条边不是共有的。为什么不去掉不在最短路上的边呢？因为这样最短路是没有变化的。