1. CSP-S为什么绕不开Dijkstra先说结论在信奥赛CSP-S提高级的图论题里Dijkstra算法不是“考不考”的问题而是“怎么考”的问题。最近几年的真题反复证明了这一点比如涉及最短路径的题目十道里有八道最终解法落脚在Dijkstra及其堆优化版本上。你要是准备参加CSP-S这个算法属于绕不过去的核心知识点跟动态规划、树状数组、二分答案这些东西一样属于必须烂熟于心的基础工具。很多刚学图论的同学会有个误区Dijkstra不就是个求最短路径的模板题吗背个板子就行。但实际比赛中Dijkstra极少以“裸题”形式出现。它更多是作为一道综合题的内层核心外面套着状态压缩、二分答案、建图技巧甚至数学推导。也就是说光会背模板不够你得真正理解这个算法每一步在干什么、为什么能这么干、它在什么情况下会失效以及怎么去优化它。这篇文章我不打算写成一板一眼的教材而是按我带选手备赛时习惯的讲法走一遍从最朴素的思路开始讲清楚原理再推到堆优化版本然后重点讲赛场上真正拉开差距的部分——各种变形考法、常见卡时间和踩坑点。最后配一组我实际带学生时高频遇到的报错和编码问题给你一份能直接照着用的避坑清单。2. Dijkstra算法的核心思想与适用边界1.1 贪心策略的通俗理解Dijkstra算法的本质是贪心。贪心在什么地方一句话概括每次从未确定最短路的点里挑一个当前距离最小的点把这个点标记为“已确定”然后拿它去松弛其他还没有确定的点。听起来很简单但这里的逻辑恰恰是初学者最容易糊涂的地方。我经常跟学生打一个比方假设你在一个迷宫里手里有一堆写着“到起点距离”的便签。一开始你只知道起点的距离是0其余全是无穷大。你每次做的事情是在所有还没贴过“终审通过”标签的岔路口里找距离最小的那个认定它已经不可能再被其他路“绕近”了然后基于这个点去更新它相邻路口的便签。重复这个过程直到所有路口都贴上“终审通过”。这里最关键的判断是为什么当前距离最小的那个点它的最短路就可以被“锁定”了原因在于所有边权非负。如果边权存在负数那么可能出现这种情况某个点当前距离是5但有一条很远的路径通过一条负边绕过来最终到它的距离变成了2。这样一来当前距离最小的点也不能被信任贪心策略就直接崩溃了。1.2 为什么边权必须非负我在课堂上习惯让同学们记住一个反例比背十遍“边权必须非负”都管用。考虑三个点起点A直接到B边权是5A到C边权是2C到B边权是-4。如果按Dijkstra来做一开始A相邻的点是B和CB距离5C距离2于是优先确定C。接着用C去松弛B发现B可以被更新成2 (-4) -2比原来的5小。问题来了B之前已经被标记为“已确定”了现在又被更新了那这个“已确定”状态还算数吗程序如果还按旧的5来处理B的后继节点结果全是错的。所以Dijkstra的有效性完全建立在“非负边权”之上。一旦题目里出现负权边你就得换SPFA或者Bellman-Ford。CSP-S的题目里大部分最短路问题默认边权非负所以Dijkstra是主力但审题时还是要留个心眼万一出现负权边及时切算法。1.3 适用场景与复杂度评估Dijkstra适用的典型场景包括单源最短路径、多源最短路径加超级源点、带限制的最短路问题、路径计数、次短路等等。复杂度上最朴素的O(n^2)版本适合稠密图堆优化版本O((nm)log n)适合稀疏图。CSP-S的数据范围通常是n在10^5到10^6级别、m在10^5到10^6级别这种情况下O(n^2)直接超时必须用堆优化。但反过来如果n只有200、300稠密图用堆优化反而不如朴素版快因为堆的常数更大。比赛时先看数据规模再决定用哪个版本这个意识很重要。3. 从朴素版到堆优化完整推导与代码实现2.1 朴素Dijkstra的代码结构与执行流程先上一版最简单的、不搞花活的朴素Dijkstra。这样的代码适合在初学阶段用来理解流程也适合n比较小、图比较密集的情况。#include bits/stdc.h using namespace std; const int INF 0x3f3f3f3f; int n, m, s; int dist[1005]; bool vis[1005]; int g[1005][1005]; void dijkstra(int s) { memset(dist, 0x3f, sizeof(dist)); memset(vis, 0, sizeof(vis)); dist[s] 0; for (int i 1; i n; i) { int u -1; int minDist INF; for (int j 1; j n; j) { if (!vis[j] dist[j] minDist) { minDist 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]); } } } } int main() { cin n m s; memset(g, 0x3f, sizeof(g)); for (int i 1; i n; i) g[i][i] 0; for (int i 0; i m; i) { int u, v, w; cin u v w; g[u][v] min(g[u][v], w); // 防重边 } dijkstra(s); for (int i 1; i n; i) { cout (dist[i] INF ? -1 : dist[i]) ; } return 0; }这段代码的逻辑很直白外层循环跑n次每次找当前未确定集合中dist最小的点找到后把它标记为已确定然后遍历所有邻接点做松弛。复杂度O(n^2)主要开销在“找最小”的那层循环上。有一点在初学者代码里特别常见用memset(g, 0x3f, sizeof(g))做初始化。0x3f3f3f3f这个数大约是10亿出头两个这样的数相加不会溢出int范围所以可以放心做dist[u] g[u][v]的加法。很多新手习惯初始化为INT_MAX一加直接溢出变成负数排查半天都找不到原因。这一点属于最经典的Dijkstra踩坑点后面我还会专门讲。2.2 为什么需要堆优化当n达到10^5级别O(n^2)意味着10^10次操作在任何竞赛环境下都不可能通过。堆优化的思路其实就是把“找当前未确定点中dist最小的点”这件事从线性扫描换成优先队列二叉堆的堆顶弹出时间复杂度从O(n)降到O(log n)。总复杂度从O(n^2)降到O((nm)log n)。关于堆优化的细节我特别想强调一点优先队列里存的是(dist, u)对dist相同时谁先弹出无所谓。但同一时间队列里可能有多个关于同一个节点的记录比如某个点先被松弛成10后来又松弛成7那队列里就同时存在(10, u)和(7, u)。我们靠vis[u]来判断如果u已经确定了直接跳过。这种“懒删除”的操作在实现里最省事。还有一种写法是直接定义一个pairint, int按first排序但C的priority_queue默认是大根堆所以要取负号或者自己写比较器。不少同学喜欢priority_queuepairint, int, vectorpairint, int, greaterpairint, int这样是对的但记得把dist放first节点编号放second因为优先队列默认先比较first。2.3 堆优化版完整实现下面这版是我平时推荐给学生的标准写法配合前向星存图跑大部分题目都没问题。#include bits/stdc.h using namespace std; const int INF 0x3f3f3f3f; const int MAXN 100005; struct Edge { int to, w, next; } edge[MAXN * 2]; // 无向图开两倍 int head[MAXN], tot; int dist[MAXN]; bool vis[MAXN]; void addEdge(int u, int v, int w) { edge[tot].to v; edge[tot].w w; edge[tot].next head[u]; head[u] tot; } void dijkstra(int s) { memset(dist, 0x3f, sizeof(dist)); memset(vis, 0, sizeof(vis)); dist[s] 0; priority_queuepairint, int, vectorpairint, int, greaterpairint, int pq; pq.push({0, s}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (vis[u]) continue; vis[u] true; for (int i head[u]; i ! -1; i edge[i].next) { int v edge[i].to; int w edge[i].w; if (dist[v] dist[u] w) { dist[v] dist[u] w; pq.push({dist[v], v}); } } } } int main() { int n, m, s; cin n m s; memset(head, -1, sizeof(head)); tot 0; for (int i 0; i m; i) { int u, v, w; cin u v w; addEdge(u, v, w); addEdge(v, u, w); // 如果是无向图 } dijkstra(s); for (int i 1; i n; i) { cout (dist[i] INF ? -1 : dist[i]) ; } return 0; }这个版本里有一点容易写错前向星的head数组初始化成-1边数组的下标从0开始累加。遍历的时候for (int i head[u]; i ! -1; i edge[i].next)别写成i 0不然初学阶段很容易把自己绕晕。另外如果题目是有向图别加那两行无向边。2.4 关于优先队列的细节为什么pair的排序没问题很多学生在使用pairint, int时有个疑问如果两个点的dist相同优先队列怎么处理答案是随便处理先弹哪个都行。因为Dijkstra的正确性只依赖“每次弹出的是当前最小dist的点”dist相同说明它们的优先级相同先后顺序不影响结果。但如果题目需要按某种规则输出路径比如编号小的优先那就需要在pair里再加维度或者自定义比较器。这种情况在CSP-S里比较少但我在练习赛中见过可以留个印象。另一个细节是priority_queue默认是大根堆竞赛里我习惯用greaterpairint,int包一层比写struct cmp省事。如果要追求常数可以手动写二叉堆或者用__gnu_pbds的配对堆但一般情况下不带必要。2.5 稠密图时的选择n小m大怎么办堆优化并不是万能的。当n只有500、m接近n^2时优先队列的常数反而可能拖慢速度。这时候朴素版的O(n^2)更稳定。我见过有同学在n1000、m10^6的稠密图上用堆优化结果跑了1秒多反而是朴素版秒出。比赛题的图通常造得很有针对性如果n是10^5、m是10^5那必是稀疏图用前向星加堆优化没问题。如果n是200、m是20000那直接邻接矩阵加朴素Dijkstra最舒服。所以看到数据范围先想想图是疏还是密再决定用哪个板子不要无脑套堆优化。4. 信奥赛里Dijkstra的常见变形考法3.1 多源最短路与超级源点不少题目不是求“从一个点出发到所有点的最短路”而是“从若干个起点中的任意一个出发到某个终点的最短路”。比如有k个补给站求任意一个补给站到城市的最短距离。常见做法是引入一个超级源点0从0到每个补给站连一条权值为0的边然后跑一遍从0出发的Dijkstra。这个方法的原理非常巧妙超级源点到各补给站距离为0那么超级源点到达任意点的最短路就等于最近的补给站到该点的最短路。相当于把k次Dijkstra降成1次。这在复杂度上是巨大优化。注意一个实现细节0号节点需要占用一个编号并且建图时要把0号节点正常加入。很多同学忘记把dist[0]初始化为0导致整个算法跑出来的全是INF调试半天才发现是超级源点自己没设好。3.2 最短路径条数CSP-S里也常出现“求最短路径有多少条”的题。这时Dijkstra在松弛时要额外维护一个cnt[u]。转移逻辑是如果dist[v] dist[u] w说明找到了更短路此时cnt[v] cnt[u]。如果dist[v] dist[u] w说明有另一条同样短的路此时cnt[v] cnt[u]。这个加法可能很大题目通常要求取模。有个隐藏的坑当有多条路径都到达同一个点时cnt[v]可能被重复加但因为我们是在弹出u时更新v每个u只会被处理一次所以计数逻辑是可靠的。前提是vis的标记时机要正确必须在弹出时标记不能入队时标记。我自己教学生时习惯让他们记住一句话最短路径计数不是简单的BFS层次遍历必须把“更短更新”和“相等累加”分开处理。很多人在相等时忘记累加或者在更短时忘记覆盖而不是累加最后答案差一点检查半天才发现。3.3 带状态的最短路分层图分层图是Dijkstra在提高组里一个很重要也很常见的延伸。比如题目要求“最多可以让k条边的边权变成0”求最短路。这时候可以建k1层图第i层表示“已经使用了i次免费机会”。在层与层之间连权值为0的边表示“在这条边上使用了免费机会”。用Dijkstra跑分层图本质上就是把“状态”并入到节点编号里。每个状态是(当前点, 已用免费次数)对应一个独立的节点。最终答案就是min_{i 0..k} dist[n i * n]也就是第i层里原终点n的最短距离。分层图最需要注意的是空间。k如果到20n是10^5那节点数就是2*10^6级别边数还要乘以层数很容易爆数组。所以开数组时一定要算清楚MAXN * (k1)边也要开够。很多时候不是算法不会写而是边数组开小了运行直接越界表现出来却是答案全错。3.4 次短路问题次短路严格次短或非严格次短也是一个高频变形思路是维护两个dist数组dist1[u]表示最短路dist2[u]表示次短路。松弛的时候先用新值尝试更新最短路如果更新不了最短路就尝试更新次短路。具体逻辑如果nd dist1[u]则把当前dist1[u]降级成dist2[u]再用nd替换dist1[u]。否则如果nd dist1[u] nd dist2[u]则更新dist2[u]。最后答案取dist2[终点]。这里很多同学漏掉“降级”这一步。当发现一个更短的路时原来的最短路就自动变成了次短路候选必须把原来的dist1[u]赋给dist2[u]否则次短路会丢数据。这个细节在考试中特别容易考因为样例数据可能很小看不出问题但一到大数据就直接WA。3.5 二维坐标网格中的Dijkstra还有一种常见考法是网格图每个格子有权值求从左上到右下的最小代价。这种题虽然也可以用BFS做但一旦格子权值不同BFS就不再适用于求最小代价而是需要Dijkstra。网格图本身边的数量是O(4n)级别堆优化跑起来毫无压力。网格题里有个容易踩的坑把二维坐标映射成一维编号时写错。个人建议直接用二维dist数组但Dijkstra的优先队列里存的是坐标那就要把坐标编码成一个int或者直接用pairint,int做节点。如果题目要求路径输出还需要额外维护前驱这又要注意内存开销。5. 真题实战以常见题型为例4.1 从一道经典练手题看建图与输出我拿一个典型的CSP-S风格题来举例给定n个城市和m条双向道路每条道路有长度求从城市1到城市n的最短距离。多数情况下这就是纯裸题背面堆优化版Dijkstra就能过。但有些题会在输入格式上使绊子比如给的边有重边那就在读入时取最小值比如是稀疏图但n很大那就要用map存邻接表否则邻接矩阵直接开不下。实际做题时我会按这个顺序来先看n的范围如果n小于等于2000可以考虑邻接矩阵加朴素Dijkstra如果n大于2000必定用前向星或vector邻接表加堆优化。然后是m的范围m很大时说明图密集这时候vector邻接表的遍历也会比较慢需要思考要不要换写法。建图的方式我在代码里常选前向星因为它的内存连续遍历快。但对很多初学者来说vectorvectorpairint,int更直观。两种写法都可以关键是自己顺手、不出错。比赛中最怕的不是复杂度不够而是写着写着指针越界、数组开小。4.2 典型提高组真题思路拆解非题目原文有一类题是这样的给出若干个公交站点和线路每条线路是一个环形站点之间通行时间已知求从一个站点到另一个站点的最短时间。直接建图会遇到“同一线路上的任意两个站点都能直达”这种特殊关系如果完全展开边数会是O(k^2)爆炸。常规解法是把每条线路抽象成一个虚点站点到该线路的虚点连一条权值为0或固定费用的边虚点到站点再连一条边这样就把二次方级别的边数压缩成线性级别。然后用Dijkstra跑。这种“虚点建图”的思路在提高组里极其常见比单纯套最短路径模板高一个维度。这类题目最值得研究的不是Dijkstra本身而是如何把题目条件转化成图上的边。我一直和学生强调CSP-S的图论题重点在建模Dijkstra只是最后那一下的“执行者”。建模建对了算法只是工具建模错了再熟练的模板也救不了。4.3 比赛中的输出格式陷阱Dijkstra题还有一个很容易丢分的地方——输出格式。题目经常要求“如果不可达输出-1”但有些题要求输出一个很大的数比如2^31-1或者输出impossible。我看到过不少学生算法完全正确却在输出判断上栽了跟头。所以我建议在写主函数输出部分时先看清楚题目说明是“不存在时输出-1”还是“保证可达”还是“输出INF时用特定字符串”。别小看这个细节很多正式比赛中一道题的满分线就卡在这里。6. 常见报错与调试排查技巧实录5.1 数组开太小导致的神秘越界有次一个学生跑一个n100000的题Dijkstra写得很标准但一提交就段错误。查了很久才发现前向星边数组只开了MAXN而题目是无向图意味着边数要乘以2。他加边时又加了每条无向边的两个方向实际边数是2m数组却只开了m大小。数据一大直接越界写坏了邻接区域表现出来就是dist数组莫名其妙被改成极小或极大的值。这类问题靠肉眼很难看到建议在本地用较大数据跑开AddressSanitizer或者用-fsanitizeaddress编译能直接定位越界位置。如果比赛环境不允许那就只能靠平时形成习惯无向图边数组开2 * MAXM有向图开MAXM再额外多开5到10的余量。5.2 memset初始化INF的误区很多人习惯memset(dist, 0x3f, sizeof(dist))这个写法本身没问题0x3f3f3f3f是一个足够大的数。但有个隐患如果某个题目的边权可能很大比如1e9级别的边长那么dist[u] w就可能超过0x3f3f3f3f导致比较出错。更安全的方式是把INF设成一个比“所有理论最短路的最大值”更大的数比如LLONG_MAX / 4再用long long存储dist。很多同学一上来用int存dist结果边权累加超过2^31溢出成负数Dijkstra直接乱套。所以看到数据范围里单条边权重达到1e9或者路径长度可能超过int范围直接改用long long。这里不要省宁可在每个地方多写两个字母也不要让溢出坑你一整场比赛。5.3 优先队列里的“脏数据”处理堆优化Dijkstra里同一个点可能被多次push进优先队列。有的同学会在if (vis[u]) continue;之前加一句if (d ! dist[u]) continue;这也是一个优化。其实这两种写法都能用效果一样。区别只在于只判断vis会稍微多做几次无用的循环但代码更简洁判断dist是否等于当前值能跳过更早的“脏数据”。我在实现时通常只写if (vis[u]) continue;因为更短且不容易漏判。如果不用vis而改用if (d ! dist[u]) continue;那么在初始化时dist[s] 0入队(0, s)后续某个时候s可能被再次入队(更大的值)这时d ! dist[s]能拦住它。但注意如果同一个点在不同时刻有相同距离被push比如dist都是5那这种拦截就失效了好在相同距离不影响答案所以也没问题。5.4 负数边权下Dijkstra的错误表现来一个经典的实战案例学生拿到一道带负权边的最短路题没注意看题直接套Dijkstra样例也过了。一提交WA。我让他打印中间过程发现某个点因为负边被更新了两次但vis已经为true导致更新被忽略。后面所有依赖这个点的最短路径都算错。负权边的标准解法是SPFA但对于特别大的数据SPFA可能被卡。所以CSP-S里大部分题不会出负权边一旦出了就说明出题人想让你用SPFA或Bellman-Ford。审题时如果看到“边权可为负数”立刻放弃Dijkstra不要犹豫。5.5 重边和自环的处理题目里经常不会保证没有重边和自环。自环不影响Dijkstra因为从u到u的边权如果为正永远不会更新dist[u]如果为负又会导致算法不适用。重边则会在建图时造成麻烦如果存邻接矩阵直接取min即可如果存前向星或vector那多几条边只是稍微多几次松弛不会出错。不过要注意如果题目要求输出路径重边会导致路径选择不唯一这时需要想清楚题目希望输出哪条。通常题目会明确“任意一条即可”所以问题不大。5.6 一个我自己也踩过的坑从INF判断不可达还有一个细节是判断不可达时不要用dist[i] INF因为有的路径长度可能恰好等于INF值如果在某种特殊数据构造下。更稳妥的方法是把INF设成一个比所有可能答案都大的数比如1e18再配合long long使用。这样dist[i] INF的判断才是安全的。我在带学生时反复强调INF不是随便写一个很大的数就行的它必须满足“INF 任意边权仍大于INF”这个条件这样在松弛时不会误更新。如果INF取INT_MAX加上一个正数会溢出成负数那整个算法直接从内部崩掉。这是新手最容易踩的坑没有之一。5.7 调试技巧从暴力对拍到样例构造很多同学Dijkstra写错了却不知道从哪查起。我的习惯是先用朴素BFS或者Floyd写一个暴力版本在n很小的情况下对比Dijkstra的结果。一旦有差异立刻缩小范围。这个思路我称为“暴力对拍”是竞赛里最有效的排错方式。还可以自己构造特殊样例一条链、一个环、一个星形图再加大一点的随机图反复跑。Dijkstra的常见错误在这几类图上基本都会暴露。比如链上某个点被跳过、环里某个方向没遍历到、星形图中心节点被重复松弛这些都能通过手工样例快速定位。7. 实战后的经验总结与下一步建议Dijkstra这个算法表面上看只是一个模板但它的变形和细节在CSP-S里能延伸出一大片题目。朴素版、堆优化版、分层图、次短路、路径计数、多源最短路、虚点建图每一块都值得单独写一篇笔记。我个人的建议是先把朴素版彻底吃透能手写出来并解释每一步为什么这么写再上堆优化。别一上来就直接背堆优化模板那样出了问题根本没有排查能力。从做过的真题来看CSP-S里图论的比重并不低而Dijkstra又是最短路问题里的绝对主力。把这块基础打牢后面学SPFA、Floyd、网络流时会轻松很多。如果时间允许可以拿近五年的真题里所有图论题拉出来统一用Dijkstra的思路先分析建模再看题解验证。这个过程坚持下来对建图能力的提升会非常明显。最后再分享一个小技巧我习惯在本地维护一个“Dijkstra模板库”里面存了朴素版、堆优化版、路径记录版、计数版、次短路版、分层图版。每次比赛前花十分钟把模板过一遍确认没有手误再进考场。真正考试时核心精力留给建模而不是去回忆板子。这样既稳又快也减少低级错误。