城市路P1381：四种最短路算法详解与选型指南

第一次做信息学奥赛一本通P1381“城市路”的人，大概率都有一种感觉：题面明明讲的是城市和道路，怎么就和Dijkstra绑在一起了。其实把城市看成点、道路看成带权边以后，这就是最经典的单源最短路问题，而P1381真正有价值的地方，是它能把四种主流做法全部牵出来讲清楚：朴素Dijkstra、堆优化Dijkstra、Bellman-Ford、SPFA。

我当年学这道题的时候，老师只讲了朴素版本，后来在校赛里被一道大范围正权图卡到怀疑人生，才回过头把其余三种写法补齐。你可以把P1381当成一个最短路模板实验场：数据范围不大、没有负权边、图结构也不复杂，非常适合把四种算法的原理、实现、复杂度差异一次性练明白。这篇文章适合两类人，一是刚学图论、第一次接触最短路的新手，二是已经会写模板、想系统梳理算法选型思路的备赛选手。下面我按“建图思路—四种算法原理—参考代码—避坑记录”的顺序，把这一整块内容完整讲一遍。

1. 先把 P1381 的图模型建明白

1.1 把“城市和道路”翻译成点和边

图论题能不能顺利做出来，第一道坎永远是建图。P1381的题面很朴素：有n个城市，编号从1到n；有m条道路，每条道路给出起点、终点和长度；最后问你从1号城市到n号城市的最短路径长度。翻译成图论语言就是：城市是节点，道路是有向边或双向边，道路长度是边权，目标是求单源最短路。

这里有一个特别容易被忽略的判断：题面说“两个城市之间可以沿道路通行”，到底是有向还是无向？如果是双向通行，加边时要同时加入u到v、v到u两条边；如果明确是单向道路，就只加一条。我见过太多人第一次提交错得莫名其妙，翻遍全代码找不到问题，最后发现就是漏了反向边。P1381流传的版本里有的给有向边，有的给无向边，务必以你手里的题面为准。

建完图之后，目标就很统一了：从起点s（通常为1号）跑一遍单源最短路算法，最后看dist[n]。如果dist[n]仍然是无穷大，说明城市1和城市n根本不在同一个连通块里，按题面要求输出约定的不可达值（一般是-1）。

存储方式也得跟着数据范围走。n很小的时候可以直接用邻接矩阵，读入重边的时候取min；n上了两三千，邻接表或链式前向星更省空间、遍历更快。我个人习惯用链式前向星写这道题，因为四个算法切换起来都方便，本质上它就是一个数组模拟的邻接表，比vector邻接表多一个next指针，理解起来并不难。

1.2 同一道题为什么值得写四种做法

很多初学者会问：一种算法能AC不就行了，为什么还要折腾四种？我的回答是：P1381最大的价值不是让你AC，而是让你在没有数据压力的模板环境里，把最短路里的四种“流派”全部理解透。

朴素Dijkstra讲的是贪心：为什么每次选dist最小的点标记为已确定，在正权边下是安全的。堆优化Dijkstra讲的是优化：当n大到几万，朴素写法里“每次O(n)找全局最小点”会成为瓶颈，优先队列能把这一步降到O(log n)。Bellman-Ford讲的是暴力之美：不管图长成什么样，我只要无脑把每条边松弛n-1轮，照样能求出正确答案，还能顺便检测负环。SPFA讲的是剪枝：既然只有被更新过的点才可能继续更新别人，那就用队列只记录这些“待定者”，把无效工作全部砍掉。

在真实比赛里，算法选型几乎直接决定你是AC还是TLE。拿到题目先看数据范围，再看边权有没有负数：正权大图用堆优Dijkstra，正权小稠密图用朴素Dijkstra；负权小图优先Bellman-Ford，负权稀疏图想快一点再考虑SPFA，但要有被卡超时的心理准备。表面上你只是在做一道题，实际上你把未来所有可能面对的最短路场景都提前演练了一遍。

2. 四种最短路算法的核心原理与适用场景

2.1 朴素Dijkstra：贪心思想的教科书

朴素Dijkstra的流程，我习惯用三步来记：

1. 初始化dist数组，起点为0，其余为INF，vis数组全false。
2. 循环n次，每次在未访问的点里找到dist最小的点u，把它标记成已确定。
3. 用u去松弛所有邻接点v：if (dist[v] > dist[u] + w) dist[v] = dist[u] + w。

为什么挑dist最小的点就一定“确定”了呢？因为图里没有负权边，所有边权都大于等于0，任何从其他未确定点绕到u的路径，要么直接走当前最短边，要么会经过一个dist更大的中间点，再加上一段非负边权，无论如何不会比当前dist[u]更小。所以一旦把u标记为已确定，它后面的dist值就不会再被其他路径改写了。

这个论证有一个致命前提：边权非负。我常举的反例是：1到2权5，1到3权6，3到2权-3。Dijkstra先看全局最小点，2的dist是5，3的dist是6，于是先确定2；可是1->3->2的总长度只有3，比5还小。Dijkstra已经跳进了坑里，后面再想爬出来就晚了。因此在做Dijkstra之前必须确认边权非负，P1381里的“道路长度”天然满足这一点，用起来很安全。

朴素版本的复杂度是O(n^2+m)。外层n轮选点、内层n个点找最小值，加上松弛所有边O(m)，整体约等于O(n^2)。当n在1000以内直接写完全没问题；当n到几万，每轮O(n)找最小值就会卡到怀疑人生。这也是为什么我建议初学者先把朴素版写熟，它逻辑最简单、debug最容易，后面做优化时你能清楚知道自己到底优化的是哪一步。

2.2 堆优化Dijkstra：把“选点”从O(n)降到O(log n)

朴素Dijkstra的瓶颈一眼就能看见：每次循环都要把所有点扫一遍找最小dist。如果能把“取全局最小”的操作交给一个每次O(log n)的数据结构，总复杂度就能从O(n^2)降到O(m log n)。标准做法是用优先队列，也就是小根堆，存pair<dist, 节点编号>。

流程是这样：

1. 起点s的dist设为0，把{0, s}压入小根堆。
2. 不断从堆顶取出dist最小且未被访问过的点u；如果堆顶这个点的dist已经被后面更新成更大的旧值，就continue跳过。
3. 标记u已确定，然后松弛它所有邻接边v。如果dist[v]被刷新变小，就把新的{dist[v], v}压入堆。

这里有个容易翻车的细节：优先队列默认是大根堆，要把它变成小根堆，得写 priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq。比赛里写错成默认大根堆，每次取出来的都是当前dist最大的点，整个算法逻辑全乱。我有一回就是只差一个greater，WA了快一个小时，排查到怀疑自己是不是眼睛出了问题。

堆优化Dijkstra的复杂度是O(m log n)。在稀疏图里，也就是m和n同一个数量级时，优势特别明显。比如n=10000、m=10000，朴素O(n^2)要跑上亿次，堆优只需要约一万次入堆加每次log级的弹出，完全不在一个量级。P1381这种数据两种写法都能过，但如果是n=1e5、m=2e5的大图，不想超时的话就老老实实用堆优。

再说两个实操细节。一是vis数组可写可不写，靠“堆里的dist和当前dist不一致”也能判断过期元素，但写vis逻辑更清晰，多数竞赛模板也会写。二是重边根本不用怕，同一个点可能被压入堆多次，出队时用vis或过期值判断自然就会过滤掉无效的那几次。

2.3 Bellman-Ford：无脑松弛n-1轮的暴力流派

Bellman-Ford的思路比Dijkstra更朴素：不需要找最小点，只需要把每条边看一遍，能松弛就松弛。核心就是两层循环：外层循环n-1轮，内层遍历所有边，对每条边u->v做一次dist[v] = min(dist[v], dist[u] + w)。

为什么是n-1轮？因为在无负环的图里，从起点出发到任意点的最短路，最多经过n-1条边。再多就会成环，绕环只会让路径更长。第1轮松弛能保证所有“只经过1条边”的最短距离正确；第2轮能保证“经过至多2条边”的正确；以此类推，等n-1轮跑完，所有点的最短距离自然就正确了。从动态规划的角度理解会更通透：外层是状态“最多经过k条边”，内层逐边转移，最后得到的就是全局最优。

判断负环的方式也很直接：跑完n-1轮之后再扫一遍所有边，如果还能发现某条边u->v满足dist[v] > dist[u] + w，说明存在负环。负环会让路径长度可以无限变短，最短路根本不存在，这时候算法应该返回不可行。

Bellman-Ford的复杂度是O(n*m)，非常慢，但它的优势是“不挑图结构”——不要求边权非负，也不依赖堆和队列。P1381用它能AC，但明显不是最优解，它更适合n很小、又带负权边的小数据场景。写这个算法时还要注意一个坑：松弛前一定要判断dist[u]是不是INF，否则INF加一个负权边可能溢出成很小的数，让整轮松弛直接“短路”。

2.4 SPFA：队列优化的Bellman-Ford，能打但怕卡

SPFA的全称是Shortest Path Faster Algorithm，本质是Bellman-Ford的队列优化版。它的出发点特别朴素：一轮把所有边都扫一遍，里面其实有很多边根本没有被松弛过，纯粹在浪费力气。不如只记录“哪些点变短了”，因为只有变短的点，它的出边才有资格去刷新别人。

实现用的就是一个队列：起点入队；每次弹出队首u，遍历u的出边，如果v的dist被刷新得更小，且v不在队列里，就让v入队。为了防止同一个点反复入队，加一个inq标记，入队置true，出队置false。这个标记如果忘了在出队时恢复成false，会导致该点之后再也不能参与松弛，答案错得非常离谱。

SPFA平均复杂度可以到O(m)，因为大多数点入队次数很少。但它的最坏复杂度会退化到O(n*m)，一些专门构造的数据能把SPFA卡成“地心历险记”。所以我在比赛中养成的习惯是：只有看到负权边才把SPFA拿出来；如果是正权最短路，一律堆优Dijkstra。P1381没有负权，用SPFA只是为了理解队列优化的思想，真正上场我更信任Dijkstra。

SPFA还有一个经典能力是判负环。记录cnt[v]为“从源点到v当前最短路边数”，每次更新时令cnt[v] = cnt[u] + 1。如果某个点的cnt超过n-1，说明存在一直让路径变短的环，负环无疑。这个技巧在差分约束、判定不等式组是否有解时特别常用。

3. 四种写法落到 P1381：核心代码与选型对比

3.1 先写建图，四个算法共用一套数据结构

先给出我写最短路时最喜欢的链式前向星建图代码，四个算法都基于它跑。

#include <bits/stdc++.h> using namespace std; const int INF = 0x3f3f3f3f; const int MAXN = 2505; const int MAXM = 10005; struct Edge { int to, w, nxt; } edge[MAXM]; int head[MAXN], tot; int dist[MAXN]; void addEdge(int u, int v, int w) { edge[++tot] = {v, w, head[u]}; head[u] = tot; }

读入部分按P1381常见的n、m处理：循环里读u、v、w，如果是双向道路，就调用两次addEdge(u, v, w)和addEdge(v, u, w)。链式前向星和vector邻接表相比，最直观的好处是空间连续、遍历时不产生太多的动态分配开销，在老旧评测环境里也更稳。如果你更习惯vector，完全可以用vector<pair<int,int>> g[MAXN]，原理一样，不影响后面的算法。

初始化记得memset(head, 0, sizeof(head)); memset(dist, 0x3f, sizeof(dist)); 这样每个算法开头都站在同一条起跑线上。

3.2 四种最短路核心函数一页纸

先看朴素Dijkstra。这个版本适合n不大的稠密图，我这里用邻接矩阵演示，注意重边取min。

int g[MAXN][MAXN]; bool vis[MAXN]; void dijkstra_plain(int s, int n) { memset(dist, 0x3f, sizeof(dist)); dist[s] = 0; for (int i = 1; i <= n; i++) { int u = -1, minD = INF; for (int j = 1; j <= n; j++) if (!vis[j] && dist[j] < minD) { minD = dist[j]; u = j; } if (u == -1) break; vis[u] = true; for (int v = 1; v <= n; v++) if (!vis[v] && g[u][v] != INF) dist[v] = min(dist[v], dist[u] + g[u][v]); } }

u == -1 时break这个细节很关键。如果图不连通，或者后面没有可继续扩展的点，提前跳出能省时间，也避免后续把不存在的点当成有效点。我刚开始写的时候漏了这个判断，在一个不连通的数据点上直接输出了错误答案。

再来看堆优化Dijkstra，这是实战里出场率最高的模板。

priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq; void dijkstra_heap(int s) { dist[s] = 0; pq.push({0, s}); while (!pq.empty()) { int d = pq.top().first; int u = pq.top().second; pq.pop(); if (vis[u]) continue; vis[u] = true; for (int i = head[u]; i; i = edge[i].nxt) { int v = edge[i].to; if (dist[v] > dist[u] + edge[i].w) { dist[v] = dist[u] + edge[i].w; pq.push({dist[v], v}); } } } }

注意dist数组必须在进入函数前已经memset成INF，并且dist[s]设成0。如果漏了memset，后面全是毒。堆优版在P1381的数据范围里一样AC，换到任何大图也不过时，属于必须背下来的模板。

Bellman-Ford的核心代码：

struct EdgePlain { int u, v, w; }; vector<EdgePlain> e; bool bellman_ford(int s, int n) { memset(dist, 0x3f, sizeof(dist)); dist[s] = 0; for (int i = 1; i < n; i++) { bool update = false; for (auto &ed : e) { if (dist[ed.u] != INF && dist[ed.v] > dist[ed.u] + ed.w) { dist[ed.v] = dist[ed.u] + ed.w; update = true; } } if (!update) break; } for (auto &ed : e) if (dist[ed.u] != INF && dist[ed.v] > dist[ed.u] + ed.w) return false; // 有负环 return true; }

返回值直接告诉你是否存在负环。P1381本身没有负权，所以这里的负环判断只是教学演示，真遇上判断负环的题再把它拿出来用。

SPFA的核心代码：

queue<int> q; bool inq[MAXN]; int cnt[MAXN]; bool spfa(int s, int n) { memset(dist, 0x3f, sizeof(dist)); dist[s] = 0; q.push(s); inq[s] = true; while (!q.empty()) { int u = q.front(); q.pop(); inq[u] = false; for (int i = head[u]; i; i = edge[i].nxt) { int v = edge[i].to; if (dist[v] > dist[u] + edge[i].w) { dist[v] = dist[u] + edge[i].w; cnt[v] = cnt[u] + 1; if (cnt[v] >= n) return false; // 存在负环 if (!inq[v]) { q.push(v); inq[v] = true; } } } } return true; }

SPFA里最容易被忽略的就是出队时别忘了inq[u] = false。假如你在一次更新后把v入队，却在v弹出时忘记恢复标记，之后v距离再次被更新时就不会再入队，答案错得非常隐蔽。我的排查经验是打印每个点的入队次数，正常情况应该远小于n，一旦某个点疯狂入队，不是有负环就是标记逻辑写错了。

3.3 四个算法的复杂度与选型对照

我把自己的整理结果放在一张表里，练习时贴在题目旁边很方便。

选型时我基本按三个问题走：

1. 边权有负数吗？有，就别碰Dijkstra，去Bellman-Ford或SPFA。
2. m接近n还是接近n^2？接近n用堆优，接近n^2用朴素也没问题。
3. 要不要判负环？只要题目问“是否存在负环”这类话，SPFA或Bellman-Ford都行，我更喜欢SPFA加cnt计数。

P1381本身是正权图，数据范围也没大到夸张，任何一种都能AC。但从养成正确习惯的角度，我建议默认堆优Dijkstra，它既稳定又能扛大图。等以后遇到负权边，再接上SPFA那一套，就能无缝切换。

4. 实战中的常见问题与排查方案

4.1 初始化的门道：INF为什么用0x3f3f3f3f

几乎每个初学者都会问，为什么不用INT_MAX？核心原因有两个，一个是溢出，一个是memset。

INT_MAX大约是21亿，如果dist[u]是INT_MAX，再遇到一个负权边比如-3亿，dist[u] + w就可能溢出成负数，导致所有松弛逻辑全部崩坏。而0x3f3f3f3f大约是10.6亿，两个这样的数相加约21.2亿，仍然没有超过int的上限。所以即使出现INF加上某个正权边的操作，也不会溢出，这一点在Dijkstra里尤其重要，因为松弛时会频繁写dist[u] + w。

另一个原因是0x3f3f3f3f的每个字节都是0x3f，memset(dist, 0x3f, sizeof(dist))能把int数组每个字节填成0x3f，恰好得到0x3f3f3f3f。这让初始化变成一行代码，不用写循环。如果换成一个没那么规整的数，比如1e9，就没法用memset直接填，必须用fill或for循环。

输出时也要注意：如果最后dist[n]仍然等于INF，说明1号和n号不在同一个连通块里。我建议先判断if (dist[n] == INF) 输出-1，再输出dist[n]，别把那个巨大的INF直接打出来。

4.2 建图最容易错的三个点

第一是双向边漏加。P1381如果题面说“城市之间可以相互通行”，就必须add(u->v)和add(v->u)都加。有些同学自测小样例答案碰巧对了，是因为数据里恰好有对称边或者起点终点特殊，多组数据一上来就暴露。我的习惯是建图后立刻检查边的总数，无向图预期应该是2*m，如果发现只有m，多半就是漏了反向加边。

第二是重边没处理。邻接矩阵存图时，同一对点之间如果有多条道路，读入时一定要g[u][v] = min(g[u][v], w)，否则只会记最后一条，可能留下了较大那条导致答案偏大。邻接表和链式前向星则天然保留所有重边，算法会在多条边中自动取最短，所以无脑add进去即可，不需要额外处理。

第三是起点和终点的编号。P1381有些版本起点是1、终点是n，也有版本是s和t。遇到后者，调用算法时一定要把参数传对。我见过不只一个人在主函数里写了Dijkstra(1)，却忘了题目实际的终点是t，调半天才发现是调用参数的问题。

4.3 四种算法各自的经典翻车点

我把这些年见过的高频错误整理成速查表，照着排雷能省下大量时间。

比如堆优Dijkstra，如果忘了greater，堆就变成大根堆，每次弹出的都是当前dist最大的点，相当于随机挑点松弛，结果必然不对。这一类细节光盯屏幕很难看出来，拿手推样例逐行走一遍，问题定位会非常快。

4.4 一个实用测试套路：用小数据自查

写完代码以后，建议先测三组小数据再交大样例。第一组是n=1、m=0，答案应该为0；第二组是不连通图，比如n=3只有一条1到2的边，问从1到3是否无解；第三组是重边，比如1到2有两条边，长度分别为5和2，期望答案是2。

这三组数据基本能把建图和松弛逻辑的问题逼出来。我每次写完最短路题都会强制自己跑一遍这三组，多年下来已经成了肌肉记忆。数据规模再大以后，还可以自己写一个随机图生成器，拿朴素Dijkstra当暴力对拍器，跑出来的结果和堆优Dijkstra逐点比对，一旦不一样，就说明某个地方写坏了。

5. 从 P1381 延伸出去：最短路还能怎么考

5.1 现在学的模板，后面都用在哪儿

P1381只是最短路这条线的一个起点。后续的常见变式，基本都是在这四个模板上继续叠东西：

负权与负环题，用Bellman-Ford或SPFA判负环，题目一换皮就成了“是否存在无限缩短路径”；多源最短路，有多个起点要同时求，往往在Dijkstra堆里先把所有起点压进去，一趟跑完；次短路、计数最短路，在dist之外再存一个次小值或方案数，松弛时多写几个分支；分层图，比如允许免费坐几次车，把图复制成好几层，在层之间加边权为0的边，再用Dijkstra做跨层搜索；差分约束，把形如a-b<=c的不等式组建模成边，靠判负环检测无解，核心还是SPFA。

这些变式如果现在不把底层模板吃透，后面叠buff的时候会越写越乱。所以我一直建议把P1381当成自己的模板库沉淀点，四种算法像乘法口诀一样背熟。

5.2 一个适合大多数人的学习顺序建议

我个人推荐的学习顺序是：朴素Dijkstra -> 堆优化Dijkstra -> Bellman-Ford -> SPFA -> Floyd。前四个刚好是这篇文章主讲的四条路，Floyd适合n只有三四百的稠密小图，是全源最短路，也值得顺手掌握。

学的时候每学一个新算法，就把P1381重写一遍。不要只看模板，一定亲手敲，然后拿三组自测数据过一遍。敲完第四遍以后你会发现，不同算法之间共享的只有dist和松弛思想，区别只在谁先确定、谁入队、谁扫描所有边，脑子里那条图论主线就彻底打通了。

最后分享一个我自己的小习惯：正式比赛里遇到正权最短路，我默认堆优Dijkstra，几乎不临时换方案，因为它在各种数据规模下都很稳；遇到有负权的题，小数据用Bellman-Ford求稳，大数据再考虑SPFA。如果你也能建立起这种“拿到题目先问自己三个问题”的条件反射，那P1381这道题就没有白刷。