[CSP-J 2023] 旅游巴士 题解
一、先理解题目（不要急着抽象）
【简单理解】
这道题其实是在解决：
小 Z 要从 1 号点走到 n 号点。
景区里有很多条单向道路，每条道路都有三个信息：
表示：
* 这条路从 u 走到 v；
* 走这条路需要 1 单位时间；
* 这条路最早在 t 时刻开放。
还有一个很重要的限制：
小 Z 只能在 k 的倍数时刻坐车进入景区，也只能在 k 的倍数时刻坐车离开景区。
比如 k = 3，那么能坐车的时刻是：
题目要我们求：
小 Z 最早能在什么时刻从 n 号点离开景区。
如果无论怎么走都不行，就输出：
最容易误解的一点：
小 Z 在景区里面不能停留。
也就是说，他到达一个点之后，下一分钟必须继续走一条路，不能站在那里等某条路开放。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
二、题意抽象（从故事变成数学问题）
【抽象之后】
给定：
* n 个点；
* m 条有向边；
* 每条边通过时间都是 1；
* 每条边有一个开放时间 t；
* 起点是 1；
* 终点是 n；
* 进入景区和离开景区的时刻都必须是 k 的倍数。
要求：
找一个最小的时间 ans，满足：
1. ans 是 k 的倍数；
2. 小 Z 能在 ans 时刻到达 n 并离开；
3. 路上经过每条边时，这条边都已经开放；
4. 路途中不能停留。
本质：
我们要找的不是普通最短路，而是“最早的合法离开时间”。
因为答案必须是 k 的倍数，所以可以把答案写成：
问题就变成：
有没有某个最小的 x，使得小 Z 可以在 x * k 时刻离开景区？
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
三、思考如何解决（先讲思考过程）
1. 最直接的方法是什么？
最直接的想法是：
从起点 1 开始，一步一步往外走，尝试所有路线。
这种方法不行。
原因是：
* 图里路线可能很多；
* 有些路线会绕圈；
* 直接枚举路线可能一直枚举不完；
* 我们还要处理每条边的开放时间。
所以不能暴力枚举所有路线。
2. 观察题目特点
我们观察到两个重要特点。
第一个特点：
答案一定是 k 的倍数。
所以答案可以写成：
第二个特点：
如果某个离开时间 x * k 可以做到，那么更晚的离开时间通常也更容易做到。
因为所有道路的限制都是：
走得更晚，不会让已经开放的路重新关闭。
这说明答案具有“可以二分”的特点。
这里第一次出现专业名词：
二分答案，就是不直接求答案，而是先猜一个答案，再判断这个答案行不行。
如果这个答案可行，就尝试更小；如果不可行，就尝试更大。
3. 为什么要反着想？
如果从起点正着走，会遇到一个麻烦：
当某条路还没开放时，小 Z 不能在原地等。
正着判断时，我们要考虑“是不是可以把出发时间整体往后推”，比较绕。
换个角度：
我们先假设最终离开时间已经确定了，比如：
然后从终点 n 倒着往回推。
如果一条路是：
正着走时，从 v 到 u 要花 1 分钟。
倒着看，就是从 u 退回到 v，表示这条路是最后某一步经过的路。
这样我们就可以直接知道：
如果从 v 走到 u，那么经过这条边的出发时刻是多少。
只要这个出发时刻不早于边的开放时间，这条边就可以用。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
四、算法核心思想（重点讲理解）
1. 二分的对象
因为答案一定是 k 的倍数，所以我们二分的是：
最终答案是：
例如 k = 3：
如果二分到 x = 4，其实就是在判断：
2. CHECK(X) 表示什么
check(x) 的作用是判断：
如果可以，返回 1。
如果不可以，返回 0。
3. 为什么反向建图
原来输入的边是：
表示可以从 u 走到 v。
我们在代码里反向存：
也就是把边存成：
这样在 check(x) 里面，就可以从终点 n 开始往回找。
4. 状态到底是什么意思
先不要急着看二维数组。
我们先想一个问题：
如果倒着找路，我们需要知道什么？
最少要知道：
比如现在倒推到了 u，说明我们正在思考：
如果只是普通走迷宫，记录一个：
可能就够了。
但是这道题不够。
原因是本题不仅关心“能不能到某个点”，还关心：
因为这个长度会影响一件很重要的事：
进入景区的时间是不是 k 的倍数。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
5. 为什么一维状态 DIS[U] 不够
假设 k = 3，最终离开时间是：
现在有两种方法都能倒推到同一个点 u。
第一种方法：
那么正着走时，到达 u 的时间是：
第二种方法：
那么正着走时，到达 u 的时间是：
这两个情况都在同一个点 u，但是它们不一样。
为什么不一样？
因为：
第一种路线长度不是 3 的倍数，第二种路线长度是 3 的倍数。
最后如果倒推到起点 1，我们必须保证整条路线长度是 k 的倍数。
这样进入时间：
才也是 k 的倍数。
所以只记录：
会把“同一个点，但是路线长度余数不同”的情况混在一起。
一旦混在一起，就可能把本来合法的路线丢掉。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
6. 为什么状态要是二维
既然只记录点不够，那还要多记录什么？
我们刚才发现，真正会影响合法性的不是完整长度本身，而是：
比如 k = 3：
它们虽然长度不同，但是对 3 取余都是 0。
只要余数相同，它们在“能不能让进入时间也是 k 的倍数”这件事上，作用是同一类的。
所以我们把状态设计成：
表示：
这里有两个信息：
* 第一维 u：现在在哪个点；
* 第二维 r：已经倒推的路程长度对 k 取余是多少。
可以把它想成一张表。
如果 k = 3，每个点都有三种情况：
状态 含义 dis[u][0] 倒推到 u，路线长度是 3 的倍数 dis[u][1] 倒推到 u，路线长度除以 3 余 1 dis[u][2] 倒推到 u，路线长度除以 3 余 2
同一个点 u，这三种情况必须分开存。
因为它们最后能不能作为起点，是不一样的。
只有余数为 0 的路线长度，才能保证进入时间也是 k 的倍数。
数组里面存的值：
表示：
也就是说，dis[u][r] 存的是最短时间。
注意：
dis[u][r] 不是实际时刻。
它是“从 u 到终点还需要走的最短路程长度”。
为什么要存最短？
因为如果两个方案都倒推到了同一个点 u，而且余数都是 r，那么它们对“能不能让入口时间是 k 的倍数”这件事没有区别。
它们的区别只剩下：
更短的方案一定不比更长的方案差。
原因是：最终离开时间 T = x*k 已经固定。
如果从 u 到终点还要走的时间越短，那么正着到达 u 的时间就是：
这个时间会更晚。
而道路开放的要求是：
走得更晚，只会更容易满足开放时间，不会更难。
所以对于同一个 u,r，我们只需要保留最短时间。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
7. 为什么第二维一定是余数
因为进入和离开的时刻都必须是 k 的倍数。
我们在 check(x) 中已经固定最终离开时间：
这个时间一定是 k 的倍数。
如果整条路线长度是 L，那么进入景区的时间是：
现在要让进入时间也是 k 的倍数。
由于 T 已经是 k 的倍数，所以只需要：
所以我们根本不需要记录完整的 L 属于哪一类，只需要记录：
这就是第二维为什么是余数。
最后我们看：
意思是：
能不能倒推回起点 1，并且整条路线长度对 k 取余为 0。
如果可以，进入时间和离开时间就都能坐车。
8. 倒推一条边时怎么判断能不能走
假设当前在倒推状态：
并且：
这表示：
从 u 走到终点 n，还需要 d 分钟。
现在倒着经过一条边，退回到前一个点 v。
那么从 v 到终点的路程长度就变成：
如果最终离开时间是：
那么正着走这条边 v -> u 的出发时间就是：
这条边的开放时间是 lim。
只有当：
也就是代码里的：
这条边才可以使用。
如果可以使用，就更新：
因为倒退了一条边，路程长度增加了 1，余数也要加 1。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
五、用简单例子模拟算法过程
假设：
有这些路：
终点是 4。
我们判断：
意思是：
能不能在 6 时刻离开景区？
初始时，从终点开始倒推：
表示已经在终点，离终点还需要 0 分钟。
第一步，倒着走 3 -> 4。
从 3 到终点要：
正着走 3 -> 4 的出发时刻是：
这条路开放时间是 0，5 >= 0，可以走。
所以：
第二步，倒着走 2 -> 3。
从 2 到终点要：
正着走 2 -> 3 的出发时刻是：
这条路开放时间是 4，4 >= 4，刚好可以走。
所以：
第三步，倒着走 1 -> 2。
从 1 到终点要：
正着走 1 -> 2 的出发时刻是：
这条路开放时间是 0，3 >= 0，可以走。
所以：
为什么余数是 0？
因为：
这说明路线长度是 3，进入景区时间是：
3 也是 k 的倍数，所以可以坐车进入。
因此 check(2) 返回 1。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
六、复杂度分析
一次 check(x) 中，每个状态最多进入队列一次。
状态是：
所以状态数量是：
每条边在每种余数下最多被检查一次，所以一次检查的时间复杂度大约是：
二分答案需要检查很多次。
如果二分范围是 0 到 1e7，大约检查 log(1e7) 次，也就是二十多次。
所以总时间复杂度是：
空间复杂度：
根据本题数据范围，k <= 100，这个做法可以通过。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
七、代码实现思路
代码需要这些变量：
* n,m,k：点数、边数、巴士间隔；
* E[v]：反向图，存能到达 v 的前一个点；
* dis[u][r]：倒推到 u，路程长度 % k = r 时，从 u 到终点的最短时间；
* check(x)：判断能不能在 x*k 时刻离开；
* l,r,mid：二分答案用的变量。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
八、代码逐步解释
1. 为什么输入时反向存边
题目给的是：
但我们要从终点倒着推回起点。
所以代码写成：
意思是：
如果倒推时到了 v，就可以尝试退回 u。
2. CHECK(X) 为什么从 N 开始
check(x) 已经固定了离开时间：
所以我们先站在终点 n，表示已经离开前的最后位置。
这里的 0 表示：
从终点到终点还需要 0 分钟。
3. 为什么用队列 BFS
每次倒推一条边，路程长度都会增加 1。
也就是说，所有边的“倒推代价”都是一样的。
这种情况下可以用 BFS，也就是一层一层扩展。
BFS 的特点是：
先扩展距离短的状态，再扩展距离长的状态。
所以一个状态第一次被访问到时，得到的一定是最短时间。
例如：
表示我们第一次用 3 分钟倒推到了 (u,r)。
如果后面还有一种方法也能到 (u,r)，但需要 5 分钟，那么它没有必要再更新。
因为同样是 (u,r)，3 分钟更短，正着看就是到达 u 的时间更晚，更容易满足后续边的开放时间。
这就是为什么代码里只在：
时才更新。
4. 最关键的判断
代码中最重要的是这一句：
它包含两层意思。
第一层：
表示这个状态之前没有到达过。
由于 BFS 是按路程长度从小到大扩展的，所以“之前没有到达过”也等价于：
第二层：
表示正着走这条边时，出发时间不早于开放时间。
这里：
* x*k 是最终离开时间；
* val 是从当前这个前驱点走到终点还需要的时间；
* x*k-val 就是正着经过这条边的出发时间；
* lim 是这条边的开放时间。
5. 为什么最后看 DIS[1][0]
如果：
说明我们能倒推回起点 1，并且整条路线长度对 k 取余为 0。
设路线长度为 L。
因为最终离开时间是：
如果：
那么进入景区的时间：
也是 k 的倍数。
这就同时满足：
1. 可以坐车进入；
2. 可以坐车离开；
3. 中间每一步都不等待。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
九、易错点总结
1. 没有反向建图
这份做法的核心是从终点往起点倒推，所以输入边 u -> v 要存成 E[v].push_back({u,t})。
2. 把 dis[u][r] 理解成到达时间
这里的 dis[u][r] 不是实际时刻，而是从 u 到终点最少还要走多少分钟。
实际经过某条边的时间，要用：
算出来。
3. 忘记判断起点时间是否合法
不是能倒推到 1 就一定合法。
必须是：
因为这表示路线长度是 k 的倍数，进入景区时间才也是 k 的倍数。
4. 二分的是 x，不是直接二分答案时间
代码里二分的是：
最后输出的是：
5. check 每次都要重新初始化 dis
不同的 x 表示不同的最终离开时间，能走的边可能不同。
所以每次检查前都要把 dis 重新设成 -1。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
十、最后总结解题方法
这道题考察的是：
1. 二分答案；
2. 反向建图；
3. BFS 判断可行性；
4. 用路程长度对 k 取余来保证进出时间合法。
看到这类题：
第一步：
先观察答案是否有固定形式。本题答案一定是 k 的倍数，所以写成 x*k。
第二步：
思考能不能二分。越晚离开，路的开放时间越容易满足，所以可以二分。
第三步：
固定一个离开时间 x*k，从终点倒着推。
第四步：
倒推每条边时，计算正着经过这条边的出发时刻：
如果不早于开放时间，就可以转移。
第五步：
最后检查：
如果成立，说明这个离开时间可行。
