从学校出发只跑一次 Dijkstra,之后每位同学 O(1) 查表。
C 城可以视为由 n 个结点与 m 条边组成的无向图。这些结点依次以 1, 2, …, n 标号,第 i(1 ≤ i ≤ m)条边连接编号为 uᵢ 与 vᵢ 的两个结点,长度为 lᵢ 米。
小 A 的学校坐落在编号为 s 的结点。小 A 的同学们共有 q 位,第 i 位同学(1 ≤ i ≤ q)告诉小 A,他的家位于编号为 hᵢ 的结点,并且他每秒钟能行走 1 米。请你帮小 A 计算,每位同学从家出发需要多少秒才能到达学校。
| 样例 | 内容 |
|---|---|
| 输入 #1 | 5 5 3 3 |
| 输出 #1 | 4 |
s,可同学们的家有 q 个,各有各的位置。家 → 学校 的最短时间 = 学校 → 家 的最短时间。O(1) 出结果。无向带权图单源最短路堆优化 Dijkstra一次预处理 + O(1) 查询反向思考
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 n, m, s, q;随后 m 行 uᵢ, vᵢ, lᵢ;再随后 q 行 hᵢ |
| 输出 | 共 q 行,每行一个整数,表示该同学到学校的最短时间 |
| 数据范围 | 1 ≤ n, m, q ≤ 2 × 10⁵ |
| 边长范围 | 1 ≤ lᵢ ≤ 10⁶(全是正数) |
| 图的形态 | 无向图,允许重边(平行边) |
| 速度 | 1 米/秒 ⇒ 最短长度就是最短时间 |
q 次 Dijkstra 是 O(q(n + m) log n),最坏约 8 × 10¹⁰ 次操作,远超 1 秒能承受的范围;而且这 q 次算的其实是同一张表,重复计算毫无意义dist(s → h) = dist(h → s),反向建图都不需要lᵢ ≥ 1,边权全部为正,Dijkstra 的"每次取出距离最小的点即为定稿"成立,不需要 Bellman-Ford / SPFAn − 1 条边,每条 lᵢ ≤ 10⁶,最坏约 2 × 10¹¹,远超 int 的 2.1 × 10⁹样例的图共有 5 个结点、5 条边,学校在结点 3:
| 边 | 长度 | 备注 |
|---|---|---|
| 1 — 2 | 3 | |
| 2 — 3 | 2 | |
| 3 — 4 | 1 | |
| 4 — 5 | 3 | |
| 1 — 4 | 2 |
dist[1…5] 全部 = ∞
dist[3] = 0(学校自己到自己是 0 秒)
小根堆里压入 (0, 3)
准备出发
松弛 2:dist[2] = 0 + 2 = 2
松弛 4:dist[4] = 0 + 1 = 1
堆里现在是 (1, 4)、(2, 2)
dist[2] = 2,dist[4] = 1
松弛 1:dist[1] = 1 + 2 = 3
松弛 5:dist[5] = 1 + 3 = 4
松弛 3:结点 3 已定稿,跳过
堆里现在是 (2, 2)、(3, 1)、(4, 5)
dist[1] = 3,dist[5] = 4
松弛 1:2 + 3 = 5 比现在的 3 大,不更新
松弛 3:结点 3 已定稿,跳过
两个邻居都不需要更新
结点 1、结点 5 没有能再松弛的邻居
堆空,Dijkstra 结束
✅ 表算完了
| 结点 | 1 | 2 | 3(学校) | 4 | 5 |
|---|---|---|---|---|---|
| dist | 3 | 2 | 0 | 1 | 4 |
| 询问 | 同学的家 | 查表 dist[hᵢ] | 说明 |
|---|---|---|---|
| 1 | 5 | 4 | 5 → 4 → 3,长度 3 + 1 = 4 |
| 2 | 1 | 3 | 1 → 4 → 3,长度 2 + 1 = 3(比 1 → 2 → 3 的 5 短) |
| 3 | 4 | 1 | 4 → 3,长度 1 |
1 → 2 → 3 长 5,1 → 4 → 3 长 3。Dijkstra 自动取了最短的那条,这正是我们要的答案,而不是"边数最少"或"任意一条路"。题目问的是"家 → 学校",我们算的是"学校 → 家"。这两者凭什么相等?
无向图里 (u, v, l) 与 (v, u, l) 是同一条边
所以 家 → … → 学校 的结点序列倒过来写
就是 学校 → … → 家 的合法路径
两条路径的边完全一样,长度自然一样
✅ 两个方向的"路径集合"完全相同
既然路径集合相同,最短长度必然相同
dist(h → s) = dist(s → h)
所以我们算出 dist[s] 这张表
答案就是所有询问要的东西
✅ 一次 Dijkstra 覆盖全部询问
| 做法 | 最短路次数 | 最坏运算量 | 结论 |
|---|---|---|---|
| 每位同学各跑一次 | q ≤ 2 × 10⁵ 次 | 约 8 × 10¹⁰ | ❌ 超时 |
| 从学校跑一次 + 查表 | 1 次 | 约 7 × 10⁶ | ✅ 推荐 |
long long——m ≤ 2 × 10⁵、lᵢ ≤ 10⁶,最坏一条路径长约 2 × 10¹¹,用 int 会直接溢出成负数,答案全错;INF 要设得足够大——常见写法 INF = 1e9 比最短路还小,会让"不可达"和"可达"混在一起,建议写成 4e18。以学校为源点求单源最短路,之后每个询问直接查 dist[hᵢ]
dist(h → s) = dist(s → h);而 Dijkstra 在非负边权下给出的dist[s][v] 就是真正的最短距离。对每个 hᵢ 都以 hᵢ 为源点跑 Dijkstra,取 dist[s]
| 方案 | 复杂度 | 结论 |
|---|---|---|
| 从 s 跑一次 Dijkstra + 查表 | O((n + m) log n + q) | ✅ 推荐(官方做法) |
| 每个询问各跑一次 Dijkstra | O(q(n + m) log n) ≈ 8 × 10¹⁰ | ❌ 超时 |
| Floyd 全源最短路 | O(n³) ≈ 8 × 10¹⁵ | ❌ 完全不可行 |
第一行输入 n m s q,随后 m 行输入 u v l(无向边),再随后 q 行输入每位同学的家 h。程序会从学校 s 跑一次 Dijkstra,展示结点定稿顺序与每位同学的答案。
点按钮开始 →
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll INF = 4e18; // 最短路最长约 2e11,4e18 绝对够大 int n, m, s, q; vector<pair<int, ll> > g[200005]; // 邻接表:{到达点, 边长} ll dist_[200005]; // 避免与 std::distance 冲突,故意加下划线 int main() { scanf("%d %d %d %d", &n, &m, &s, &q); for (int i = 0; i < m; i++) { int u, v; ll l; scanf("%d %d %lld", &u, &v, &l); g[u].push_back(make_pair(v, l)); // 无向边:两个方向都要加 g[v].push_back(make_pair(u, l)); } // ---------- 从学校 s 出发跑一次堆优化 Dijkstra ---------- for (int i = 1; i <= n; i++) dist_[i] = INF; priority_queue<pair<ll, int>, vector<pair<ll, int> >, greater<pair<ll, int> > > pq; dist_[s] = 0; pq.push(make_pair(0, s)); while (!pq.empty()) { ll d = pq.top().first; int x = pq.top().second; pq.pop(); if (d > dist_[x]) continue; // 过期的记录,丢弃 for (int t = 0; t < (int)g[x].size(); t++) { int y = g[x][t].first; ll w = g[x][t].second; if (d + w < dist_[y]) { dist_[y] = d + w; pq.push(make_pair(dist_[y], y)); } } } // ---------- 每个询问 O(1) 查表 ---------- while (q--) { int h; scanf("%d", &h); if (dist_[h] >= INF) puts("-1"); // 兜底:数据保证连通时这行不会执行 else printf("%lld\n", dist_[h]); } return 0; }
INF 都用 long long,最坏距离约 2 × 10¹¹。| 代码 | 作用 | 为什么这样写 |
|---|---|---|
g[u].push_back(...); g[v].push_back(...); | 建图 | 无向边必须双向加,否则"家 → 学校"可能被当成不可达 |
dist_[s] = 0; pq.push(...); | 初始化源点 | 学校到自己是 0 秒,这是最短路算法的起点 |
if (d > dist_[x]) continue; | 丢弃过期记录 | 同一个点可能被压入多次,只处理最短的那次 |
if (d + w < dist_[y]) | 松弛 | 发现更短的路就更新,并入堆继续扩散 |
printf("%lld
", dist_[h]); | 回答询问 | 一次最短路换来的表,q 次 O(1) 查询 |
int;③ 无向边只加了一个方向;④ INF 取 1e9 太小;⑤ 变量名别叫 distance,会和 <bits/stdc++.h> 里的 std::distance 撞名(本代码用 dist_ 规避)。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
5 5 3 3 | 4 3 1 | 题面样例:5 → 4,1 → 3,4 → 1 |
2 1 1 2 | 0 5 | 第一个询问的家就是学校,答案是 0 |
3 3 1 2 | 2 1 | 绕路更近:1 → 3 → 2 只有 2,直连的 10 更贵 |
4 3 1 3 | 21 7 0 | 链上累加:距离随边数线性增长 |
2 2 1 2 | 3 0 | 重边(平行边):自动取短的那条 3 |
3 2 2 3 | 1000000 1000000 0 | 大边权:最坏总长约 2 × 10¹¹,必须 long long |
邻接表存 2m 条有向弧,约占 O(n + m);距离数组 long long dist_[n + 1] 占 O(n);小根堆最多同时存 O(m) 条记录。
✅ 一次最短路打底,之后全部 O(1) 查表,把 q 个询问的重复计算彻底消掉了,20 万规模的询问毫无压力。
// 「一次单源最短路 + 多次 O(1) 查询」通用模板 // 1) 读图:无向图记得两条方向都加边 void addEdge(int u, int v, ll w) { g[u].push_back(make_pair(v, w)); g[v].push_back(make_pair(u, w)); } // 2) 从固定源点跑一次最短路(边权非负 ⇒ 用堆优化 Dijkstra) void dijkstra(int src) { fill(dist + 1, dist + n + 1, INF); dist[src] = 0; priority_queue<pair<ll,int>, vector<pair<ll,int> >, greater<pair<ll,int> > > pq; pq.push(make_pair(0, src)); while (!pq.empty()) { ll d = pq.top().first; int x = pq.top().second; pq.pop(); if (d > dist[x]) continue; for (auto e : g[x]) if (d + e.second < dist[e.first]) { dist[e.first] = d + e.second; pq.push(make_pair(dist[e.first], e.first)); } } } // 3) 所有询问 O(1) 回答:读入询问后直接输出 dist[询问点] // 本题不需要反向建图,因为无向图的路径可逆 // 4) 变量命名不要用 distance / rank 之类与标准库重名的词 // (std::distance 会让编译报一堆看不懂的错)
把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。
| 能力点 | 本题怎么用 | 还能迁移到 |
|---|---|---|
| 一次预处理 + 多次查询 | 从学校跑一次,q 个询问查表 | 任意"静态图 + 大量询问"的题目 |
| 反向思考 | 家 → 学校 等价于 学校 → 家 | 无向图里把端点互换的提问方式 |
| 非负边权 ⇒ Dijkstra | 边长 ≤ 10⁶ 全为正,可以放心用堆 | 含 0 权可以用 Dijkstra,含负权必须换算法 |
| long long 防溢出 | 最坏距离 2 × 10¹¹ | 所有"边权 × 边数"可能超过 2 × 10⁹ 的题 |
| 重边自然处理 | 平行边都加进邻接表,取小的那条 | 有重边、自环的图论题 |
q 位同学,但道路会临时封闭(每次封锁一条边,封锁后再问)",一次 Dijkstra 还够用吗?(提示:不够了——图在变,预先算好的表就失效了。这类"带修改的最短路查询"要么每次重跑(q 小的时候可行),要么就要换更高级的图分治 / 最短路树技巧。先看清"图会不会变",再决定要不要预处理,是做题的第一步判断。)