企业官网建设流程全解析

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 位的极大值；第三，所有加法运算要考虑溢出风险。这三点任何一个没处理，后面都是雷。

如果题面里出现了“方案总数”并且对 1e9+7 取模，那本质上是在最短路里叠加一个动态规划计数。看到这种设问，心里就要立刻响应：松弛操作里除了更新距离，还要同步更新方案数，而且要小心重复计数。

2. 算法选型：为什么首选堆优化的Dijkstra

2.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((N+M)logN)，在 N=10^5、M=2×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; } }; vector<vector<pair<int, ll>>> graph; vector<ll> dist; vector<int> cnt; void dijkstra(int s) { priority_queue<Node, vector<Node>, greater<Node>> 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 路径还原：不仅要距离，还要输出具体路线

如果题目要求在最短距离基础上输出完整路径，可以在松弛时顺手记录每个节点的前驱节点，也就是从哪个点转移来的。更新条件是“距离变短”，但不要在“距离相等”时更新前驱，否则输出的路线可能不符合字典序要求。

vector<int> pre(n + 1, -1); // 在 dist[u] + w < dist[v] 时: pre[v] = u; void print_path(int t) { vector<int> 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 long，INF 也要给到足够大，我习惯给 4e18，因为 long long 最大值约 9.22e18，4e18 既能保证“无穷大 + 有限边权”不溢出，又不会大到在比较运算中出错。

还要注意判断不可达时别用 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] 是准确的。这个设计不是细节，是正确性的关键。

我复盘时还整理了一个问题速查表，写代码前扫一遍，能避开大部分坑：

5. 如何把这题的解题能力变成八级应试肌肉

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，而是你能不能把一个成熟算法在全新场景里用对、用稳。竞赛这事，从来不是“我听过这个算法”就能拿分，而是“我能在高压下正确实现它”才算数。希望这份复盘能让你少走几步弯路，下次在考场上看到“最短距离”这五个字时，嘴角能微微上扬而不是眉头一皱。