信息学奥赛刷题实战：用SPFA算法秒杀《最短路》这道题（附C++完整代码）
在信息学竞赛的战场上，最短路径问题就像一位常驻考官，几乎在每场比赛中都会以不同面貌出现。而面对这位考官的终极武器，往往不是单一的算法，而是对多种算法的深刻理解和灵活运用。今天，我们就来深入探讨如何在实际竞赛中，根据题目特点精准选择最优解法，并用SPFA算法高效解决《信息学奥赛一本通》1382题。
1. 算法选型：为什么SPFA更适合这道题？
当面对一个顶点数高达10万的图论问题时，算法选择直接决定了程序能否在规定时间内运行完毕。让我们先看看几种常见最短路径算法的复杂度对比：
| 算法类型 | 时间复杂度 | 适用场景 |
|---|---|---|
| 朴素Dijkstra | O(V²) | 稠密图，顶点数较少 |
| 堆优化Dijkstra | O(ElogE) | 稀疏图，边数相对较少 |
| SPFA | 平均O(kE) | 稀疏图，无负权环 |
对于本题而言，顶点数V=1e5，边数E=5e5，这意味着：
- 朴素Dijkstra的V²将达到1e10，远超竞赛常见的时间限制1e7
- 堆优化Dijkstra的ElogE约为1e6，完全可接受
- SPFA在稀疏图中的k通常很小，平均复杂度可能优于堆优化Dijkstra
关键决策点：
- 题目明确是无向图（可能有重边和自环）
- 边数远小于V²，属于典型稀疏图
- 没有负权边（SPFA处理负权边的优势无法体现）
// 邻接表存储结构示例 struct Edge { int to, weight; Edge(int t, int w) : to(t), weight(w) {} }; vector<Edge> graph[MAXN];提示：在实际竞赛中，当V>1e4时就应该立即排除朴素Dijkstra算法。而在稀疏图中，SPFA的实际表现往往优于理论复杂度。
2. SPFA算法核心实现与优化技巧
SPFA(Shortest Path Faster Algorithm)本质上是Bellman-Ford算法的队列优化版本，通过动态松弛操作来逐步逼近最短路径。让我们拆解其核心实现：
算法流程：
- 初始化距离数组dis[]为INF，起点dis[s]=0
- 创建队列，将起点入队
- 当队列非空时：
- 取出队首节点u
- 遍历u的所有邻接边u→v：
- 若dis[v] > dis[u] + w(u,v)，则更新dis[v]
- 若v不在队列中，则将其入队
- 队列为空时算法结束
void SPFA(int start) { fill(dis, dis+MAXN, INF); dis[start] = 0; queue<int> q; q.push(start); inQueue[start] = true; while(!q.empty()) { int u = q.front(); q.pop(); inQueue[u] = false; for(auto &e : graph[u]) { int v = e.to, w = e.weight; if(dis[v] > dis[u] + w) { dis[v] = dis[u] + w; if(!inQueue[v]) { q.push(v); inQueue[v] = true; } } } } }性能优化点：
- 使用循环队列避免频繁内存分配
- 对稠密图可改用优先队列（退化为Dijkstra）
- 添加SLF(Small Label First)优化：当新节点v的dis[v] < dis[q.front()]时插入队首
注意：虽然SPFA最坏复杂度为O(VE)，但在竞赛题目的数据下，特别是随机生成的稀疏图中，实际运行效率往往接近O(kE)，k通常为2-3。
3. 邻接表实现的工程化考量
在算法竞赛中，邻接表的实现方式直接影响代码的编写效率和运行性能。常见的实现方式有：
- vector数组法（推荐初学者使用）
vector<Edge> graph[MAXN]; // 添加边 graph[u].emplace_back(v, w);- 链式前向星（内存更紧凑）
struct Edge { int to, w, next; } edges[MAXM]; int head[MAXN], cnt; void addEdge(int u, int v, int w) { edges[++cnt] = {v, w, head[u]}; head[u] = cnt; }对比分析：
| 特性 | vector数组法 | 链式前向星 |
|---|---|---|
| 内存占用 | 较高（动态分配） | 更低（静态分配） |
| 编码复杂度 | 简单直观 | 需要维护指针 |
| 缓存友好性 | 较差 | 更好 |
| 遍历效率 | 略低 | 更高 |
对于竞赛编程，除非遇到极端内存限制（如V=1e6以上），否则vector数组法因其编写简单、调试方便的优势，通常是更好的选择。
4. 完整题解代码与测试技巧
结合上述分析，我们给出完整的SPFA解法代码，并附上关键测试技巧：
#include <bits/stdc++.h> using namespace std; const int MAXN = 1e5 + 5; const int INF = 0x3f3f3f3f; struct Edge { int to, w; Edge(int t, int weight) : to(t), w(weight) {} }; vector<Edge> graph[MAXN]; int dis[MAXN]; bool inQueue[MAXN]; void SPFA(int start, int n) { fill(dis, dis + n + 1, INF); dis[start] = 0; queue<int> q; q.push(start); inQueue[start] = true; while (!q.empty()) { int u = q.front(); q.pop(); inQueue[u] = false; for (auto &e : graph[u]) { int v = e.to, w = e.w; if (dis[v] > dis[u] + w) { dis[v] = dis[u] + w; if (!inQueue[v]) { q.push(v); inQueue[v] = true; } } } } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; for (int i = 0; i < m; ++i) { int u, v, w; cin >> u >> v >> w; graph[u].emplace_back(v, w); graph[v].emplace_back(u, w); // 无向图 } SPFA(1, n); cout << dis[n] << endl; return 0; }测试技巧：
- 边界测试：n=1的特殊情况
- 重边测试：添加多条u→v的边，取最小值
- 自环测试：检查u→u的边是否影响结果
- 极端数据：构造链式图和菊花图测试性能
5. 算法对比与竞赛策略
在实际竞赛中，最短路径问题的解题策略应该是：
数据规模分析：
- V≤1e3：朴素Dijkstra
- V≤1e5，E≤1e6：堆优化Dijkstra或SPFA
- 存在负权边：必须使用SPFA或Bellman-Ford
编码复杂度考量：
- SPFA代码量通常比Dijkstra少10-20%
- 在时间压力大的比赛中，SPFA可能是更稳妥的选择
稳定性考虑：
- 当题目可能存在刻意卡SPFA的数据时，优先选择Dijkstra
- 对于明确无负权边的题目，Dijkstra的理论保证更强
// 堆优化Dijkstra的关键片段 priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq; pq.emplace(0, start); dis[start] = 0; while (!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); if (d > dis[u]) continue; for (auto &e : graph[u]) { if (dis[e.to] > dis[u] + e.w) { dis[e.to] = dis[u] + e.w; pq.emplace(dis[e.to], e.to); } } }在最近的NOI系列比赛中，出题人倾向于设置更大的数据规模（V,E≤2e5），这使得算法选择更加关键。根据我的参赛经验，在这种规模下，SPFA和Dijkstra的时间差距可能只有100-200ms，但正确的选择意味着AC与TLE的天壤之别。
