P10917

035966_L3 · 2024-08-24 12:21:45 · 题解

设地图大小为 s=nm，传送入口为 P_x，出口为 Q_i，起点为 Q_0，终点为 T_y，\to 为最短路径，\Rightarrow 为传送。

很明显，最短路径只能是以下中的一种：

• ………………………………………………………………………

因此，我们要求出 Q_i \to P_x 的长度，并以此求出 Q_0 \to \ldots \to Q_i \to T_y 的长度。

很明显，求 Q_i \to P_x 的长度时，(q+1) 遍 BFS 是不可取的。然而，由于这 (q+1) 遍 BFS 的终点都是 P_x，我们可以以 P_x 为起点反向进行 BFS，这样就可以在 O(s) 内求出 Q_i \to P_x 的长度了。

举个例子：

初始状态：

最终状态（6 轮 BFS 后）：

因此 Q_{[0,6]} \to P_x 的长度分别为 6,6,0,2,2,+\infty,2（Q_5 无法到达 P_x），Q_0 \to Q_{[0,6]}（走传送门）的长度分别为 0,6,12,12,14,16,+\infty（Q_6 无法通过这一方式到达，因为 Q_5 无法到达 P_x）。

求 Q_0 \to \ldots \to Q_i \to T_y 的长度时，我们仍然可以 BFS，对每个可能的最短路径长度 BFS 一轮即可。当目前长度等于 Q_0 \to Q_i（走传送门）的长度，且 Q_i 还没有入队时，我们要将 Q_i 入队。

我们继续使用上面的例子。

初始状态：