题解

思路

不能原地等待是本题的关键。若在时刻 (t) 由通道 (u-v) 到达 (v)，且该通道持续可用，那么可以沿它来回走动，并在 (t,t+2,t+4,\ldots) 这些同奇偶时刻再次到达 (v)。因此，对每个地点分别维护偶数时刻和奇数时刻的可达性。

把一条无向通道拆成两个方向，再按出发时刻奇偶拆分。对于固定方向和固定奇偶性，合法出发时刻形成公差为 (2) 的连续序列 ([L,R])。若能在其起点于某个时刻 (s\le L) 到达，并能沿已有通道来回走到 (L)，就可以在 (L) 使用它；使用后，终点在 ([L+1,R+1]) 中所有同奇偶时刻均可达。

做法

子任务 1

递归枚举每一步选择的通道。状态包含当前地点与当前时刻；到达地点 (n) 时更新答案。最大时刻不超过九，直接枚举全部合法行走序列。

子任务 2

按时间建立分层可达集合。令 (reach[t][v]) 表示时刻 (t) 能否位于地点 (v)。扫描所有边，把 (reach[t][a]) 转移到 (reach[t+1][b])，反向同理。时间复杂度为 (O(Tm))，其中 (T=\max r_i)。

满分算法

对每个地点拆成奇、偶两个状态。每个有向奇偶事件记录：

• 最早合法出发时刻 (L)；
• 最晚合法出发时刻 (R)；
• 起点状态和终点状态。

用小根堆按当前最早出发时刻处理事件。对状态 ((u,p))，维护同奇偶时刻下最晚可达时刻 (last[u][p])。

若弹出的事件满足 (last[u][p]\ge L)，它可以在 (L) 使用，于是终点最早在 (L+1) 到达，最晚可通过在这条边上来回走动延伸到 (R+1)。用 (R+1) 更新终点状态。

若暂时有 (last[u][p]<L)，把事件挂在该起点状态。以后该状态被新事件扩展时，把挂起事件以新的最早可达时刻重新放回堆。每个有向奇偶事件只会被弹出常数次。

正确性说明

固定地点与时间奇偶性后，任何一次沿同一条仍可用通道的往返恰好消耗两秒，所以一段同奇偶的连续可达时刻可以由一个最早时刻和一个最晚时刻完整表示。

每个事件的 ([L,R]) 恰好包含原通道在该方向和该奇偶性下的全部合法出发时刻。若 (last[u][p]\ge L)，起点在 (L) 可达，事件可被使用；沿该边往返又保证终点从 (L+1) 到 (R+1) 的同奇偶时刻全部可达。反之，若 (last[u][p]<L)，当前所有已知路径都无法在事件出现后到达起点，只能等待未来其他事件扩展该状态，因此挂起不会漏解。

小根堆总先处理最小的候选出发时刻。首次产生到达地点 (n) 的事件时，其到达时刻不大于任何尚未处理事件可能产生的到达时刻，故得到全局最早答案。

复杂度

子任务 1 为指数枚举；子任务 2 时间复杂度 (O(Tm))，空间复杂度 (O(n))；满分算法时间复杂度 (O(m\log m))，空间复杂度 (O(n+m))。