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