P3720 [AHOI2017初中组]guide题解

提供一种不一样的解法（ ~~也就想、调了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`，就可以算出抱怨值最小是多少了。