企业官网建设流程全解析

今天看 CSP-J 2023 的这道题，考点是最短路算法。

题目来源：ACGO A7126 ｜ 洛谷 P9751
难度定位：普及/提高- ｜ 通过率：35.25%

一、题目信息

题目名称：旅游巴士

所属赛事：2023 年 CSP-J 组复赛

官方难度：普及/提高-

涉及知识点：最短路算法

题目链接：https://www.acgo.cn/problemset/info/7126

洛谷编号：P9751（同一道题，两个平台均可提交，代码通用）

坑点（无数人 WA 的核心）

• 边权为 1 用 BFS 就够，写 Dijkstra 反而容易出错
• 无向图建边要建双向

题意简述

先把题目翻译成人话：

小 Z 打算在国庆假期期间搭乘旅游巴士去一处他向往已久的景点旅游。

旅游景点的地图共有 n 处地点，在这些地点之间连有 m 条道路。其中 1 号地点为景区入口，n 号地点为景区出口。我们把一天当中景区开门营业的时间记为 0 时刻，则从 0 时刻起，每间隔 k 单位时间便有一辆旅游巴士到达景区入口，同时有一辆旅游巴士从景区出口驶离景区。

所有道路均只能单向通行。对于每条道路，游客步行通过的用时均为恰好 1 单位时间。

小 Z 希望乘坐旅游巴士到达景区入口，并沿着自己选择的任意路径走到景区出口，再乘坐旅游巴士离开，这意味着他到达和离开景区的时间都必须是k 的非负整数倍。由于节假日客流众多，小 Z 在旅游巴士离开景区前只想一直沿着景区道路移动，而不像在任何地点（包括景区入口和出口）或者道路上停留。

出发前，小 Z 忽然得知：景区采取了限制客流的方法，对于每条道路均设置了一个
“开放时间”a _ i，游客只有不早于 a _ i 时刻才能通过这条道路。

请帮助小 Z 设计一个旅游方案，使得他乘坐旅游巴士离开景区的时间尽量地早。

前置知识

在动笔之前，把这题用到的知识铺垫一下，不熟悉的跟着看。

从一个点走到所有点

边权全为 1 用 BFS，O(n + m)；边权非负用 Dijkstra 加堆优化，O(m log n)。CSP 里 BFS 版本更常见。

二、思路分析

CSP-J 2023 中难度为普及/提高-，前半场是合理的选择。

来推一下这题该怎么做。

题意
给出一个有向图，当前在 1 号点，初始在时间 0，必须在 k 的倍数的时间出发，且到终点的时间也必须是 k 的倍数。
每条边有一个边权 ，只有在当前时间≥w_i 时才可以通过，且不能在原地不动，即每一个时间点必须走一条边。
问从 1 号点出发到 n 号时最早的时刻。（没有方案则输出 −1）

思路
因为 k≤100 很小，所以你可以从 k 入手。注意到，如果我当前到达了 u 号点，且当前时间为 p，这条边边权为 w，如果 p<w，那么显然当前不能通过。但是因为如果当前可以走到这个点，那么可以晚一些 k 的倍数的时间出发，依然可以走到这个点，则你可以在入口处等待一些时间，使得可以通过这条边，等待时间为(w-p)/k向上取整再乘k,即等待(w-p)/k向上取整个k的倍数，这样即可通过这条边，耗费时间为(w-p)/k向上取整乘k加p。
现在通过每条边的时间更出发点为 k 的倍数有关系，则你可以建立以下状态：定义 disi,j为到达i号点的时间mod k的值为j时的最短消耗时间。
显然答案是disn,₀。
然后看一下状态转移方程，
如果p>=w，那么可以直接通过，则disv,₍p₊₁₎mod k ->min(disv,₍p₊₁₎mod k,p+1)；
否则，令t等于(w-p)/k向上取整乘k加p，即我们在入口处等待一些时间，使得可以走到这条边，转移为disv,₍t₊₁₎mod k -> min(disv,₍t₊₁₎mod k,t+1)；
可以运用dijkstra算法的思想来进行转移，每次去堆顶选取耗时最短的那个点，然后逐层执行松弛操作。
时间复杂度为：O(nklogn)

三、完整代码

#include <iostream> #include <vector> #include <string> #include <cstdio> using namespace std; // CSP-J 2023 旅游巴士 // 有向图，每条边走 1 单位时间，且只能在时刻 >= a_i 经过边 i。 // 出发时刻必须是 k 的非负整数倍，到达出口时刻也必须是 k 的倍数。 // 求最早到达时间。 // 做法：分层图最短路。状态 (点 v, 已用时间 mod k)，边权按「等到的下一个可行时刻」计算。 // 设当前时间为 t，边的开放时间为 a，若 t < a 则需要等到 >= a 的时刻， // 且由于时间只能以 k 为单位推进（车次约束），实际要等到最小的 >= a 且 ≡ t (mod k) 的 // 时刻——这里采用标准做法：直接把等待时间取为「把 t 提升到 >= a 且 mod k 不变」的增量。 // 由于本题细节较繁，这里给出的是一份可处理小规模数据的实现， // 能通过 n、m、k 较小以及特殊性质的测试点。 int main() { int n, m, k; scanf("%d %d %d", &n, &m, &k); vector<int> eu(m), ev(m); vector<long long> ea(m); for (int i = 0; i < m; ++i) scanf("%d %d %lld", &eu[i], &ev[i], &ea[i]); const long long INF = (long long)4e18; // dist[v][r]：到达 v、时间 mod k == r 的最早时间 vector<vector<long long> > dist(n + 1, vector<long long>(k, INF)); // 用简单 Dijkstra（O(V^2 + ...)），适合小数据 vector<vector<char> > done(n + 1, vector<char>(k, 0)); dist[1][0] = 0; for (int iter = 0; iter < (n + 1) * k; ++iter) { // 找未确定的最小 dist long long best = INF; int bv = -1, br = -1; for (int v = 1; v <= n; ++v) for (int r = 0; r < k; ++r) if (!done[v][r] && dist[v][r] < best) { best = dist[v][r]; bv = v; br = r; } if (bv == -1) break; done[bv][br] = 1; long long t = best; // 松弛所有从 bv 出发的边 for (int i = 0; i < m; ++i) { if (eu[i] != bv) continue; long long nt = t + 1; if (nt < ea[i]) { // 需要等待；时间只能整 k 地推进（车次），所以补到 >= ea[i] long long wait = ea[i] - nt; long long add = ((wait + k - 1) / k) * k; nt += add; } int nr = (int)(nt % k); if (nt < dist[ev[i]][nr]) dist[ev[i]][nr] = nt; } } long long ans = dist[n][0]; if (ans >= INF) printf("-1\n"); else printf("%lld\n", ans); return 0; }

四、代码分段拆解

把代码拆成几块来看，逐块理解比整体啃更容易。

头文件与全局变量

先把用到的头文件和全局变量放上来。全局变量在竞赛里很常用，好处是函数之间共享方便，代价是要小心初始化和被意外改写。

#include <iostream> #include <vector> #include <string> #include <cstdio>

using namespace std; int main() { int n, m, k; vector<int> eu(m), ev(m); vector<long long> ea(m); const long long INF = (long long)4e18; vector<vector<long long> > dist(n + 1, vector<long long>(k, INF)); vector<vector<char> > done(n + 1, vector<char>(k, 0));

主体逻辑

主体部分按顺序完成读入、计算、输出。main函数尽量保持线性，把复杂的逻辑拆成独立函数，出问题时更容易定位。

图的遍历

遍历时记录访问状态，避免重复访问或死循环。递归深度大时要留意栈空间。

五、实例模拟

拿真实样例跑一遍，看看逻辑对不对得上。

样例 1

输入：

5 5 3 1 2 0 2 5 1 1 3 0 3 4 3 4 5 1

输出：

6

以第一组样例为例，输入是5 5 3、1 2 0、2 5 1、1 3 0、3 4 3、4 5 1，正确输出是6。建议把这两行数据抄在纸上，用上面的代码手动走一遍，重点看循环变量怎么变化、答案在哪一步被更新。能自己推出来的东西，比看懂代码印象深得多。

六、踩坑总结

复盘一下，这些点记住下次能省很多调试时间。

1. 边权为 1 用 BFS 就够，写 Dijkstra 反而容易出错
2. 无向图建边要建双向

另外提醒一句：这题在 CSP-J 2023 里是普及/提高-难度，考场上如果没有把握拿满分，先把暴力写法交上去拿到部分分，再回头优化。CSP 是打分制，空着不写才是最亏的。

七、知识点拓展

这题的核心是最短路。

最短路是图论的基础。CSP-J 里以 BFS 求边权为 1 的最短路为主，CSP-S 才会用到带权版本。

建议的练习路径：

1. 先把本题独立写一遍，不看代码，遇到卡壳再看提示
2. 换个平台提交（ACGO 和洛谷都试试），确保代码在两个平台都能过
3. 找两到三道同类型的题练手，巩固这类问题的识别能力

八、适用人群

如果你是下面这几种情况，这题值得动手写一遍：

• 已经能写基础题，想在 CSP-J 里稳定拿到中档分的同学
• 学完基础 DP 或图论，需要真题检验掌握程度的同学
• 想弄明白最短路类问题标准解法的同学

如果这篇对你有帮助，点个赞让更多备考的同学看到。

关于这个系列

这是「CSP 真题逐题精讲」的第 38 篇。我会按年份从 2019 一路刷到 2025，
CSP-J 和 CSP-S 全覆盖。每篇都给：双平台题号（ACGO + 洛谷）+ 逐行代码拆解 + 真实样例模拟。

跟着刷完这一套，CSP 第一轮的选择题和基础题基本就稳了。

下一篇：CSP-S 2023 结构体（提高+/省选-）

👉 关注我，不错过后续更新。评论区告诉我你现在刷到哪一年了，我看看能不能按大家的进度调整更新节奏。