houpingze 的博客

膜拜zqs,sx,zlt,ymw,qyh官方博客

P3720 [AHOI2017初中组]guide题解

提供一种不一样的解法(

也就想、调了5h吧,嗯不算长/cy

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


2021-05-20 21:47:12 in 题解