GESP 题解库 / 8 级题解 / [GESP202503 八级] 上学 · 第 10 / 24 题
GESP202503 八级 · P11966 · 中等

上学路上求最短距离

从学校出发只跑一次 Dijkstra,之后每位同学 O(1) 查表。

🏫
n, m, q ≤ 2 × 10⁵
结点 / 边 / 询问数
📏
lᵢ ≤ 10⁶
每条路的长度(米)
⚡
O((n + m) log n + q)
一次最短路 + 查表
🎯
单源最短路
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

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 计算,每位同学从家出发需要多少秒才能到达学校。

输入输出样例

样例内容
输入 #15 5 3 3
1 2 3
2 3 2
3 4 1
4 5 3
1 4 2
5
1
4
输出 #14
3
1
💡
人话翻译:这是一张无向带权图,边权就是"走这条边要几秒"(1 米/秒,长度 = 时间)。
学校固定在 s,可同学们的家有 q 个,各有各的位置。
如果每个同学都单独跑一次最短路,就要跑 q 次 Dijkstra,必超时。
关键转念:在无向图里正着走和反着走一样长,所以 家 → 学校 的最短时间 = 学校 → 家 的最短时间。
于是只需从学校 s 跑一次 Dijkstra,把到每个点的最短时间算出来存好,之后每位同学问一次就查一次表,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 米/秒 ⇒ 最短长度就是最短时间

需要解决的问题

02
思维导图
整理解题思路的全貌
🏫 从学校出发跑一次 Dijkstra + q 次查表
📥 建图
无向边 → 双向加边
边权 = 长度(也就是时间)
邻接表 vector 存图
重边照单全收,不用特判
⚙️ 一次最短路
源点取学校 s
堆优化 Dijkstra(小根堆)
dist[v] = s 到 v 的最短时间
距离数组先全部设为 ∞
🔎 回答询问
读入 hᵢ 后直接输出 dist[hᵢ]
每次 O(1),总共 O(q)
家就在学校 ⇒ 答案是 0
不需要第二次最短路
⚠️ 易错点
每位同学各跑一次 → 超时
距离用 int → 溢出
INF 设太小(要大于 2 × 10¹¹)
忘记无向边要加两次
03
样例手算推导
样例 1 的三个询问逐一手算

🧮 样例 1:从学校 3 出发算一遍

样例的图共有 5 个结点、5 条边,学校在结点 3:

边长度备注
1 — 23
2 — 32
3 — 41
4 — 53
1 — 42
1
初始化

dist[1…5] 全部 = ∞

dist[3] = 0(学校自己到自己是 0 秒)

小根堆里压入 (0, 3)

准备出发

2
取出 (0, 3) → 结点 3 定稿

松弛 2:dist[2] = 0 + 2 = 2

松弛 4:dist[4] = 0 + 1 = 1

堆里现在是 (1, 4)、(2, 2)

dist[2] = 2,dist[4] = 1

3
取出 (1, 4) → 结点 4 定稿

松弛 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

4
取出 (2, 2) → 结点 2 定稿

松弛 1:2 + 3 = 5 比现在的 3 大,不更新

松弛 3:结点 3 已定稿,跳过

两个邻居都不需要更新

5
取出 (3, 1)、(4, 5) → 全部定稿

结点 1、结点 5 没有能再松弛的邻居

堆空,Dijkstra 结束

✅ 表算完了

📊 算出来的表与询问答案

结点123(学校)45
dist32014

回答 q = 3 个询问

询问同学的家查表 dist[hᵢ]说明
1545 → 4 → 3,长度 3 + 1 = 4
2131 → 4 → 3,长度 2 + 1 = 3(比 1 → 2 → 3 的 5 短)
3414 → 3,长度 1
🔑
注意第二次询问:结点 1 到 3 有两条路可选——1 → 2 → 3 长 5,1 → 4 → 3 长 3。Dijkstra 自动取了最短的那条,这正是我们要的答案,而不是"边数最少"或"任意一条路"。

🧮 为什么"换个起点"就等于"换个方向"?

题目问的是"家 → 学校",我们算的是"学校 → 家"。这两者凭什么相等?

1
一条路反过来还是路

无向图里 (u, v, l) 与 (v, u, l) 是同一条边

所以 家 → … → 学校 的结点序列倒过来写

就是 学校 → … → 家 的合法路径

两条路径的边完全一样,长度自然一样

✅ 两个方向的"路径集合"完全相同

2
取最短之后仍然相等

既然路径集合相同,最短长度必然相同

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。
04
解法对比
一次 Dijkstra 查表 vs 每个询问各跑一次 vs Floyd

⚔️ 解法对比

🟢 从 s 跑一次 Dijkstra + O(1) 查表 推荐

以学校为源点求单源最短路,之后每个询问直接查 dist[hᵢ]

  • 时间 O((n + m) log n + q)
  • n = m = q = 2 × 10⁵ 时约 7 × 10⁶
  • 空间 O(n + m)
  • 代码约 40 行,模板化程度高
💡
正确性来源:无向图的路径可逆 ⇒ dist(h → s) = dist(s → h);而 Dijkstra 在非负边权下给出的dist[s][v] 就是真正的最短距离。
所以"算一次 + 查 q 次"与"算 q 次"答案完全一致,只是把 q 倍的重复计算省掉了。

🟠 每位同学各跑一次最短路

对每个 hᵢ 都以 hᵢ 为源点跑 Dijkstra,取 dist[s]

  • 时间 O(q(n + m) log n)
  • 最坏约 8 × 10¹⁰,必然超时
  • 正确性没问题,但做法浪费
  • 只适合 q、n 都很小的部分分
⚠️
为什么会挂:每次最短路都在同一张图上重复劳动,q = 2 × 10⁵ 时相当于把同一个计算做了 20 万遍。
把"多次询问"合并成"一次预处理 + 多次查询",是这类题最通用的优化思路。

📈 性能对比

方案复杂度结论
从 s 跑一次 Dijkstra + 查表O((n + m) log n + q)✅ 推荐(官方做法)
每个询问各跑一次 DijkstraO(q(n + m) log n) ≈ 8 × 10¹⁰❌ 超时
Floyd 全源最短路O(n³) ≈ 8 × 10¹⁵❌ 完全不可行
05
算法流程图
一次最短路 + q 次 O(1) 查表
开始读入 n、m、s、q读入 m 条无向边 (u, v, l),双向加入邻接表dist[1…n] = ∞;dist[s] = 0,把 (0, s) 压入小根堆小根堆还是空的吗?弹出堆顶 (d, x);若 d 已大于 dist[x] 就丢弃这一条记录d + w < dist[y] 吗?是 ✓dist[y] = d + w,把 (dist[y], y) 入堆否 ✗这条边不用松弛堆空了,进入询问阶段:读入 hᵢ输出 dist[hᵢ](若家就在学校,自然是 0)结束反复松弛
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🏫 最短上学时间计算器

第一行输入 n m s q,随后 m 行输入 u v l(无向边),再随后 q 行输入每位同学的家 h。程序会从学校 s 跑一次 Dijkstra,展示结点定稿顺序与每位同学的答案。

结果会显示在这里

点按钮开始 →

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

💻 完整 C++ 代码(从学校出发的一次 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;
}
🔑
三个要点:① 源点是学校 s,不是某个同学的家;② 无向边两个方向都要加,只加一次就变成有向图了;③ 距离和 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_ 规避)。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

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

输入答案考察点
5 5 3 3
1 2 3
2 3 2
3 4 1
4 5 3
1 4 2
5
1
4
4
3
1
题面样例:5 → 4,1 → 3,4 → 1
2 1 1 2
1 2 5
1
2
0
5
第一个询问的家就是学校,答案是 0
3 3 1 2
1 2 10
1 3 1
3 2 1
2
3
2
1
绕路更近:1 → 3 → 2 只有 2,直连的 10 更贵
4 3 1 3
1 2 7
2 3 7
3 4 7
4
2
1
21
7
0
链上累加:距离随边数线性增长
2 2 1 2
1 2 9
1 2 3
2
1
3
0
重边(平行边):自动取短的那条 3
3 2 2 3
1 2 1000000
2 3 1000000
1
3
2
1000000
1000000
0
大边权:最坏总长约 2 × 10¹¹,必须 long long
✅
自查清单:① 源点是学校 s 吗?② 无向边两个方向都加了吗?③ 距离用 long long 了吗?④ 询问是 O(1) 查表吗?

🚨 易错点清单

⚠️
每位同学各跑一次最短路:那是 q 次 Dijkstra,最坏 8 × 10¹⁰,必定超时;本题只需从学校跑一次。
⚠️
距离用 int:最坏一条路径约 2 × 10¹¹,超过 int 上界 2147483647,会溢出成负数。
⚠️
无向边只加一次:那就成了有向图,"家 → 学校"可能直接变成不可达。
⚠️
INF 设得太小:用 1e9 当无穷会让正常答案被误判;建议 4e18。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O((n + m) log n + q)
空间复杂度
O(n + m)
最短路次数
仅 1 次
查询
每次 O(1)

时间怎么算的?

空间都用在哪?

邻接表存 2m 条有向弧,约占 O(n + m);距离数组 long long dist_[n + 1] 占 O(n);小根堆最多同时存 O(m) 条记录。

✅ 一次最短路打底,之后全部 O(1) 查表,把 q 个询问的重复计算彻底消掉了,20 万规模的询问毫无压力。

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

🔗 常用技巧小抄

// 「一次单源最短路 + 多次 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 小的时候可行),要么就要换更高级的图分治 / 最短路树技巧。先看清"图会不会变",再决定要不要预处理,是做题的第一步判断。)