★ FEATURED ARTICLE GESP的C八级说实话是很多选手第一次真正接触“竞赛级图论”的地方。2025年9月这套卷子里那道“最短距离”我印象很深表面看就是个经典单源最短路但考场上能把样例跑通的人不少能把边界情况和大数据全部处理稳的才真正拿到分。这篇文章就用这道真题作为引子把从题意建模到堆优化Dijkstra落地再到考场避坑的完整链路拆开讲一遍适合正在备考GESP八级、以及准备CSP-J/S第二轮的同学参考。1. 真题背景与考点定位1.1 2025年9月这道题在考什么“最短距离”这道题按考生回忆整理的题面大致是这样的给定N个点和M条无向带权边每条边有一个正整数权值再给定起点S和终点T要求输出从S到T的最小总权值如果无法到达则输出-1。数据范围方面N最大可以到10万M到20万边权最大到10的9次方。这个范围设置很讲究。N10万意味着你不可能用邻接矩阵M20万说明图的稀疏程度还算友好边权到10的9次方则直接提醒你别用int存距离。综合下来这道题就是在考你有没有掌握堆优化的Dijkstra以及有没有踩过“int不够用”的坑。GESP八级大纲里图论是绝对的重头戏最短路径、最小生成树、拓扑排序这“图论三件套”几乎每年都轮流出现在考卷上而其中最常被选中当大题的就是最短距离。很多同学会问BFS不是也能求最短吗这里要分清图的性质。BFS求的是无权图上的最少步数而这道题每条边有权值步数最少不等于总权值最小所以必须上带权最短路算法。理解了这一点整道题的解法方向就对了。1.2 为什么八级把这类题当常客GESP前几级考的东西本质上是单策略问题四级的递归、五级的分治、六级的贪心、七级的动态规划都是“把问题映射到一个已知模型然后按模型套路做”。八级引入图论后情况突然变了因为图论题的难点一多半在建图而不是算法本身。拿“最短距离”举例算法核心就三句话维护距离数组、找当前最近节点、松弛相邻边。但你要在建边时想清楚无向边要加两条、重边要不要处理、自环会不会影响答案你要在数据结构上想清楚用vector存邻接表还是链式前向星你还要在复杂度上想清楚朴素Dijkstra为什么过不了10万的数据。一个环节出错整道题直接归零。出题人非常清楚这一点。最短距离类题目既能考察选手的图论建模能力又能考察代码实现的稳定性还能通过数据范围自然淘汰掉不会堆优化的选手区分度极高。所以八级反复考它真的不是巧合而是这类题刚好命中了大纲要求的“综合能力”。2. 题意解析与状态设计2.1 一个可以现场复现的题面框架为了后面讲实现方便我先把一个典型的题面框架写出来你们可以对照着理解输入格式 第一行一个整数T表示测试数据组数。 每组数据 第一行两个整数N、M表示点数和边数。 接下来M行每行三个整数u、v、w表示u和v之间有一条无向边权值为w。 最后一行两个整数S、T表示起点和终点。 输出格式 对于每组数据输出一个整数表示S到T的最短距离 如果S和T不连通输出-1。示例输入1 5 6 1 2 2 1 3 4 2 4 5 2 5 10 3 5 3 4 5 1 1 5手动模拟一下1到5有三条候选路径1-2-4-5总权值为25181-2-5总权值为210121-3-5总权值为437所以答案应该是7。这个用例可以作为你写完代码后对拍的第一道测试。真题现场可能有细微差别比如边权可能大到1e12或者要求输出最短路径本身而不仅是距离但核心模型不变。你们拿到题目后第一件事就是看清边权范围和是否连通这个输出约定这两个信息直接决定你的算法选型和INF设置。2.2 邻接表与链式前向星二选一建图方式我推荐直接用C STL的vector邻接表理由很实际代码短、不易写错、调试方便。定义是这样的struct Edge { int to; long long w; }; vectorvectorEdge g(n 1);无向边记得加两次g[u].push_back({v, w}); g[v].push_back({u, w});。这是新手最容易漏掉的一行漏了之后你会发现有的用例答案偏大因为图变成单向的了。追求极限性能的同学可以用链式前向星。虽然它稍微快一点但在10万点、20万边的规模下vector邻接表完全够用而且链式前向星的头插法容易把边序搞反调试起来更费劲。我的个人建议是考场上用你最熟练、最不容易出错的写法而不是“理论最快”的写法。代码稳定性在GESP考场上远比微小的常数优化重要。为什么不能用邻接矩阵很简单N10万时邻接矩阵需要10万乘以10万个元素就算用bool类型存储也要大约10GB内存直接爆掉评测机的内存限制。这也是一个判断信号——看到N超过5000想都不要想直接排除矩阵解法。2.3 状态定义里隐藏的坑最短路的状态定义初看很简单dist[i]表示从起点S到点i的当前已知最短距离。初始时dist[S]0其余全部是无穷大。状态转移也不复杂对于当前点u的每条边(u,v,w)如果dist[u] w dist[v]就更新dist[v]。但这里面藏着一个本质问题图里是存在环的。你从一个点出发绕一圈回来理论上可以无限次地更新距离这就是为什么不能像普通动态规划那样从前往后递推一遍就完事。Dijkstra算法解决的核心难点正是“在边权非负的前提下如何保证每次选出来的节点距离就是最终答案不需要再反复更新”。我常用一个生活化的类比来理解这件事想象你在医院候诊每个候诊者有一个“预计等待时间”。每次你从候诊室挑一个预计时间最短的人去就诊因为所有新产生的时间都只增不减边权非负所以这个人后续不可能再有更短的时间可以放心确定结果。优先队列在这里就是那个自动帮你找“最短候诊者”的数据结构。3. 算法选型为什么是堆优化的Dijkstra3.1 选Dijkstra而不是SPFA单源正权最短路最稳的选择就是堆优化的Dijkstra复杂度为O((NM)logN)。在本题的10万点规模下这个复杂度毫无压力即使M到20万总运算量也就是百万级别轻松通过。有的同学会想SPFA不是写起来更短吗SPFA在随机数据下表现不错但它有一个致命弱点——最坏时间复杂度是O(N*M)可以被精心构造的网格图卡到超时。GESP是计算机学会组织的认证考试数据设计里完全可能包含这种卡SPFA的用例。在正权图上你没理由放弃复杂度有保证的Dijkstra而选择等待不确定的SPFA。Dijkstra唯一不能处理的是负权边。如果题目允许边权为负数Dijkstra的“确定一次不再更新”的核心假设就崩了必须换Bellman-Ford这类算法。但至少2025年9月这道“最短距离”题目明确是正整数边权堆优化Dijkstra就是标准答案。3.2 优先队列里的三个细节用优先队列实现堆优化有几个细节一定要养成肌肉记忆第一插入的pair里first放距离second放节点编号。因为pair默认先比first再比second这样保证优先队列按距离排序。写成pairlong long, int不要只写pairint,int距离一大就会溢出截断。第二优先队列默认是大顶堆要取距离最小必须用greaterpairlong long, int声明小顶堆。这个greater经常有人忘写一旦忘写算法就变成每次取最远的点结果完全错误。第三弹出节点后要“懒删除”。因为同一个节点可能被多个不同距离的条目多次入队我们只希望处理距离最小的那一次。常见有两种写法// 写法A用vis数组标记已确定 if (vis[u]) continue; vis[u] true; // 写法B直接对比dist if (d ! dist[u]) continue;两种写法都对但不要混用更不要在push时就把vis标记为true。为什么不能在push时标记因为第一次入队时的距离未必是最终最短距离可能后面又发现了一条更短的路若你已经标记了vis这条更短的路就无法更新了。这个坑我见过无数人踩务必重视。3.3 复杂度与数据范围对照表数据规模可用算法复杂度结论N ≤ 200Floyd-WarshallO(N^3)可过代码最短N ≤ 1000M较小朴素DijkstraO(N^2)勉强可过N ≤ 100000堆优化DijkstraO((NM)logN)必须使用存在负权边Bellman-Ford/SPFAO(N*M)特殊场景才用从这张表能看出考场上先看数据范围再定算法是避免超时的关键一步。一道题如果N给了10万算法选错基本就是0分和满分的区别。4. 完整C题解与逐步讲解4.1 参考代码C17#include bits/stdc.h using namespace std; typedef long long ll; const ll INF 1e18; struct Edge { int to; ll w; }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T; cin T; while (T--) { int n, m; cin n m; vectorvectorEdge g(n 1); for (int i 0; i m; i) { int u, v; ll w; cin u v w; g[u].push_back({v, w}); g[v].push_back({u, w}); // 无向图记得加反向边 } int s, t; cin s t; vectorll dist(n 1, INF); vectorbool vis(n 1, false); priority_queuepairll, int, vectorpairll, int, greaterpairll, int pq; dist[s] 0; pq.push({0, s}); while (!pq.empty()) { auto cur pq.top(); pq.pop(); ll d cur.first; int u cur.second; if (vis[u]) continue; // 已经确定最短路的点跳过 vis[u] true; if (u t) break; // 终点已确定可提前结束 for (const Edge e : g[u]) { int v e.to; ll nd d e.w; if (nd dist[v]) { dist[v] nd; pq.push({nd, v}); } } } if (dist[t] INF) { cout -1 \n; } else { cout dist[t] \n; } } return 0; }这段代码用了bits/stdc.h万能头文件。GESP的评测环境通常支持但如果你平时在本地用的是MSVC一类不支持万能头的环境改成iostream、vector、queue、functional也完全可以。4.2 核心代码逐段拆解整个主循环的逻辑本质上是在维护一个“已确定最短距离的节点集合”。从优先队列里弹出来的节点一定是当前所有未确定节点中距离最小的这个节点一旦弹出它的距离就不可能再被缩短于是标记vis并入集合。然后扫描它所有邻居尝试更新邻居的距离把更新成功的邻居重新入堆。这里我特别想展开讲一下“提前break”的合法性。很多同学写过Dijkstra但不敢提前结束担心后面还有更短路径。实际上当终点T第一次从堆顶弹出时因为堆顶是所有未确定节点里距离最小的而所有边权为正不可能存在一条“尚未被发现的路径”比当前T的距离更短——如果真的存在那条路径上的某个中间节点早就应该以更小距离出现在堆里了。所以if (u t) break;这个优化是安全且省时间的。再讲一下INF的设置。为什么用1e18而不是2e9或INT_MAX因为最短路长度可能超过int范围。一条路径最多经过N-1条边每条边权值最大1e9乘积最大是1e5乘以1e9等于1e14所以用long long配合1e18的INF既不会溢出也能保证“INF加一个正常边权仍然远大于任何真实距离”不会出现INF被误判为可达的情况。4.3 自测用例与期望输出写完代码一定不要直接交先跑几个自己设计的用例。这里给出一张自测表你们可以拿去过一遍逻辑编号输入要点期望输出验证目的15点6边1到57最基本的最短路正确性23点1-2有两条重边(10和5)2-3有边16重边是否被正确处理32点0边起点1终点2-1不连通情况的输出42点1边边权1e121000000000000大边权是否用long long5N1起点终点0起点即终点的边界第5个用例很多人会忽略。起点和终点相同时最短距离当然是0代码里dist[s]0直接输出即可不需要任何特判。如果忘了考虑有可能在循环里跑一圈后输出一个奇怪的值。5. 考场高频踩坑与避坑清单5.1 最容易让人丢分的五个点第一个坑是INF类型不对。用int存距离再赋个1e9遇到大边权直接WA。GESP八级的评测用例里专门会设计边权接近1e9的数据来卡你所以距离数组、dist计算、pair里的first全部要统一成long long。第二个坑是无向边只加了一次。这属于建图错误典型表现是小数据能过大数据答案偏大。注意看题目描述用的是“无向边”还是“有向边”无向边一定要g[u]和g[v]两边都加。第三个坑是vis标记时机错误。前面说过在push时标记vis会断掉后续更短路径的更新。这种错误非常隐蔽小样例可能恰好能过一旦出现“先经过长边再到终点、后经过短边再到终点”的用例就直接翻车。第四个坑是忘记清空数据结构。如果题目有多组测试数据dist和vis每次都要重新初始化为INF和false。这个方法我在代码里放在了while循环内部定义每次循环都是全新数组天然安全。第五个坑是没有判断不可达。题目要求不可达输出-1但有的同学直接输出INF或者在循环结束后不检查直接打印dist[t]。要专门加一行if (dist[t] INF) cout -1;这个条件判断在考场上至少值10分。5.2 内存与代码稳定性技巧堆优化的Dijkstra优先队列里可能同时存在很多条“过期的旧数据”。比如某个节点被更新了3次堆里就可能有3个条目对应它。这不用担心因为旧条目弹出时要么被vis数组拦下要么被d ! dist[u]拦下不会影响正确性。堆里最多条目数是M级别的内存依然安全。另外一个小技巧是输出调试。如果答案不对我通常会在每次弹出节点时打印一下u和d如果发现某个节点的弹出顺序不是从小到大说明堆的比较器有问题如果发现某个节点被重复处理说明vis标记时机错了。调试最短路题目打印关键节点距离比逐行看代码快得多。我还喜欢在本地写一个对拍脚本用暴力DFS跑N≤8的小随机数据和Dijkstra的结果对拍。只要小数据跑几十组不出错算法正确性基本就有了保证。6. 从最短距离到八级其他常考变式6.1 变式A带状态的二维最短路GESP八级不满足于只考裸最短路常见的升级方式是“给状态加维度”。比如网格地图上从起点到终点每个格子可以正常走过去也可以花费一个道具瞬移到特殊位置但道具最多只能用一次。这就是典型的二维状态最短路dist[i][j]表示到点i、用了j次道具的最短距离转移时多枚举一层“是否使用道具”的决策。这类题的建图方式从普通图变成了“分层图”每一层对应一种剩余道具状态层内正常连边层间通过使用道具的边连接。理解了Dijkstra的“状态松弛”本质分层图也就是多开一个维度的dist数组而已。八级真题里大量题目都是这个套路建议备考时主动练习几道。6.2 变式B负权边与多源最短路如果题目加了负权边堆优化Dijkstra就不能用了这时候需要了解Bellman-Ford或者SPFA。它们还可以检测是否存在负权环——如果某个点被入队超过N次说明存在负环。GESP八级对这部分考得不深但了解原理能帮助你判断“为什么这道题不能用Dijkstra”。另一个高频变式是多源最短路有多个起点问哪个点到终点的距离最短。最优雅的解法不是跑多次Dijkstra而是建立一个超级源点把它和所有起点连一条权值为0的边然后只跑一次Dijkstra得到的结果就是所有起点的最短距离。这个“超级源点”思想在很多图论题里都有用一次学会终身受益。6.3 备考建议把最短路模板练成肌肉记忆我在带八级考生时反复强调最短路模板必须练到“闭着眼睛也能默写”的程度。因为考试时你根本没时间现场推理优先队列的逻辑如果写一段想一段大概率会在小细节上出错。具体操作分三步。第一步每天花15分钟默写一遍Dijkstra模板连续一周。第二步给模板换不同的数据结构和建图方式比如改成链式前向星、改成有向图、改成输出路径把模板的每个配件都摸透。第三步找往年的八级真题和CSP普及组真题专门挑最短路相关的题刷10道以上重点练“从文字描述到状态定义”的建模能力而不是重复抄代码。我个人在实际操作中最深的体会是这道“最短距离”题真正拉开分数差距的从来不是“会不会Dijkstra”而是“能不能在紧张状态下写对每一个细节”。INF类型、无向图加边两次、vis标记时机、不可达判断这四个点随便踩中两个一道题就从满分变成30分。最后再分享一个小技巧每次交代码前花10秒钟检查一下distance相关变量是否都是long long、无向边是不是加了两行、输出前有没有判断INF这三个检查能帮你稳定救回十分以上。GESP八级想拿高分靠的不是灵光一现而是把基本功打磨到无懈可击。
阅读完成 · 觉得有帮助？
