GESP八级C组2025年9月这场考的“最短距离”我考完第一反应是真没想到能在一道看似模板的图论题里埋这么多坑。群里对答案的时候大家讨论最多的不是压轴的状压DP反而就是这道“最短距离”有人样例过了交上去分数不对有人连最短路都写挂了。这篇文章我把自己的复盘思路、完整模板、优化细节、考场上踩过的雷全部整理出来给准备冲八级的同学当一份可以直接参考的备考笔记。先说清楚“最短距离”这种题在八级里绝不是单纯的背模板它至少考了你三件事会不会建图、能不能写出稳定高效的最短路、有没有能力处理边界甚至路径计数。题目看着不动声色实际上每一处都对应考纲里的图论重点。下面我按考场上拆题的逻辑一步步讲。1. 拿到题目先做的事拆题面找考点1.1 “最短距离”在GESP八级里的真实定位GESP C八级大纲里图论部分的重头戏就是单源最短路、多源最短路、拓扑排序、最小生成树。“最短距离”这个题名看起来宽泛但在八级试卷里出现基本锁定为带权图的单源最短路径问题。和一级到四级那些考语法、考模拟的题不一样八级更看重算法复杂度分析和综合应用能力所以这种题表面是“送分”实际上每一档数据范围都在逼你选对算法。从这几年八级真题的风格看出题人很喜欢做一件事把经典算法变成一个“套了壳”的场景题。比如城市间修路、物流配送、通信网络延迟本质上都是最短路。外壳变来变去核心永远不变给你一堆节点和一堆带权边问你从某个起点出发到达目标点的最小代价。所以考场第一步不是着急敲代码而是把题面的壳剥掉确认它到底属于哪一类图论模型。1.2 复盘后还原出的典型题面因为考后论坛上大家复述的版本略有出入我按绝大多数人一致的记忆整理出下面这个题面结构也是这类题最经典的面貌有 N 个城市M 条道路每条道路连接两个城市长度为 W。道路可能是单向的也可能是双向的题目会给清楚。给定起点 S 和终点 T求 S 到 T 的最短距离。数据范围N 可以达到 10^5 级别M 可以达到 2×10^5 级别W 可以到 10^9 级别。部分年份还会追加一问如果存在多条最短路径输出方案总数并对某个模数取余。这个结构几乎就是为堆优化的 Dijkstra 量身定做的。你别小看加了一个“方案总数”就是这么个额外小问能刷掉一大批只会背模板的考生。为什么因为计数逻辑藏在松弛操作里写错一个更新顺序样例可能都对大数据直接挂。1.3 数据范围就是出题人给的提示我复盘时最爱做的一件事就是“倒推出题人意图”。看到 N ≤ 10^5、M ≤ 2×10^5立刻排除三层循环的 Floyd也基本排除裸 BFS。Floyd 是 O(N^3)10^5 个点想都别想BFS 只能处理无权图而这里每条边有长度 W。再注意边权范围到 10^9这代表了三件事第一距离要用 64 位整数保存第二初始化无穷大不能用 int 的 0x3f3f3f3f要用 64 位的极大值第三所有加法运算要考虑溢出风险。这三点任何一个没处理后面都是雷。如果题面里出现了“方案总数”并且对 1e97 取模那本质上是在最短路里叠加一个动态规划计数。看到这种设问心里就要立刻响应松弛操作里除了更新距离还要同步更新方案数而且要小心重复计数。2. 算法选型为什么首选堆优化的Dijkstra2.1 无权图才用BFS这里别犯迷糊很多同学看到“最短距离”第一反应是 BFS因为平时练迷宫题练出肌肉记忆了。但 BFS 的正确性建立在“每走一步代价相同”的基础上队列先到先得天然保证第一次访问就是最短。可一旦边有权重队列的先进先出就完全失效了先访问到的节点不意味着代价更小。举个例子一条边权为 100 的边先让你到达某个点另一条边权为 1 的边后到达同一个点BFS 会傻乎乎地锁定前者正确答案却是后者。所以这题必须上带权最短路算法。2.2 SPFA在GESP考场上翻车概率太高SPFA 的原理是用队列优化 Bellman-Ford在随机图上跑得飞快很多同学在学校OJ上用它屡试不爽。但它的最坏时间复杂度是 O(NM)当出题人构造出能反复入队的“网格图”“菊花图”时SPFA 会被卡到怀疑人生。GESP 的数据是官方精心构造的不代表随机的善意数据。我见过不止一个考生在考场上用 SPFA 写完跑样例全对自己觉得稳了结果提交一部分测试点超时。更关键的是SPFA 的代码里还有一堆细节容易出错比如标记是否在队列里的 inq 数组、出队后要清标记、判断负环要记录入队次数。在八级考场上时间紧张何苦选一个既有复杂度风险、又要多维护状态的算法。除非题目明确说明存在负权边否则我建议你直接不写 SPFA。2.3 堆优化Dijkstra的稳定性最值得信赖Dijkstra 的前提是图中不存在负权边而这题的边权是道路长度天然为正。堆优化后的复杂度是 O((NM)logN)在 N10^5、M2×10^5 的数据下非常好跑。它的思想其实和生活很像你手里有一堆待确认距离的点每次从中挑一个当前距离最小的点这个点的最短距离就可以正式确定了然后拿它去尝试更新它所有邻居。为什么每次都挑最小的因为所有边权都是正数不存在绕一圈回来反而更短的情况。这个“当前最小就是全局最小”的贪心结论是整个算法的基石。实现上使用优先队列小顶堆来维护“当前距离最小的候选点”每次弹出堆顶。需要注意一个经典细节同一个点可能因为多条路径被多次压入堆所以弹出时要判断当前堆里存的距离是否和 dist 数组一致不一致说明这是个过期状态直接丢弃。3. C代码实现从建图到最短路径计数3.1 邻接表用vector还是链式前向星建图方式上我推荐用 vector 邻接表。虽然链式前向星在极限常数上更快、内存更紧凑但对绝大多数考生而言vector 邻接表足够稳定代码可读性更高调试也更方便。GESP 的数据规模用 vector 完全不会成为瓶颈。我见过有些同学为了追求性能强行写链式前向星结果结构体数组下标一多就晕明明是简单题还把自己绕进去。竞赛的原则是用你最有把握的写法而不是用看起来很酷的写法。3.2 完整模板与逐段解读下面这个模板是我自己整理的包含最短路计算、距离输出、路径计数三个核心功能。题目场景是 N 点 M 边有向图求 S 到每个点的最短距离如果有最短路计数就输出计数结果。#include bits/stdc.h using namespace std; using ll long long; const ll INF 4e18; const int MOD 1000000007; struct Node { ll d; int u; bool operator(const Node other) const { return d other.d; } }; vectorvectorpairint, ll graph; vectorll dist; vectorint cnt; void dijkstra(int s) { priority_queueNode, vectorNode, greaterNode pq; dist[s] 0; cnt[s] 1; pq.push({0, s}); while (!pq.empty()) { Node cur pq.top(); pq.pop(); int u cur.u; if (cur.d ! dist[u]) { continue; } for (auto edge : graph[u]) { int v edge.first; ll w edge.second; if (dist[u] w dist[v]) { dist[v] dist[u] w; cnt[v] cnt[u]; pq.push({dist[v], v}); } else if (dist[u] w dist[v]) { cnt[v] (cnt[v] cnt[u]) % MOD; } } } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m, s; cin n m s; graph.assign(n 1, {}); dist.assign(n 1, INF); cnt.assign(n 1, 0); for (int i 0; i m; i) { int u, v; ll w; cin u v w; graph[u].push_back({v, w}); // 如果是无向边再加一句 graph[v].push_back({u, w}); } dijkstra(s); for (int i 1; i n; i) { if (dist[i] INF) { cout unreachable \n; } else { cout dist[i] cnt[i] \n; } } return 0; }这段代码里最核心的松弛逻辑要仔细捋一遍。当从 u 出发经过边权 w 能到 v会出现两种情况。第一种这条路比 v 当前记录的最短距离还要短那么 v 的最短距离被更新因为最短距离变了对应的最短路径方案数也要被覆盖成 cnt[u]同时把新状态压入堆。第二种这条路刚好等于 v 当前记录的最短距离说明发现了一条同样短的新路径方案数要累加为 cnt[v] cnt[u]。有人会问为什么第二种情况不把 v 重新压入堆我的回答是不需要。因为 dist[v] 没有被改变它已经在堆里拥有一个合法的状态再压只会多产生重复计算和额外时间开销。很多同学的计数错误就出在这里把相等的情况也当成更新距离去压堆结果方案数被反复累加样例过了却错得莫名其妙。3.3 路径还原不仅要距离还要输出具体路线如果题目要求在最短距离基础上输出完整路径可以在松弛时顺手记录每个节点的前驱节点也就是从哪个点转移来的。更新条件是“距离变短”但不要在“距离相等”时更新前驱否则输出的路线可能不符合字典序要求。vectorint pre(n 1, -1); // 在 dist[u] w dist[v] 时: pre[v] u; void print_path(int t) { vectorint path; while (t ! -1) { path.push_back(t); t pre[t]; } reverse(path.begin(), path.end()); for (int i 0; i (int)path.size(); i) { if (i) cout ; cout path[i]; } }如果要求字典序最小就不能简单地在等距时忽略。此时应该比较从起点到 v 的路径字典序复杂度会变高常规做法是建反图从终点跑一次 Dijkstra再结合正图贪心选点。不过这种进阶问法在GESP八级里比较少见了解原理即可。基础代码把 pre 维护明白就已经够应付绝大多数情况。3.4 多源情况与“所有点对”的变化有的“最短距离”题会改成多源一组起点集合问所有点到这个集合的最近距离。做法也很简单设一个虚拟超级源点从这个虚拟点向每个真实起点连一条边权为 0 的边然后跑一次单源 Dijkstra。这个技巧在很多真题变体里都能见到值得写进自己的模板库。还有一种变化是问所有点对距离看到 N ≤ 500 才有 Floyd 的发挥空间。如果 N 很大还问所有点对那就要思考是不是用 n 次 Dijkstra或者题目另有简化条件比如树结构。树上的所有点对最短路就是经过 LCA 的那条唯一路径与普通的图不同不能直接套 Dijkstra。4. 考场上的坑说出来全是经验踩过才长记性4.1 重边和自环竞赛图里的数据不一定是干净数据两点之间可能有两条长度不同的路甚至有一点连向自己的自环。邻接表建图时不需要刻意去重Dijkstra 在松弛时会自动取最短的边因为长的那条边计算出的距离不会被采纳。但自环要稍微想想自环如果长度为正不会影响最短路如果题目加了计数自环则可能让方案数出现不合理的叠加。一般情况下如果你看到 u v建图时直接跳过更保险避免造成逻辑歧义。4.2 64位溢出和INF的选择这是最经典、也是最容易翻车的一点。距离用 long long 没问题但 INF 千万别写死成 1e9。边权是 10^9路径可能经过 N 条边总和最大是 10^14已经超过了 int 范围。就算你用 long longINF 也要给到足够大我习惯给 4e18因为 long long 最大值约 9.22e184e18 既能保证“无穷大 有限边权”不溢出又不会大到在比较运算中出错。还要注意判断不可达时别用 dist[i] INF因为如果有一个状态真的从 INF 更新过dist 就不再是原来的数值用不等于关系判断要留个心眼。实际上更稳妥的写法是 dist[i] INF / 2 视为不可达。4.3 下标从0开始还是从1开始GESP 的题面习惯从 1 到 N 编号所以数组开 n 1循环也从 1 开始。如果你平时练题习惯从 0看题时一定要额外注意最好在草稿纸上写一句“编号从几开始”。我见过有同学在考场上一半代码用 1 一半代码用 0最后数据越界调试浪费了二十分钟。4.4 多组数据时记得清空状态有些测试点会把多组数据放在同一个文件里这时候每组输入都要重新 assign 一遍 dist、cnt、pre还有清空邻接表。如果你只是单纯在循环外初始化一次第二组数据就会带着上一组的结果跑满分直接变零分。这种错误在考后复查里特别多因为样例往往只有一组根本测不出来。4.5 优先队列排序方向别写反C 的 priority_queue 默认是大顶堆要想小顶堆你可以用 greater 自定义比较或者像我示例里那样重载 operator 再用 greater 。每次写完尽量自测一个三条边的小数据确认弹出来的顺序确实是距离小的在前。方向写反后代码看起来还能“跑出结果”但答案几乎全错。4.6 计数逻辑的顺序问题关于方案数的计数有一个高频错误在“距离相等”时把 cnt[u] 拿出来用了但此时 u 的方案数可能不是最终值因为 u 也许还没被完全更新。所以最好等 u 从堆里弹出确认它已经收敛为最短路后再用它的 cnt 去更新别人。上面模板里就是在弹出时先检查 cur.d ! dist[u] 就跳过保证取到的 cnt[u] 是准确的。这个设计不是细节是正确性的关键。我复盘时还整理了一个问题速查表写代码前扫一遍能避开大部分坑风险点表现对策距离溢出大数据输出负数或超大数dist 用 long longINF 用 4e18INF 过小不可达点被错误更新INF 大于所有可能路径之和重边最短路记录次优边不用去重松弛自然淘汰自环计数异常增加建图时 uv 跳过多组数据未清空第二组答案错乱每组重新 assign相等距离重复入堆计数翻倍只在距离严格变小时 push编号习惯混乱越界或答案错统一从 1 到 n数组开 n15. 如何把这题的解题能力变成八级应试肌肉5.1 八级真题的命题倾向从我这几年看 GESP 真题的感受来说八级题目确实在向综合性、应用性靠拢。“最短距离”这种题名不是考点考点藏在它背后的算法选择、复杂度分析、边界处理和代码稳定性里。我不建议大家去背“题面长什么样”而要背“这类模型怎么抽象”。八级里图论、树论、动态规划是绝对主力而且经常混合出题。比如最短路可以和 DP 组合可以和图的最小生成树对比考察可以要求输出具体方案。你在准备时要把最短路当成一个基础工具来熟练而不是孤立的一道题。5.2 冲刺阶段的刷题方向如果你现在距离考试还有一段时间我的建议按优先级来最短路三件套堆优化 Dijkstra、正确判断负环、SPFA的原理都要懂。实际考试优先 Dijkstra但原理必须会分析。建图基本功vector 邻接表、链式前向星二选一至少一种能闭眼敲出来。常见变形最短路径计数、路径输出、多源最短路、边权可能为 0 的情况。经典前导知识并查集、拓扑排序、二分答案这些经常和最短路配合出现。别贪多把每种模板的每一行都弄明白为什么这样写。我见过太多人背得滚瓜烂熟一换问法就不知道怎么改就是因为他只记了代码没记思想。5.3 考场时间分配和自检习惯八级考试时间有限题目数量不少如果“最短距离”不是压轴题建议控制在一个小时内完成从读题到自测。如果遇到的是带计数、带字典序路径的变体可以放宽到一个半小时但考场上要时刻留意剩余时间。交卷前给自己留出五分钟做三件事第一重新看一遍数据范围和编号起点第二把样例手动模拟一遍确认输出和自己推演的一致第三检查有没有多组数据清空问题。这三件事做完比多写十分钟不确定的优化更能保分。5.4 一个让代码更稳的小习惯我个人的一个小习惯是主函数开头固定写 ios::sync_with_stdio(false) 和 cin.tie(nullptr)。GESP 的输入量到 2e5 级别时这两行能省下不少时间。如果你更习惯 scanf 和 printf也不是不行但混用 cin/cout 与 scanf/printf 时要注意关闭同步后潜在的缓冲区混用问题。稳定压倒一切选你平时最常用的那套。最后说一点我自己复盘这套真题的体会。以前我也觉得“最短距离”是最没技术含量的题模板一背就完事。直到这次在考场上看到路径计数和一堆边界条件才发现真正拉开差距的不是你会不会 Dijkstra而是你能不能把一个成熟算法在全新场景里用对、用稳。竞赛这事从来不是“我听过这个算法”就能拿分而是“我能在高压下正确实现它”才算数。希望这份复盘能让你少走几步弯路下次在考场上看到“最短距离”这五个字时嘴角能微微上扬而不是眉头一皱。