第一次做信息学奥赛一本通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很小的时候可以直接用邻接矩阵读入重边的时候取minn上了两三千邻接表或链式前向星更省空间、遍历更快。我个人习惯用链式前向星写这道题因为四个算法切换起来都方便本质上它就是一个数组模拟的邻接表比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的流程我习惯用三步来记初始化dist数组起点为0其余为INFvis数组全false。循环n次每次在未访问的点里找到dist最小的点u把它标记成已确定。用u去松弛所有邻接点vif (dist[v] dist[u] w) dist[v] dist[u] w。为什么挑dist最小的点就一定“确定”了呢因为图里没有负权边所有边权都大于等于0任何从其他未确定点绕到u的路径要么直接走当前最短边要么会经过一个dist更大的中间点再加上一段非负边权无论如何不会比当前dist[u]更小。所以一旦把u标记为已确定它后面的dist值就不会再被其他路径改写了。这个论证有一个致命前提边权非负。我常举的反例是1到2权51到3权63到2权-3。Dijkstra先看全局最小点2的dist是53的dist是6于是先确定2可是1-3-2的总长度只有3比5还小。Dijkstra已经跳进了坑里后面再想爬出来就晚了。因此在做Dijkstra之前必须确认边权非负P1381里的“道路长度”天然满足这一点用起来很安全。朴素版本的复杂度是O(n^2m)。外层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)。标准做法是用优先队列也就是小根堆存pairdist, 节点编号。流程是这样起点s的dist设为0把{0, s}压入小根堆。不断从堆顶取出dist最小且未被访问过的点u如果堆顶这个点的dist已经被后面更新成更大的旧值就continue跳过。标记u已确定然后松弛它所有邻接边v。如果dist[v]被刷新变小就把新的{dist[v], v}压入堆。这里有个容易翻车的细节优先队列默认是大根堆要把它变成小根堆得写 priority_queuepairint,int, vectorpairint,int, greaterpairint,int pq。比赛里写错成默认大根堆每次取出来的都是当前dist最大的点整个算法逻辑全乱。我有一回就是只差一个greaterWA了快一个小时排查到怀疑自己是不是眼睛出了问题。堆优化Dijkstra的复杂度是O(m log n)。在稀疏图里也就是m和n同一个数量级时优势特别明显。比如n10000、m10000朴素O(n^2)要跑上亿次堆优只需要约一万次入堆加每次log级的弹出完全不在一个量级。P1381这种数据两种写法都能过但如果是n1e5、m2e5的大图不想超时的话就老老实实用堆优。再说两个实操细节。一是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完全可以用vectorpairint,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_queuepairint,int, vectorpairint,int, greaterpairint,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; }; vectorEdgePlain 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的核心代码queueint 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 四个算法的复杂度与选型对照我把自己的整理结果放在一张表里练习时贴在题目旁边很方便。算法时间复杂度能处理负权边能判负环适合场景朴素DijkstraO(n^2m)不能不能n小、稠密图比如n≤2000的完全图堆优化DijkstraO(m log n)不能不能稀疏图首选n、m大的正权图Bellman-FordO(n*m)能能n很小但有负权边SPFA平均O(m)最坏O(n*m)能能有负权且图比较友好需防卡数据选型时我基本按三个问题走边权有负数吗有就别碰Dijkstra去Bellman-Ford或SPFA。m接近n还是接近n^2接近n用堆优接近n^2用朴素也没问题。要不要判负环只要题目问“是否存在负环”这类话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的每个字节都是0x3fmemset(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忘记vis标记就继续更新u-1时break漏写松弛循环里加if(!vis[v])再打印vis数组确认点是否被二次更新堆优化Dijkstra优先队列没写greater没判断dist[v] dist[u] w把每次堆顶弹出的dist打印出来和手推样例对照Bellman-Ford松弛时没判断dist[u] ! INF负环判断提前到第n-1轮用小样例手工模拟一轮看INF是否被负权拽成小值SPFA出队时没恢复inq[u]负环的cnt统计错误打印每个点的入队次数正常情况应远小于n比如堆优Dijkstra如果忘了greater堆就变成大根堆每次弹出的都是当前dist最大的点相当于随机挑点松弛结果必然不对。这一类细节光盯屏幕很难看出来拿手推样例逐行走一遍问题定位会非常快。4.4 一个实用测试套路用小数据自查写完代码以后建议先测三组小数据再交大样例。第一组是n1、m0答案应该为0第二组是不连通图比如n3只有一条1到2的边问从1到3是否无解第三组是重边比如1到2有两条边长度分别为5和2期望答案是2。这三组数据基本能把建图和松弛逻辑的问题逼出来。我每次写完最短路题都会强制自己跑一遍这三组多年下来已经成了肌肉记忆。数据规模再大以后还可以自己写一个随机图生成器拿朴素Dijkstra当暴力对拍器跑出来的结果和堆优Dijkstra逐点比对一旦不一样就说明某个地方写坏了。5. 从 P1381 延伸出去最短路还能怎么考5.1 现在学的模板后面都用在哪儿P1381只是最短路这条线的一个起点。后续的常见变式基本都是在这四个模板上继续叠东西负权与负环题用Bellman-Ford或SPFA判负环题目一换皮就成了“是否存在无限缩短路径”多源最短路有多个起点要同时求往往在Dijkstra堆里先把所有起点压进去一趟跑完次短路、计数最短路在dist之外再存一个次小值或方案数松弛时多写几个分支分层图比如允许免费坐几次车把图复制成好几层在层之间加边权为0的边再用Dijkstra做跨层搜索差分约束把形如a-bc的不等式组建模成边靠判负环检测无解核心还是SPFA。这些变式如果现在不把底层模板吃透后面叠buff的时候会越写越乱。所以我一直建议把P1381当成自己的模板库沉淀点四种算法像乘法口诀一样背熟。5.2 一个适合大多数人的学习顺序建议我个人推荐的学习顺序是朴素Dijkstra - 堆优化Dijkstra - Bellman-Ford - SPFA - Floyd。前四个刚好是这篇文章主讲的四条路Floyd适合n只有三四百的稠密小图是全源最短路也值得顺手掌握。学的时候每学一个新算法就把P1381重写一遍。不要只看模板一定亲手敲然后拿三组自测数据过一遍。敲完第四遍以后你会发现不同算法之间共享的只有dist和松弛思想区别只在谁先确定、谁入队、谁扫描所有边脑子里那条图论主线就彻底打通了。最后分享一个我自己的小习惯正式比赛里遇到正权最短路我默认堆优Dijkstra几乎不临时换方案因为它在各种数据规模下都很稳遇到有负权的题小数据用Bellman-Ford求稳大数据再考虑SPFA。如果你也能建立起这种“拿到题目先问自己三个问题”的条件反射那P1381这道题就没有白刷。