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，就可以算出抱怨值最小是多少了。