P15417「yrOI R1」彼时蓝星这道题赛后我看了一圈讨论发现不少人卡在了同一个地方明明是最短路的壳子为什么直接把普通 Dijkstra 板子搬过来却过不了样例我的答案是你还没把“错过班车”这件事转化成图上的转移。这篇文章就是一份完整题解我会从题意抽象开始把状态设计、算法正确性、代码实现和调试经验都过一遍。适合已经掌握基础 Dijkstra、想突破带时间约束最短路模型的选手参考。1. 题意理解与问题转化1.1 原题背景与抽象模型题目背景里把节点叫作空间站边叫作星际航线。每一趟航线有固定的离站时刻和到站时刻你只能在这个离站时刻乘坐它如果你到达起点站的时刻早于离站时刻就可以在站内等待如果晚于离站时刻这班航线就彻底错过了。目标是求出从编号 1 的地球站到编号 n 的蓝星站的最早到达时刻。形式化来说图上有 n 个点m 条有向边。每条边 e 由四个信息组成起点 u、终点 v、离站时间 s_e、到站时间 t_e且保证 t_e s_e。当你当前站在 u 的时刻为 cur 时只有 cur ≤ s_e 才能走这条边走完之后到达 v 的时刻变为 t_e。如果有多条边可用你可以任意选择在节点内等待不消耗额外时间只改变你出发时对应的时刻。这个模型看起来和普通最短路非常像但有一个本质区别边权不再是固定的常数而是“有条件触发”的离散事件。你不能简单写成 dist[v] min(dist[v], dist[u] w)因为 w 在这里不是一个定值而是和“你到底坐上了哪班航线”绑定。理解这个区别是解开整道题的第一步。为了直观感受你可以把每个节点想象成一个公交站每条边想象成一班只在固定时间发车的公交。公交车不会因为你来早了就提前出发也不会因为你来晚了就等你。普通最短路里的“随到随走”完全失效取而代之的是“要么上车要么等下一班要么这站直接放弃”。1.2 为什么朴素搜索做不了很多新手第一反应是 DFS 或 BFS从 1 出发枚举所有能坐的航线记录到达 n 的最小时间。可惜这个方案很快就会被数据规模劝退。因为路径数量是指数级的哪怕 n 只有几十m 上百暴力枚举也会在递归层数变深后彻底爆炸。更麻烦的是图里可能存在环而 DFS 如果不去重就会被环套住出不来。有人会说“那我记忆化搜索记录每个点的最早到达时间不就行了”这确实接近正解了但仍需要小心处理。如果直接按 DFS 的记忆化顺序去更新一个点可能先被一个较晚的到达时间更新之后又被一个更早的到达时间更新但如果 DFS 的搜索顺序不对就会漏掉后者。本质上你还是需要一种能保证“先处理最早到达状态”的遍历顺序。BFS 也不行因为边的“代价”不是统一的层数。你以为走了一步实际时间可能从 1 跳到 100也可能从 100 跳到 101。BFS 的队列只能保证步数单调不能保证时间单调。普通最短路里的 SPFA 同样不适合它的松弛顺序依赖边权可加性面对这种离散班次模型很容易出现反复入队、复杂度退化甚至错误更新。所以我们需要一种能够主动维护“当前最小时间”的数据结构。这正好是 Dijkstra 的用武之地。虽然它的经典形式是处理非负边权但稍加改造就能处理这种固定班次的时间依赖图。1.3 把“等待”当成一种特殊转移在普通最短路中从 u 到 v 的转移只发生在你到达 u 的瞬间。但在本题里转移实际上分为两步先考虑是否需要等待再乘坐航线。等待本身不改变你的位置只改变当前时刻。如果当前时刻 cur 小于某条航线的离站时间 s_e那么等车后的时刻就变成 s_e随后到达 v 的时刻是 t_e。如果 cur 恰好等于 s_e那就不需要等待直接上船。从状态图的角度看等待相当于在原图上增加了许多“时间环”从节点 (u, cur) 跳到 (u, s_e)再通过航线跳到 (v, t_e)。普通最短路把所有可能的等待时间都压成了一次转移所以会显得比较隐蔽。一旦你把等待显式展开就会发现整个图其实是一个时间单调递增的 DAG因为它永远不会让你回到过去。这也是为什么 Dijkstra 在这里非常自然每条航线都在把时间往前推Dijkstra 按当前已知最早时间从小到大处理状态恰好尊重了这种时间单向性。如果题目中允许出现“到达时间倒流”的边那模型就完全变了可能要用到带负环的最短路算法但本题不存在这种情况。2. 核心算法从最短路到时间依赖 Dijkstra2.1 状态设计与松弛方程定义 dist[u] 表示从起点 1 出发到达节点 u 的最早时刻。初始时 dist[1] 0其余点为 INF。我们只需要维护这个一维数组不需要额外把时间拆进节点原因在于每个节点的最早到达时间已经足够描述后续转移的所有信息。对于一条从 u 指向 v、离站时刻为 s、到站时刻为 t 的边松弛条件可以写成如果 dist[u] ≤ s则 dist[v] min(dist[v], t)。为什么不需要考虑 dist[u] s 的情况因为一旦当前到达时刻晚于离站时刻这班航线就不可能再坐上了。以后从 u 出发的其他路径只会让到达时刻更晚更不可能赶上这班航线所以这条边可以直接忽略。你可能会问如果 dist[u] s那到达 v 的时刻为什么不是 s (t - s) 而是直接 t因为 t 已经包含了飞行耗时等车阶段只改变你在 u 的出发时刻不改变航线的到站时刻。换句话说从 u 出发的实际时刻是 max(dist[u], s)到达 v 的实际时刻是 t。由于条件 dist[u] ≤ s 保证了 max(dist[u], s) s所以结果就是 t。这个松弛方程和普通 Dijkstra 非常像只是把原来的 「dist[u] w」 换成了条件触发下的 t。我们可以把它统一写成伪代码if dist[u] s_e: dist[v] min(dist[v], t_e)整个算法的骨架和普通 Dijkstra 完全相同用优先队列维护当前未确定的最小 dist 节点从堆顶取出节点 u如果它已经处理过就跳过然后枚举 u 的所有出边做松弛松弛成功则把新的 dist[v] 和 v 一起压入堆中。2.2 Dijkstra 正确性论证这里有一个非常重要的问题为什么这种“边权不是常数”的 Dijkstra 依然正确我们需要仔细推敲因为它不是普通 Dijkstra 的直接推广。普通 Dijkstra 的正确性依赖两点边权非负以及最短路径的子路径也是最短路径。在本题中每条航线都会让时间严格增加t s所以任何一条路径上的节点到达时间都是严格递增的。这意味着如果你沿着某条路径从 1 走到了 v那么路径上任意一个中途节点 u 的到达时间一定不超过最终到达 v 的时间。假设算法第一次从堆中弹出节点 u 时dist[u] 已经是最小可能。如果存在一条更早到达 u 的路径 P那么路径 P 上 u 的前驱节点 w 一定在某个更早的时刻被弹出并且会通过那条边对 u 进行松弛。由于 Dijkstra 按 dist 从小到大弹出节点前驱 w 的弹出时间一定早于 u所以这条更优路径不可能被漏掉。这里的关键是转移产生的目标时间 t 严格大于当前源点时刻 dist[u]。因此任何后续状态的时间都大于当前状态堆中弹出的顺序天然保证了时间单调性。即使边权不满足经典定义但我们依然有“处理过的节点不可能被更晚状态更新得更早”的贪心性质。严格证明可以用归纳法已经弹出的节点集合 S它们的 dist 已经达到全局最优下一步从堆中取出的最小 dist 节点其值不可能再被 S 外的节点优化因为 S 外节点的 dist 都至少等于它且任何转移只会让时间变大。所以放心大胆用 Dijkstra。要注意的是同一个节点可能被多次压入堆中因此弹出时一定要用 vis 数组或者判断堆中记录是否等于当前 dist 来去重。2.3 复杂度分析与优化空间先看时空复杂度。每个节点只会在第一次以最小 dist 弹出时被处理一次之后不会再参与出边松弛。每条边至多被其起点节点扫描一次因此边的遍历总复杂度是 O(m)。优先队列的每次插入和弹出都是 O(log n)总的堆操作次数不超过 m n 的量级。整体时间复杂度为 O((n m) log n)空间复杂度为 O(n m)。这个复杂度已经非常优秀一般情况下不需要额外优化。但有一个细节值得注意如果你在 Dijkstra 内对每个节点的出边按离站时刻排序然后使用二分查找并不会降低复杂度反而会多出排序的 O(m log m) 开销。因为我们的松弛条件是扫完所有出边而不是只找一条边。为什么不能只找一条离站时刻最近的边因为不同航线的到站时刻差异很大。举例来说当前时刻是 10有一条航线 10 点出发、20 点到达另一条航线 11 点出发、12 点到达。离站时刻最近的是第一条但最优明显是第二条。所以必须比较所有满足 dist[u] ≤ s 的边取最小的 t。因此本题的优化空间不在出边排序上而在 Dijkstra 堆的常数实现。如果你用priority_queuepairlong long,int实现记得用greater转成小根堆或者用pair的负号技巧否则会把最大时刻当最先处理结果全部错乱。3. 代码实现与细节讲解3.1 数据结构与邻接表我习惯用结构体存边然后按起点建邻接表。结构体里只需要终点 v、离站时刻 s、到站时刻 t。由于 s 和 t 可能非常大建议全部用long long别用int省空间等溢出时哭都来不及。#include bits/stdc.h using namespace std; struct Edge { int v; long long s, t; }; const long long INF 4e18; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; vectorvectorEdge g(n 1); for (int i 0; i m; i) { int u, v; long long s, t; cin u v s t; g[u].push_back({v, s, t}); } vectorlong long dist(n 1, INF); priority_queuepairlong long, int, vectorpairlong long, int, greaterpairlong long, int pq; dist[1] 0; pq.push({0, 1}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (d ! dist[u]) continue; // 跳过过期状态 if (u n) break; // 已经到终点可以提前退出 for (const auto e : g[u]) { if (d e.s) continue; // 错过这班航线 if (e.t dist[e.v]) { dist[e.v] e.t; pq.push({dist[e.v], e.v}); } } } if (dist[n] INF) cout -1 \n; else cout dist[n] \n; return 0; }这段代码就是整个题目的核心不到五十行。你可能会觉得它和普通 Dijkstra 太像了甚至有点不像“压轴题”。但实际比赛里的难点往往不是代码而是你能不能从一堆背景故事里看出它是这个模型。3.2 核心循环的逐行解释我们一行一行来看。pq里存的是 pair第一维是时刻第二维是节点编号。因为我们要按时刻从小到大取所以用greater定义小根堆。d是弹出时记录的时刻u是当前节点。if (d ! dist[u]) continue;这一步非常重要。在 Dijkstra 中同一个节点可能会被优先队列压入多次比如一开始 dist 是 100后来又发现有一条路径到达时间为 80于是把 80 再次压入。当堆顶弹出 100 时它已经过期了必须跳过否则会用错误的时间去松弛出边。for (const auto e : g[u])枚举的是从 u 出发的所有航线。d e.s表示你已经错过了这班航线的离站时刻直接跳过。注意这里不是d e.s因为如果恰好相等你还可以在上船前一瞬间赶上条件应该是d e.s。e.t dist[e.v]是标准松弛。如果乘坐这条航线能比当前记录的到达时间更早就更新并压入堆。整个过程没有任何特殊魔法纯粹是 Dijkstra 的变体。3.3 记录路径与前驱的扩展如果题目不仅要求最早到达时刻还要求输出经过的航线方案那就需要在松弛时记录前驱。因为这里的“状态”是节点而“转移”是某一条具体的航线所以不能只记pre[v] u还要记pre_edge[v] e或者直接记录航线编号。我在实现时会给每条边加一个id字段代表输入序号。松弛成功时除了更新 dist还设置pre[v] u; pre_edge_id[v] e.id;最后从 n 往前回溯可以得到一条节点序列。但由于我们跳过了错过航线的边所以回溯得到的路径一定满足时间顺序不需要额外检查。如果你还想输出每个节点“什么时候出发、什么时候到达”可以在回溯后从起点正向推一遍用 dist[cur] 和边上的 s、t 就能算出来。这里要注意的是终点可能有多个相同的最早到达时间Dijkstra 只记录了一条可行路径。题目如果要求任意方案完全没问题如果要求字典序最小路径那需要在松弛时处理严格大小关系并且优先队列的排序要加上路径字典序信息复杂度会高一些。目前主流 OI 题很少这么刁难人但多留个心眼总没错。3.4 边界情况无法到达与 INF最容易被忽略的边界情况是“起点就是终点”。如果 n 1答案应该是 0不需要坐任何航线。代码里 dist[1] 初始为 0while 循环中弹出 1 后会直接 break因为判断了u n所以输出 0正确。另一个边界是图中存在孤立点或者从 1 出发的所有航线都无法到达 n。此时 dist[n] 始终保持 INF。因为题目没说保证有解所以输出 -1。很多人会把 INF 设置成0x3f3f3f3f但这里时刻可能到 1e18必须用4e18之类的值并且加法时要小心。再有一个坑是重复输入的同一条航线。如果两条航线起点终点相同、离站时刻相同、到站时刻不同我们应该保留到站时刻更小的那一条吗不必要因为 Dijkstra 会扫描所有边哪条更优自然会把 dist 更新得更小。所以去重不会影响正确性只影响常数。如果你看到 m 很大且重复严重可以考虑用 map 压一压但一般用不着。4. 常见坑、测试技巧与扩展思考4.1 我踩过的三个坑第一个坑没有判d ! dist[u]。我一开始写的是if (vis[u]) continue;加上 vis 数组。理论上也可以但有一个隐患如果你在第一次弹出 u 时把 vis[u] 置为 true后面即使堆里出现一个更小的 dist[u]这是不可能的因为第一次弹出已经是最小也会被跳过。事实上 Dijkstra 中第一次弹出的 dist[u] 一定是最小所以 vis 方案正确。但用d ! dist[u]更通用尤其是在某些带删边或动态修改的场景里不容易写错。第二个坑long long溢出。我有一版代码把 s 和 t 都用int存结果数据一大t 加了某个偏移后溢出成负数然后 Dijkstra 的堆序变得一团糟。从那以后凡是和“时间”有关的变量我统一用long long不省那点内存。第三个坑把d e.s写成了d e.s。题目里只要你在离站时刻前或恰好到站就能坐。恰好到站意味着你前脚到站后脚该航线发车这在现实中也很常见不应算错过。改成一个等号就能让边界数据顺利通过。4.2 怎么构造对拍数据这种题最常见的错误不是算法错误而是细节写错导致个别数据 WA。我建议自己写一个爆搜程序来对拍。爆搜只需处理 n ≤ 8、m ≤ 15 的小数据枚举所有可能坐的航线记录到达 n 的最早时刻。对拍时随机生成数据注意保证每条边的 t s。我一般生成两三条从 1 到 n 的路径再随机加一些环和死路。然后分别用爆搜和 Dijkstra 跑比较输出。只要随机上千组不出差异基本就能放心交。我还喜欢专门构造几种刁钻数据起点到终点有多条路径但最早那条路径上有一个节点需要长时间等待另一条路径虽然航线时间更长但总到达时间反而更早再来一条“错过关键航线就永远到不了”的数据用来验证跳过边是否会影响后续路径。这些数据能帮你快速暴露问题。4.3 从这题还能学到什么这道题本质上是一个“时间依赖最短路”的入门模型。它比普通最短路多了一层“等待”的语义但依然可以用 Dijkstra 解决因为时间只会向前走。如果哪天你遇到了“边权是当前时间的函数”的更复杂题目比如班次密度随时间变化、等待时间有上限、或者同一条线路在不同时间段价格不同那么 Dijkstra 就不一定直接适用了可能需要把时间离散化、拆点或者用线段树维护转移。我在实际写这道题时最深的感受是竞赛题目往往喜欢把一件简单的事情包装得很科幻。你只要剥掉“彼时蓝星”这层外衣看到的仍然是熟悉的最短路。反过来说如果你只背板子不会变形遇到这种题就会觉得无从下手。多想一想“这个状态能不能用 Dijkstra 维护”比多刷十道模板题更有用。最后分享一个小技巧在比赛里如果推不出来转移方程可以先试着把所有“时间点”当作事件排序看看能不能用扫描线维护。本题的航班事件天然有序Dijkstra 的优先队列其实就是一种动态扫描线。理解了这一点你再看类似的“最早/最晚时间到达”题目思路会通畅许多。
