信息学奥赛刷题实战：用Dijkstra算法搞定《城市路》这道题（附C++完整代码）

信息学奥赛刷题实战：用Dijkstra算法搞定《城市路》这道题（附C++完整代码）

第一次接触《城市路》这类最短路径题目时，我盯着2000个顶点和10000条边的数据规模发愁——邻接矩阵会爆内存，朴素Dijkstra可能超时，到底该选哪种实现方式？经过多次比赛实战和代码优化，我发现堆优化的Dijkstra配合链式前向星才是这类题目的黄金组合。本文将带你从题目分析到AC代码，一步步拆解如何用不同姿势征服这道经典题目。

1. 题目分析与算法选型

《城市路》作为信息学奥赛经典题型，考察的是单源最短路径问题的实际应用能力。题目给出n个城市（顶点）和m条双向道路（边），要求计算从城市1到城市n的最短距离。表面看是模板题，但数据规模暗藏玄机：

• 顶点数n=2000：直接排除了O(V²)的邻接矩阵存储
• 边数m=10000：提示我们需要考虑O(ElogV)级别的算法
• 双向边：建图时需要正反双向处理

算法选择对比表：

提示：虽然SPFA在随机数据下表现优异，但竞赛中更推荐使用稳定的Dijkstra算法

2. 数据结构设计：邻接表的两种实现

面对2000个顶点，我们必须放弃邻接矩阵。以下是两种更优的邻接表实现方案：

2.1 vector数组实现（推荐新手）

struct Edge { int v, w; // 目标顶点和边权值 Edge(int _v, int _w) : v(_v), w(_w) {} }; vector<Edge> graph[N]; // 邻接表存储 // 添加边示例（双向） graph[f].emplace_back(t, w); graph[t].emplace_back(f, w);

优势：

• 代码直观易调试
• 无需手动管理内存
• 遍历时直接使用range-based for

2.2 链式前向星实现（竞赛常用）

struct Edge { int to, w, next; } edges[M*2]; // 无向图需双倍空间 int head[N], cnt; void addEdge(int u, int v, int w) { edges[++cnt] = {v, w, head[u]}; head[u] = cnt; } // 添加双向边 addEdge(f, t, w); addEdge(t, f, w);

性能对比：

• 内存占用：链式前向星更节省（固定数组）
• 访问速度：链式前向星cache命中率更高
• 编码复杂度：vector更易实现

3. Dijkstra算法的三种实现策略

3.1 朴素版Dijkstra（理解原理）

void dijkstra(int start) { memset(dis, 0x3f, sizeof(dis)); // 初始化为INF dis[start] = 0; for(int i = 1; i <= n; ++i) { int u = -1; // 找到未访问的最近顶点 for(int j = 1; j <= n; ++j) if(!vis[j] && (u == -1 || dis[j] < dis[u])) u = j; vis[u] = true; // 松弛操作 for(auto &e : graph[u]) { int v = e.v, w = e.w; if(!vis[v] && dis[v] > dis[u] + w) dis[v] = dis[u] + w; } } }

缺陷分析：

• 每次查找最小dis需O(V)时间
• 总复杂度O(V²)在V=2000时约为4e6次操作
• 实际测试在部分OJ上可能卡在时间边缘

3.2 堆优化版Dijkstra（竞赛首选）

using PII = pair<int, int>; // first:距离 second:顶点 priority_queue<PII, vector<PII>, greater<PII>> pq; void dijkstra(int start) { memset(dis, 0x3f, sizeof(dis)); dis[start] = 0; pq.emplace(0, start); while(!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); if(vis[u]) continue; vis[u] = true; for(auto &e : graph[u]) { int v = e.v, w = e.w; if(dis[v] > dis[u] + w) { dis[v] = dis[u] + w; pq.emplace(dis[v], v); } } } }

关键优化点：

• 使用优先队列快速获取最小dis节点（O(logV)）
• 通过vis数组避免重复处理
• 总复杂度降为O(ElogV)

3.3 堆优化+链式前向星（终极优化）

void dijkstra(int start) { memset(dis, 0x3f, sizeof(dis)); dis[start] = 0; pq.emplace(0, start); while(!pq.empty()) { int u = pq.top().second; pq.pop(); if(vis[u]) continue; vis[u] = true; for(int i = head[u]; i; i = edges[i].next) { int v = edges[i].to, w = edges[i].w; if(dis[v] > dis[u] + w) { dis[v] = dis[u] + w; pq.emplace(dis[v], v); } } } }

性能实测数据（n=2000, m=10000）：

4. 常见踩坑与调试技巧

4.1 无穷大设置的艺术

// 0x3f3f3f3f的妙处： // 1. 足够大(1061109567) // 2. 两个0x3f相加不会溢出 // 3. memset按字节设置 memset(dis, 0x3f, sizeof(dis));

错误案例：

#define INF 0x7fffffff // 可能导致dis[u]+w溢出

4.2 双向边的处理

// 错误：忘记添加反向边 addEdge(f, t, w); // 正确：无向图需双向添加 addEdge(f, t, w); addEdge(t, f, w);

4.3 优先队列的陷阱

// 错误：未使用greater导致大根堆 priority_queue<PII> pq; // 正确：小根堆 priority_queue<PII, vector<PII>, greater<PII>> pq;

4.4 输入输出优化

// 关闭同步流加速IO（需确保不使用C风格IO） ios::sync_with_stdio(false); cin.tie(nullptr); // 对于1e4级别的输入，可节省约200ms

5. 完整AC代码实现

#include <bits/stdc++.h> using namespace std; const int N = 2005, M = 20005; struct Edge { int to, w, next; } edges[M]; int head[N], dis[N], cnt; bool vis[N]; void addEdge(int u, int v, int w) { edges[++cnt] = {v, w, head[u]}; head[u] = cnt; } void dijkstra(int start) { memset(dis, 0x3f, sizeof(dis)); dis[start] = 0; using PII = pair<int, int>; priority_queue<PII, vector<PII>, greater<PII>> pq; pq.emplace(0, start); while(!pq.empty()) { int u = pq.top().second; pq.pop(); if(vis[u]) continue; vis[u] = true; for(int i = head[u]; i; i = edges[i].next) { int v = edges[i].to, w = edges[i].w; if(dis[v] > dis[u] + w) { dis[v] = dis[u] + w; pq.emplace(dis[v], v); } } } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; while(m--) { int f, t, w; cin >> f >> t >> w; addEdge(f, t, w); addEdge(t, f, w); } dijkstra(1); cout << (dis[n] == 0x3f3f3f3f ? -1 : dis[n]); return 0; }

代码亮点：

1. 链式前向星存储节省内存
2. 堆优化保证时间复杂度
3. 输入输出优化提升速度
4. 处理了不可达情况（输出-1）