自动搬运

查看原文

来自洛谷，原作者为

	TsReaper **

搬运于2025-08-24 21:25:41，当前版本为作者最后更新于2015-07-28 19:57:01，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

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