GESP 题解库 / 8 级题解 / [GESP202609 八级] 末班车 · 第 24 / 24 题
GESP202609 八级 · P17462 · 困难

末班车可达性判定

倒着算"最晚可行出发时刻" L(u, v),再做 n 次"最大化瓶颈"Dijkstra,询问 O(1)。

🚇
n ≤ 500, m ≤ 1000
地铁站与线路数
❓
q ≤ 5 × 10⁵
询问次数(必须 O(1))
⏱️
l, s ≤ 10⁵,t ≤ 10⁴
时刻与行驶时间
🎯
n 次瓶颈 Dijkstra
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

(GESP202609 八级)城市里有 n 个地铁站以及 m 条地铁线路,地铁站依次以 1, 2, … , n 编号。

第 i 条地铁线路(1 ≤ i ≤ m)的列车从地铁站 uᵢ 单向驶向地铁站 vᵢ,最晚发车时间为第 lᵢ 分钟,途中行驶需要 tᵢ 分钟。从第 0 分钟到第 lᵢ 分钟,每分钟都会有一班列车从地铁站 uᵢ 发出。第 x 分钟(0 ≤ x ≤ lᵢ)发出的列车会在第 x + tᵢ 分钟到达地铁站 vᵢ,乘坐这班列车的乘客可以换乘第 x + tᵢ 分钟以及之后的所有从地铁站 vᵢ 发出的任意线路的列车。

现在有 q 组询问。第 i 组询问给出起点 xᵢ、终点 yᵢ 以及出发时间 sᵢ,你需要判断第 sᵢ 分钟从地铁站 xᵢ 出发是否能到达地铁站 yᵢ。第 sᵢ 分钟从 xᵢ 出发意味着你可以乘坐第 sᵢ 分钟以及之后的所有从 xᵢ 发出的任意线路的列车。

输入格式:第一行三个正整数 n, m, q;接下来 m 行每行四个整数 uᵢ, vᵢ, lᵢ, tᵢ;接下来 q 行每行三个整数 xᵢ, yᵢ, sᵢ。

输出格式:输出共 q 行。能到达则输出一行 Yes,否则输出一行 No(请注意大小写)。

数据范围:

项目限制
站点数1 ≤ n ≤ 500
线路数1 ≤ m ≤ 1000
询问数1 ≤ q ≤ 5 × 10⁵
最晚发车 / 出发时刻0 ≤ lᵢ, sᵢ ≤ 10⁵
行驶时间1 ≤ tᵢ ≤ 10⁴
部分分40% 的测试点保证 q ≤ 100
💡
人话翻译:每条线路"只要你在最晚发车时间 lᵢ 之前到站,就有车可坐",坐上去花 tᵢ 分钟到终点,到得越早、后面能赶上的车就越多。
问 q = 5 × 10⁵ 次"第 s 分钟从 x 出发能到 y 吗",每次单独跑图必然超时。
关键观察:"能到达"这件事关于出发时间单调——出发越早越有利(大不了在原地等一会儿再按原计划走)。
所以对每一对 (u, v),只要求出"最晚还能赶得上到达 v 的出发时刻" L(u, v),询问就退化成 O(1) 的一次比较:s ≤ L(x, y) 就是 Yes。

🔍 关键词提取

逆向 DP最晚可行出发时刻答案关于出发时间单调最大化瓶颈 Dijkstra反图建模询问 O(1)

已知条件

项目说明
输入第一行 n, m, q;随后 m 行 (u, v, l, t) 单向线路;随后 q 行 (x, y, s)
输出每条询问一行 Yes / No
发车规律第 0…lᵢ 分钟每分钟一班,第 x 班在 x + tᵢ 到达
换乘规则到达时刻 T 可乘"T 分钟及之后"从该站发出的任意线路
规模n ≤ 500,m ≤ 1000,q ≤ 5 × 10⁵

需要解决的问题

02
思维导图
整理解题思路的全貌
🚇 倒推最晚出发时刻 L(u, v)
🧠 核心刻画
L(u, v) = 从 u 最晚何时出发还能到 v
出发越早越有利 → 可行集是前缀
询问 (x, y, s):Yes ⟺ s ≤ L(x, y)
L(v, v) = +∞
🔁 递推关系
看从 u 出发的第一条线路 i
能坐上它要求 τ ≤ lᵢ
到达后要求 τ + tᵢ ≤ L(vᵢ, v)
L(u, v) = max min(lᵢ, L(vᵢ, v) − tᵢ)
⚙️ 计算方法
建反图:按"终点"归拢线路
对每个目标 v 单独跑一次
大根堆做"最大化瓶颈"的 Dijkstra
每次弹出即最终值
⚠️ 易错点
INF 要够大(如 2 × 10⁹),别用 1e9 边界
不可达初始值别用 0
每个询问单独跑图必超时
输出大小写 Yes / No
03
样例手算推导
样例的 L 表完整推演 + 5 条询问逐条核对

🧮 样例:先把 L 表算出来

样例输入:

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

期望输出 Yes / Yes / No / Yes / No。四条线路是:

编号线路最晚发车 l行驶时间 t含义
11 → 233第 0…3 分钟各有一班,坐 3 分钟到 2
22 → 352第 0…5 分钟各有一班,坐 2 分钟到 3
33 → 141第 0…4 分钟各有一班,坐 1 分钟到 1
41 → 306只有第 0 分钟那一班,坐 6 分钟到 3

目标 v = 1:倒推 L(·, 1)

1
起点:L(1, 1) = +∞

目标就是 1,从 1 出发随时都算"到达"

把 +∞(实现取 2 × 10⁹)放进大根堆

✅ L(1, 1) = +∞

2
用"终点为 1"的线路松弛:线路 3(3 → 1, l = 4, t = 1)

cand = min(l, L(1, 1) − t) = min(4, +∞ − 1) = 4

含义:只要在 3 站最晚第 4 分钟出发,

就能赶上 3→1 的末班车(第 4 分钟那班),第 5 分钟到 1

于是 L(3, 1) = 4

✅ L(3, 1) = 4

3
继续松弛:线路 2(2 → 3, l = 5, t = 2)

cand = min(5, L(3, 1) − 2) = min(5, 4 − 2) = 2

含义:从 2 站最晚第 2 分钟出发,坐 2→3 第 2 分钟那班,第 4 分钟到 3,

正好赶上 3→1 第 4 分钟的末班车,第 5 分钟到 1

于是 L(2, 1) = 2

✅ L(2, 1) = 2

4
线路 1(1 → 2, l = 3, t = 3)能更新吗?

cand = min(3, L(2, 1) − 3) = min(3, 2 − 3) = −1

−1 说明"就算从 1 直接到 2,也来不及接着去 1 了"

L(1, 1) 已是 +∞,不更新

✅ 该线路对这个目标无贡献

目标 v = 2 与 v = 3:同样倒推

目标 v松弛过程(从大到小)得到的 L 列
v = 2L(2, 2) = +∞ → 线路 1 给 L(1, 2) = 3 → 线路 3 给 L(3, 2) = 2L(1, 2) = 3,L(3, 2) = 2,L(2, 2) = +∞
v = 3L(3, 3) = +∞ → 线路 2 给 L(2, 3) = 5、线路 4 给 L(1, 3) = 0 → 线路 1 把 L(1, 3) 提升到 2L(2, 3) = 5,L(1, 3) = 2,L(3, 3) = +∞

汇总成 L 表(+∞ 表示起点即终点)

出发站 u \ 目标 vv = 1v = 2v = 3
u = 1+∞(自身)32
u = 22+∞(自身)5
u = 342+∞(自身)

5 条询问逐条核对

询问 (x, y, s)查表 L(x, y)比较 s ≤ L(x, y)输出
(1, 3, 2)L(1, 3) = 22 ≤ 2 ✓Yes
(2, 1, 2)L(2, 1) = 22 ≤ 2 ✓Yes
(2, 1, 3)L(2, 1) = 23 ≤ 2 ✗No
(3, 2, 2)L(3, 2) = 22 ≤ 2 ✓Yes
(3, 2, 3)L(3, 2) = 23 ≤ 2 ✗No

Yes / Yes / No / Yes / No ✓

🔑
顺手验一条:第 1 条询问 (1, 3, 2) 为什么是 Yes?
第 2 分钟从 1 出发,坐 1→2 第 2 分钟那班(2 ≤ l = 3),第 2 + 3 = 5 分钟到 2;再坐 2→3 第 5 分钟那班(正好是末班车,5 ≤ l = 5),第 7 分钟到 3。
而第 3 分钟出发就来不及了:3 + 3 = 6 > 5,赶不上 2→3 的末班车。所以 L(1, 3) = 2 分毫不差。

🧮 为什么"越早出发越有利",以及递推式的来历

这两件事只要想明白,整道题的算法就"掉"出来了。

1
第 1 步:可行出发时刻构成一个前缀

设从 u 在时刻 τ 出发能到 v。

取任意 τ′ < τ:先在 u 站等到第 τ 分钟,

之后完全照搬 τ 时刻出发的那套行程

(等待不消耗任何资源,题目允许"乘 s 分钟以及之后"的所有车),

所以 τ′ 也一定能到 v

于是可行集合 = { τ : τ ≤ L(u, v) },是一个前缀

✅ 用一个最大可行值就能刻画全部

2
第 2 步:递推式的推导

从 u 出发的第一段一定坐某条线路 i(uᵢ = u):

① 能坐上:需要 τ ≤ lᵢ;

② 坐上后第 τ + tᵢ 分钟到 vᵢ;

③ 站到 vᵢ 之后还得能到 v:需要 τ + tᵢ ≤ L(vᵢ, v);

把 ① ③ 合并:τ ≤ min(lᵢ, L(vᵢ, v) − tᵢ)

对所有以 u 为起点的线路取最大,即得 L(u, v)

✅ L(u, v) = max min(lᵢ, L(vᵢ, v) − tᵢ)

3
第 3 步:为什么能用"大根堆 Dijkstra"算

候选函数 f(x) = min(l, x − t) 关于 x 单调不减:

L(vᵢ, v) 越大,算出来的候选值只会更大、不会更小

所以"先确定当前 L 值最大的点,再用它去松弛别人"是安全的

(这和"最大瓶颈路"是同一类结构,Dijkstra 正确)

每个点第一次被弹出时,它的值就是最终值

✅ 对每个目标 v 跑一次即可

视角状态含义转移用途
正向"最早到达"earliest[u] = 最早到 u 的时刻earliest[v] = min(earliest[v], earliest[u] + t)(要求 earliest[u] ≤ l)单次询问(O(m log n) 一次)
逆向"最晚出发"L(u, v) = 最晚从 u 出发还能到 v 的时刻L(u, v) = max min(l, L(vᵢ, v) − t)预处理一次,询问 O(1)
🎯
为什么必须"逆向 + 预处理"?正向做法一次询问要跑一整张图,q = 5 × 10⁵ 次就是 5 × 10⁵ × 1500 ≈ 7.5 × 10⁸,必然 TLE。
而逆向做法把"所有起点、所有终点"的信息一次性榨干:n × n = 2.5 × 10⁵ 个 L 值,总代价 O(n(n + m) log n) ≈ 7 × 10⁶,之后每条询问只查一次表。
这就是"把询问的代价转移到预处理"的典型手段。
⚠️
关于 x == y:此时查表得到 L(y, y) = +∞,而所有合法出发时刻都满足 s ≤ 10⁵ < 2 × 10⁹,所以 s ≤ L(x, y) 天然成立,答案就是 Yes。
也就是说:只要 INF 取得比 10⁵ 大,同一句判断就能覆盖自环情形;不过很多题解仍会显式写一句 if (x == y) Yes;,这样逻辑更清楚,也避免 INF 取值偏小带来的隐患。
04
解法对比
逆向 n 次瓶颈 Dijkstra vs 每个询问正向跑图 vs 朴素模拟

⚔️ 解法对比

🟢 逆向预处理 L 表(推荐) 推荐

对每个终点 v 倒推一遍"最晚可行出发时刻",询问时只比较 s 与 L(x, y)

  • 预处理 O(n(n + m) log n)
  • 询问 O(1)
  • 空间 O(n² + m)
  • 约 7 × 10⁶ 次操作,稳过
💡
它的本质:把"能不能到"翻译成"最晚何时出发",于是 q 条询问共享同一份预处理结果。
关键前提是出发点时间单调性——没有它,就不可能用单个数值 L 概括一整段可行区间。

🟠 每条询问正向跑一次图

对 (x, y, s) 求一次"最早到达"时间,判断是否可达 y

  • 单次 O(m log n)
  • q = 5 × 10⁵ 次 → 7.5 × 10⁸
  • q ≤ 100 时可行
  • q 大时必超时
⚠️
它能拿多少分:只能过 q ≤ 100 的 40% 部分分。
思路是对的,但把"重复劳动"留在了询问里,这正是需要用"预处理"消灭的成本。

📈 性能对比

方案复杂度结论
逆向预处理 + O(1) 询问O(n(n + m) log n) 预处理,O(1) 询问✅ 正解,能拿满分
每条询问正向跑图O(q · m log n) ≈ 7.5 × 10⁸⚠️ 只有 40 分
朴素按分钟模拟状态与时刻范围成正比,巨大❌ 完全不可行
05
算法流程图
对每个目标 v 倒推 L(·, v):主流程
开始读入 n, m, q 与 m 条单向线路 (u, v, l, t)建反图:把每条线路按"终点 v"归拢起来本轮目标 v:L(v, v) = +∞,其余 L(w, v) = 不可达;( +∞, v ) 入大根堆堆空了吗?没空 ✓弹出当前 L 最大的点空了 ✗本目标算完对每条"终点为 u"的线路:cand = min(l, L(u, v) − t),更优则更新并入堆n 个目标都算完了吗?逐条询问:x == y 或 s ≤ L(x, y) 输出 Yes,否则输出 No继续弹出下一个点
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🚇 末班车可达性判定器

第一行输入 n m q,随后 m 行线路 u v l t,最后 q 行询问 x y s。程序倒推 L 表并逐条判定。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码(逆向预处理 L 表 + O(1) 询问)

#include <bits/stdc++.h>
using namespace std;

const int INF = 2000000000;          // 必须远大于最大合法出发时刻 1e5

int main() {
    int n, m, q;
    scanf("%d %d %d", &n, &m, &q);

    // 反图:radj[v] 存所有"终点为 v"的线路 (起点 u, 最晚发车 l, 行驶时间 t)
    vector<vector<pair<int, pair<int, int> > > > radj(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v, l, t;
        scanf("%d %d %d %d", &u, &v, &l, &t);
        radj[v].push_back(make_pair(u, make_pair(l, t)));
    }

    // L[goal][u] = 目标为 goal 时,从 u 出发还能到达 goal 的最大可行出发时刻
    vector<vector<int> > L(n + 1, vector<int>(n + 1, -1));
    for (int goal = 1; goal <= n; goal++) {
        vector<int>& cur = L[goal];
        cur[goal] = INF;                         // 起点即终点:随时可"到达"
        priority_queue<pair<int, int> > pq;      // 大根堆,按 L 值排序
        pq.push(make_pair(INF, goal));

        while (!pq.empty()) {
            int d = pq.top().first;
            int u = pq.top().second;
            pq.pop();
            if (d < cur[u]) continue;            // 过期项,跳过

            for (int k = 0; k < (int)radj[u].size(); k++) {
                int w  = radj[u][k].first;             // 这条线路的起点
                int l  = radj[u][k].second.first;      // 最晚发车时间
                int t  = radj[u][k].second.second;     // 行驶时间
                int cand = d - t;                      // 到达后必须在 L(u, goal) 之前出发
                if (cand > l) cand = l;                // 还要赶得上末班车 l
                if (cand > cur[w]) {
                    cur[w] = cand;
                    pq.push(make_pair(cand, w));
                }
            }
        }
    }

    while (q--) {
        int x, y, s;
        scanf("%d %d %d", &x, &y, &s);
        if (x == y || s <= L[y][x]) puts("Yes");   // 一次比较,O(1)
        else                        puts("No");
    }
    return 0;
}
🔑
两行核心:① int cand = d - t; if (cand > l) cand = l;就是 min(lᵢ, L(vᵢ, v) − tᵢ);② if (cand > cur[w]) cur[w] = cand;就是在所有"第一段线路"里取最大值。
把它们套进大根堆 Dijkstra 的骨架里,就得到了"最晚出发时刻"的完整算法。

📖 关键几行怎么看

代码作用为什么这样写
radj[v].push_back(…)建反图倒推时要用"以某点为终点"的线路集合
cur[goal] = INF;边界条件L(v, v) = +∞:从 v 出发想到 v 随时都行
vector<int>(n + 1, −1)不可达初值−1 < 0 ≤ s,所以"没被更新过"就自然是 No
priority_queue<pair<int, int> >最大堆默认是大根堆,每次弹出当前 L 值最大的点
if (cand > l) cand = l;瓶颈限制既受"末班车 l"限制,又受"后续可达性"限制,取较小者
if (x == y || s <= L[y][x])O(1) 询问所有预处理都只做一次,询问只做一次比较
⚠️
五个坑:① INF 取太小(如 10⁵),会让 INF − t 算出偏小的候选值——建议取 2 × 10⁹;② 不可达初值写成 0,在 s = 0 时会被误判成可达(要用 −1 这类负值);③ 忘了写"过期项跳过"if (d < cur[u]) continue;,会做很多无用松弛(虽然不错,但会慢);④ 每条询问单独跑图——q = 5 × 10⁵ 时必超时;⑤ 输出写成 YES / NO(题目要求 Yes / No,区分大小写)。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
3 4 5
1 2 3 3
2 3 5 2
3 1 4 1
1 3 0 6
1 3 2
2 1 2
2 1 3
3 2 2
3 2 3
Yes
Yes
No
Yes
No
题面样例:L 表见上一节的推演
2 1 1
1 2 5 3
2 2 0
Yesx == y:起终点相同,恒为 Yes
2 1 2
1 2 5 3
1 2 5
1 2 6
Yes
No
恰好赶上末班车 Yes;晚一分钟 No(L = 5)
3 1 1
1 2 9 1
1 3 0
No线路够不到终点站:L 始终不可达
3 2 3
1 2 5 5
2 3 10 5
1 3 5
1 3 6
1 3 0
Yes
No
Yes
必须换乘:s = 5 刚好赶上,s = 6 就晚了
2 1 2
1 2 0 1
1 2 0
1 2 1
Yes
No
l = 0:只有第 0 分钟那一班(L = 0)
✅
自查清单:① 是"最晚出发"而不是"最早到达"吗?② 递推里是 min(l, L(vᵢ, v) − t) 吗?③ L(v, v) = +∞、不可达用负值初始化了吗?④ 询问是 O(1) 比较吗?

🚨 易错点清单

⚠️
INF 取太小:INF − t 会算出偏小的候选值,建议取 2 × 10⁹(远大于 l, s ≤ 10⁵)。
⚠️
不可达初值设成 0:s = 0 时 0 ≤ 0 会被误判为可达,初值要用 −1 这类严格小于 0 的数。
⚠️
每条询问单独跑图:q = 5 × 10⁵ 时约 7.5 × 10⁸ 次操作,必须改成"预处理 L 表 + O(1) 询问"。
⚠️
输出大小写:题目要求 Yes / No,写成 YES / NO 会被判错。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(n(n + m) log n)
空间复杂度
O(n² + m)
单次询问
O(1) 一次比较
最坏运算量
约 7 × 10⁶

时间怎么算的?

空间都用在哪?

最大的一块是 L 表:n × n = 25 × 10⁴ 个 int,约占 1 MB;反图存 m 条线路,再加一个堆(O(n) 量级)。总空间 O(n² + m)。

✅ n ≤ 500 这个上限不是偶然的——它正好允许我们大方地开一张 n × n 的表。"用空间换时间,把询问降到 O(1)"是这道题的核心取舍。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 「状态值关于某参数单调 -> 预处理成 O(1) 询问」通用思路
// 本题的单调性:出发越早越有利  ->  可行集合是 { τ ≤ L }
//
// 递推(逆向):L(v, v) = +INF
//               L(u, v) = max over 线路 i (u_i = u) of  min(l_i, L(v_i, v) - t_i)
//
// 为什么能 Dijkstra:候选函数 f(x) = min(l, x - t) 关于 x 单调不减
//                    -> 先固定"当前 L 最大"的点是安全的(最大化瓶颈)
//
// 实现要点:
priority_queue<pair<int,int> > pq;      // 大根堆
cur[goal] = INF; pq.push({INF, goal});
while (!pq.empty()) {
    int d = pq.top().first, u = pq.top().second; pq.pop();
    if (d < cur[u]) continue;                     // 过期项
    for (每条以 u 为终点的线路 (w, l, t)) {        // 反图
        int cand = d - t;
        if (cand > l) cand = l;                   // min(l, L - t)
        if (cand > cur[w]) { cur[w] = cand; pq.push({cand, w}); }
    }
}
// 询问: x == y || s <= L[y][x]   ->  Yes / No

// 逆向对照:正向"最早到达"(一次询问一张图)
// earliest[v] = min(earliest[v], earliest[u] + t),且要求 earliest[u] <= l

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
单调性刻画可行出发时刻是一个前缀,用最大值 L 概括"参数越大越有利(或越不利)"的一切判定题
逆向递推从目标出发倒推"最晚可行出发时刻"倒推方案是否可行、倒推截止时间类问题
最大化瓶颈瓶颈 = min(l, L − t),用大根堆逐点固定最大瓶颈路、最大最小比值路径、容量类最优化
空间换时间预处理 n × n 的表,把 q 条询问降成 O(1)询问极多而状态空间小的判定题
🌟
思考题:如果题目反过来问"第 s 分钟从 x 出发,最早什么时候能到 y",上面这套"逆向 L 表"还好用吗?(提示:不好用。L 只记录了"能不能到",丢掉了时间信息;此时要么对每条询问正向跑一次"最早到达"(q 小时可行),要么反过来对每个起点 x 预处理"到达各点的最早时间函数"——但由于它依赖于出发时刻 s,一般只能做成分段的一次函数,复杂度会显著上升。所以"问可达性"能用 O(1) 表格解决,"问最早到达时刻"往往就得另想办法——这正是本题选择"倒推最晚出发"这一角度的精妙之处。)