倒着算"最晚可行出发时刻" L(u, v),再做 n 次"最大化瓶颈"Dijkstra,询问 O(1)。
(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⁵ |
τ 分钟出发能到达 v,那么第 τ′ < τ 分钟出发也一定能:只需先在起点站等到第 τ 分钟,再照搬原来那套行程。所以可行出发时刻一定是一个形如"≤ L"的前缀,用一个最大的可行出发时刻 L 就能完全刻画L(u, v) 的递推式长什么样?考虑从 u 出发坐的第一条线路 i(要求 uᵢ = u):要能坐上它,需要 τ ≤ lᵢ;坐上后第 τ + tᵢ 分钟到 vᵢ,还要求"从 vᵢ 于 τ + tᵢ 出发能到 v",即 τ + tᵢ ≤ L(vᵢ, v)。合并得 τ ≤ min(lᵢ, L(vᵢ, v) − tᵢ),对所有从 u 出发的线路取最大值L(v, v) = +∞:从 v 出发想到 v,任何时候都可以(原地不动即到达)。其余点初始化为"不可达",实现里用 −1 这种小于任何合法出发时间的值即可n 个目标各自的 L(·, v) 全部预处理出来(共 n × n 个值),之后每条询问只做一次 s ≤ L(x, y) 的判断样例输入:
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 | 含义 |
|---|---|---|---|---|
| 1 | 1 → 2 | 3 | 3 | 第 0…3 分钟各有一班,坐 3 分钟到 2 |
| 2 | 2 → 3 | 5 | 2 | 第 0…5 分钟各有一班,坐 2 分钟到 3 |
| 3 | 3 → 1 | 4 | 1 | 第 0…4 分钟各有一班,坐 1 分钟到 1 |
| 4 | 1 → 3 | 0 | 6 | 只有第 0 分钟那一班,坐 6 分钟到 3 |
目标就是 1,从 1 出发随时都算"到达"
把 +∞(实现取 2 × 10⁹)放进大根堆
✅ L(1, 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
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
cand = min(3, L(2, 1) − 3) = min(3, 2 − 3) = −1
−1 说明"就算从 1 直接到 2,也来不及接着去 1 了"
L(1, 1) 已是 +∞,不更新
✅ 该线路对这个目标无贡献
| 目标 v | 松弛过程(从大到小) | 得到的 L 列 |
|---|---|---|
| v = 2 | L(2, 2) = +∞ → 线路 1 给 L(1, 2) = 3 → 线路 3 给 L(3, 2) = 2 | L(1, 2) = 3,L(3, 2) = 2,L(2, 2) = +∞ |
| v = 3 | L(3, 3) = +∞ → 线路 2 给 L(2, 3) = 5、线路 4 给 L(1, 3) = 0 → 线路 1 把 L(1, 3) 提升到 2 | L(2, 3) = 5,L(1, 3) = 2,L(3, 3) = +∞ |
+∞ 表示起点即终点)| 出发站 u \ 目标 v | v = 1 | v = 2 | v = 3 |
|---|---|---|---|
| u = 1 | +∞(自身) | 3 | 2 |
| u = 2 | 2 | +∞(自身) | 5 |
| u = 3 | 4 | 2 | +∞(自身) |
| 询问 (x, y, s) | 查表 L(x, y) | 比较 s ≤ L(x, y) | 输出 |
|---|---|---|---|
| (1, 3, 2) | L(1, 3) = 2 | 2 ≤ 2 ✓ | Yes |
| (2, 1, 2) | L(2, 1) = 2 | 2 ≤ 2 ✓ | Yes |
| (2, 1, 3) | L(2, 1) = 2 | 3 ≤ 2 ✗ | No |
| (3, 2, 2) | L(3, 2) = 2 | 2 ≤ 2 ✓ | Yes |
| (3, 2, 3) | L(3, 2) = 2 | 3 ≤ 2 ✗ | No |
Yes / Yes / No / Yes / No ✓
(1, 3, 2) 为什么是 Yes?2 ≤ l = 3),第 2 + 3 = 5 分钟到 2;再坐 2→3 第 5 分钟那班(正好是末班车,5 ≤ l = 5),第 7 分钟到 3。3 + 3 = 6 > 5,赶不上 2→3 的末班车。所以 L(1, 3) = 2 分毫不差。这两件事只要想明白,整道题的算法就"掉"出来了。
设从 u 在时刻 τ 出发能到 v。
取任意 τ′ < τ:先在 u 站等到第 τ 分钟,
之后完全照搬 τ 时刻出发的那套行程
(等待不消耗任何资源,题目允许"乘 s 分钟以及之后"的所有车),
所以 τ′ 也一定能到 v
于是可行集合 = { τ : τ ≤ L(u, v) },是一个前缀
✅ 用一个最大可行值就能刻画全部
从 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ᵢ)
候选函数 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 取值偏小带来的隐患。对每个终点 v 倒推一遍"最晚可行出发时刻",询问时只比较 s 与 L(x, y)
O(n² + m)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 分 |
| 朴素按分钟模拟状态 | 与时刻范围成正比,巨大 | ❌ 完全不可行 |
第一行输入 n m q,随后 m 行线路 u v l t,最后 q 行询问 x y s。程序倒推 L 表并逐条判定。
点按钮开始 →
#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;就是在所有"第一段线路"里取最大值。| 代码 | 作用 | 为什么这样写 |
|---|---|---|
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,区分大小写)。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
3 4 5 | Yes Yes No Yes No | 题面样例:L 表见上一节的推演 |
2 1 1 | Yes | x == y:起终点相同,恒为 Yes |
2 1 2 | Yes No | 恰好赶上末班车 Yes;晚一分钟 No(L = 5) |
3 1 1 | No | 线路够不到终点站:L 始终不可达 |
3 2 3 | Yes No Yes | 必须换乘:s = 5 刚好赶上,s = 6 就晚了 |
2 1 2 | Yes No | l = 0:只有第 0 分钟那一班(L = 0) |
min(l, L(vᵢ, v) − t) 吗?③ L(v, v) = +∞、不可达用负值初始化了吗?④ 询问是 O(1) 比较吗?INF − t 会算出偏小的候选值,建议取 2 × 10⁹(远大于 l, s ≤ 10⁵)。s = 0 时 0 ≤ 0 会被误判为可达,初值要用 −1 这类严格小于 0 的数。q = 5 × 10⁵ 时约 7.5 × 10⁸ 次操作,必须改成"预处理 L 表 + O(1) 询问"。Yes / No,写成 YES / NO 会被判错。n 个目标各做一次 DijkstraO(n + m),每次堆操作 O(log n),即 O((n + m) log n)O(n(n + m) log n):500 × (500 + 1000) × 9 ≈ 7 × 10⁶,非常轻q ≤ 5 × 10⁵ 条,每条 O(1),合计 O(q)最大的一块是 L 表:n × n = 25 × 10⁴ 个 int,约占 1 MB;反图存 m 条线路,再加一个堆(O(n) 量级)。总空间 O(n² + m)。
✅ n ≤ 500 这个上限不是偶然的——它正好允许我们大方地开一张 n × n 的表。"用空间换时间,把询问降到 O(1)"是这道题的核心取舍。
// 「状态值关于某参数单调 -> 预处理成 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) 表格解决,"问最早到达时刻"往往就得另想办法——这正是本题选择"倒推最晚出发"这一角度的精妙之处。)