自动搬运

查看原文

来自洛谷，原作者为

	Demeanor_Roy 小时候我们总想去改变别人，后来发现，比起改变，筛选是性价比更高的事。

搬运于2025-08-24 22:51:35，当前版本为作者最后更新于2023-10-17 15:05:56，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

• 原题链接。

• 比较困难的一道最短路题。

原题所问为有哪些边，将其边权增加 $2$ 后，能使 $1 \rightarrow n$ 的最短路长度增加 $1$。

考虑将这个条件进行一个转写。令原图 $1 \rightarrow n$ 的最短路长度为 $D$，原条件等价于操作一条边后，满足：

• $1 \rightarrow n$ 不存在长度为 $D$ 的路径。

• $1 \rightarrow n$ 存在一条长度为 $D+1$ 的路径。

看上去十分废话。（

先考虑第一个条件。套路地，我们跑一遍 $1 \rightarrow n$ 的最短路，并据此建出最短路图。显然我们所求的边即为最短路图上 $1 \rightarrow n$ 路径的必经边。

思考如何求那哪些边是必经的，这里给出两个做法。

法一：由于最短路图为 DAG，我们不妨将有向边视作无向，然后用并查集维护连通性。于是我们所求便成了删掉最短路图上的哪些边，能使 $1$ 和 $n$ 不连通。而这是线段树分治裸题，用可撤销并查集维护即可。

法二：一条边是 $1 \rightarrow n$ 的必经边，等价于 $1 \rightarrow n$ 的路径条数等于 $1 \rightarrow n$ 经过该边的路径条数。这一点我们可以对正反图按拓扑序进行一个简单计数求得。但问题是路径数可能很大，无法存储，又因为我们只需要判定是否相等，而不需要真的比大小，我们不妨找一个大质数取模即可。不难证明这样做的正确率是有保证的。

接着考虑第二个条件。不难发现，如果当前我们操作的边是满足条件的，那么任意一条长度为 $D+1$ 的路径一定不会经过它，否则操作前就一定存在一条 $1 \rightarrow n$ 的长度为 $D-1$ 的路径，与已知矛盾。

于是，我们可以把第二个条件等价地写成：原图中存在一条长度为 $D+1$ 的路径不经过该边。

到这里，很多人就会开始误入歧途，往严格次短路方向去想了。但实际上那样无法得到所求。

不妨从路径长度的奇偶性上做文章。不难发现，上述条件等价于存在一条 $1 \rightarrow n$ 的长度奇偶性与 $D$ 不同的最短路不经过该边，且这条路径长度恰好为 $D+1$。这样转化的好处是我们可以把所求看成到每个点长度分别为奇/偶数的最短路信息。

于是考虑拆点，拆边。把点 $u$ 拆成 $u_1,u_2$ 分别表示奇偶。边 $(u,v,w)$ 根据 $w$ 的奇偶性，若为奇数拆成 $(u_1,v_2,w)$ 和 $(u_2,v_1,w)$；否则拆成 $(u_1,v_1,w)$ 和 $(u_2,v_2,w)$。

这样以来，我们就可以根据 $D$ 的奇偶性确定终点是 $n_1$ 还是 $n_2$。问题被等价为了新图上是否所有两点间路径都经过该边，和上面我们解决过的问题相同。

故本题解决。时间复杂度 $O(m \log n)$。

代码很长，但细节不多，就不放了，需要的私信。