旅游

算法思路

本题需要同时满足两个条件：入园和离园时刻都是 $k$ 的倍数，进入景区后不能停下来等待。

1. 记录地点和时间余数

到达同一地点时，如果时间模 $k$ 的余数不同，继续走相同的道路，到出口时的余数也不同。因此，需要把这些情况分别记录。

设 $\operatorname{dist}[u][r]$ 表示从合法入园时刻出发、途中不停留，到达地点 $u$，且到达时刻模 $k$ 为 $r$ 的最早时间。

初始设 $\operatorname{dist}[1][0]=0$，其余状态为无穷大。目标是 $(n,0)$，因为只有在出口且时间为 $k$ 的倍数时，才能立即乘车离开。

2. 道路没有开放时，整体推迟入园

假设当前方案在时刻 $t$ 到达地点 $u$，但下一条道路还没有开放。可以让江月诗改乘更晚的巴士入园，并把此前的整段行程一起向后移动。

由于巴士每隔 $k$ 单位时间到达，推迟量必须是 $k$ 的非负整数倍。此前的道路已经开放，晚一些通过仍然合法，入园后的行走也始终连续。

因此，初始化为 $0$ 只表示最早可选的入园时刻，最终方案可以选择更晚入园。

3. 计算转移时间

对于开放时间为 $a$ 的道路 $(u,v)$，当前时刻为 $t$。选择最小的非负整数 $q$，使得 $t+qk\ge a$：

其中向上取整保证推迟的时间足够；若道路已经开放，则 $q=0$。再经过这条耗时为 $1$ 的道路，得到

若 $T$ 更小，就用它更新 $\operatorname{dist}[v][r']$。

以原样例为例，$k=3$，考虑路线 $1\to 3\to 4\to 5$。先按时刻 $0$ 入园计算，在时刻 $1$ 到达地点 $3$，但道路 $(3,4)$ 从时刻 $3$ 才开放。于是把整个方案推迟 $3$ 单位时间：实际入园时刻变为 $3$，到达地点 $3,4,5$ 的时刻分别为 $4,5,6$，最终在时刻 $6$ 离开，全程没有停留。

4. 使用 Dijkstra 求最早时间

把每个 $(u,r)$ 看作一个状态，用最小堆优先处理当前到达时间最早的状态，跳过过期记录，再枚举出边，按上述公式更新后继状态。

首次取出 $(n,0)$ 的有效记录时，其时刻就是答案；若该状态不可达，则输出 $-1$。

正确性证明

同一状态的两个到达时刻相差 $k$ 的整数倍。较早方案可以整体推迟到较晚时刻，再接上相同的后续行程，因此只保留最早时间不会丢失最优方案。

转移选择满足道路开放要求的最小推迟量，得到的行程合法。在固定余数下，较早到达不会使后继状态的最早时间变晚，且每次转移都会增加时间，因此 Dijkstra 能正确求出最早到达时间。目标状态 $(n,0)$ 恰好对应合法离园，所以算法正确。

复杂度分析

共有 $nk$ 个状态、$mk$ 个可能的转移。使用允许重复入堆的二叉堆时，时间复杂度为 $O(nk+mk\log(mk+2))$，包含优先队列在内的空间复杂度为 $O((n+m)k)$。