自动搬运

查看原文

来自洛谷，原作者为

	houpingze 再也找不回曾经的自己

搬运于2025-08-24 21:52:00，当前版本为作者最后更新于2021-05-20 21:47:12，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

提供一种不一样的解法（

也就想、调了5h吧，嗯不算长

考虑$3$次SPFA。

第一次，我们使用SPFA建立 $Mx$数组，$Mx_i$表示导航1认为的$1$到$n$的最短路径 。

第二次，我们再一次使用SPFA建立 $My$数组，$My_i$表示导航2认为的$1$到$n$的最短路径。

注意区分$p_i$和$q_i$不要写错了

重点来了！

我们可以再建一个图$G$，其中$G_{i,j}$表示从结点$i$走到结点$j$，抱怨数之和，当然结点$i$和结点$j$有直接的边相连。

那么咋算有直接边的两点之间的抱怨数和呢？

我们想到，如果从$i$结点出发，到$j$结点，第一个GPS会抱怨，当前仅当$Mx_i+u\neq Mx_j$（注意是$\neq$）。

其中u为第一个GPS认为的从$i$结点出发，到$j$结点的时间。

第二个GPS会抱怨的情况也同理。

我们可以把经过每条边的抱怨值都算出来（第一个GPS是否抱怨+第二个GPS是否抱怨），构成一个图，再跑一遍SPFA，就可以算出抱怨值最小是多少了。