标签：le nm 复杂度 bfs 终点 TeleporterAndClosedOff

Teleporter and Closed off

思路

首先考虑从起点和终点分别 bfs（终点的 bfs 定义为从其他所有点到他，即在反向图上），预处理出两个距离，可以在 \(O(nm)\) 的复杂度内求出。

然后考虑怎样可以不经过 \(i\)。

必然是存在一个 \(j\)，使得 \(j+k(1\le k\le m)>i\)，且存在边 \(j->j+k\)。每次对于确定的 \(i\)，暴力枚举可能的 \(j,k\)。复杂度 \(O(nm^2)\)。

代码

标签：le,nm,复杂度,bfs,终点,TeleporterAndClosedOff
From： https://www.cnblogs.com/wscqwq/p/17601005.html