题解

思路推导

一次操作能够从 $u$ 到达 $v$，当且仅当原图中存在一条从 $u$ 到 $v$、长度恰为某个 $2^k$ 的路径。可以先求出所有这种点对，再把它们看作新图中的一条边。问题就转化为新图中从 $1$ 到 $n$ 的最少边数。

设 $f_k(u,v)$ 表示原图中是否存在长度恰为 $2^k$ 的路径。原图中的每条边对应 $f_0$。一条长度为 $2^k$ 的路径可以从中间切成两条长度为 $2^{k-1}$ 的路径，因此可以通过枚举中点递推。

题目只允许总长度不超过 $2^{31}-1$，所以只需处理 $k=0,1,\ldots,30$。

做法

先把原图边写入 $f_0$。对每个 $k\ge1$，枚举 $u,x,v$；若 $f_{k-1}(u,x)$ 与 $f_{k-1}(x,v)$ 都成立，则令 $f_k(u,v)$ 成立。

只要某个 $f_k(u,v)$ 成立，就在新图中加入从 $u$ 到 $v$ 的边，表示可以用一秒完成这段移动。最后在新图上从顶点 $1$ 做 BFS，得到到顶点 $n$ 的最少边数。

正确性证明

对 $k$ 归纳。$k=0$ 时，$f_0(u,v)$ 恰好表示原图中存在一条边，即存在长度为 $1=2^0$ 的路径。

假设 $f_{k-1}$ 的含义正确。若递推得到 $f_k(u,v)$，则存在中点 $x$，使得 $u$ 到 $x$ 和 $x$ 到 $v$ 都有长度 $2^{k-1}$ 的路径，连接后得到长度 $2^k$ 的路径。反过来，任意长度 $2^k$ 的路径在走完前 $2^{k-1}$ 条边后到达某个中点 $x$，两半都会被 $f_{k-1}$ 记录，故递推一定得到 $f_k(u,v)$。归纳成立。

因此新图中的每条边与一次合法的跑路器操作一一对应。新图中的一条从 $1$ 到 $n$ 的路径对应一系列合法操作，路径边数就是耗时；任何合法操作序列也对应新图中的同长路径。BFS 求得的最少边数即为最少秒数。

复杂度分析

共有 $31$ 层可达关系，每层枚举三个顶点。预处理时间复杂度为 $O(31n^3)$，BFS 时间复杂度为 $O(n^2)$；空间复杂度为 $O(31n^2)$。