得从CSP-S考场上一个很现实的问题说起同样是求最短路为什么有人能用Dijkstra十分钟AC有人却卡在SPFA的TLE里出不来还有人连建图都写不对。这篇东西就是把我自己备考和带选手过程中关于Dijkstra算法最核心的那套东西全拆开揉碎讲清楚。从原理本质到堆优化写法从链式前向星建图到真题实战再到那些课本上从来不写的坑一次说透。1. 为什么是Dijkstra它在CSP-S里的地位与边界1.1 最短路题型的出场率翻翻近几年CSP-S的真题和高质量模拟题图论永远是压轴题和高频题的重灾区而最短路又是图论里最基础、最实用的模型。说句不夸张的话Dijkstra在CSP-S提高组里就是“保分题”的代名词——它经常作为一道大题的第一步、一个子任务、或者一个关键前置算法出现。你如果能在考场上快速、准确地把Dijkstra写出来至少能锁定几十分的基础分。很多选手一开始学最短路先学Floyd因为代码短好背再学SPFA感觉写法也简单。可一到真正的CSP-S考场上Floyd的O(n³)复杂度在1000个点以上就直接绝望SPFA在最坏情况下能被出题人构造的数据卡到O(nm)直接TLE没商量。这个时候Dijkstra才是那个“稳”的算法。尤其是加了堆优化之后复杂度是O((nm)log n)在n和m都在10^5级别的时候依然能跑得很舒服。1.2 Dijkstra与其他最短路算法的分界线有不少初学者会问我到底什么时候用Dijkstra什么时候用SPFA或者Bellman-Ford这个问题一定要在脑子里形成固定的条件反射。Dijkstra用的是贪心思想每次从还没确定最短路的点里挑一个“当前距离最小”的点把它当作已经确定最短路的点然后用它去松弛其他点。这个贪心策略成立的前提是所有边的边权必须非负。只要边权非负那么已经确定最短路的点就不可能再被其他点通过绕路的方式更新出更小的距离——因为绕路必然会增加距离。一旦图里出现负权边这个逻辑就崩了Dijkstra的结果就可能错。所以我的建议是题目里没有负权边闭眼用Dijkstra题目有负权边但没负环用Bellman-Ford或者SPFA题目有负环一般不是求最短路而是判负环相关的题目。在CSP-S考场上绝大多数最短路场景都是非负权边Dijkstra就是你最该信任的算法。2. Dijkstra核心原理为什么能贪心边界在哪2.1 一个生活化的直观理解想象你在一张地图上要从北京去上海每条路都是单行道且没有回头路实际比这复杂但先这么理解。Dijkstra的做法是你先看从北京出发能直接到达的所有城市挑一个距离最近的城市比如济南那么北京到济南的最短路径就确定了。为什么因为所有路的长度都是正数你不可能通过“北京到某某地方再到济南”绕出一条比“直接到济南”更短的路绕路会让总距离变长。确定了济南之后再用济南去更新“北京经济南到其他城市”的距离然后在所有还没确定的城市里再挑一个当前距离最小的继续重复。这个“从当前已知最短距离的点中选最小的”动作就是贪心的体现。它每次都能锁定一个真正的最短路径终点而且一旦锁定就不再回头。这就是Dijkstra高效的根本原因。2.2 为什么必须是非负边权理解了这个贪心逻辑你就明白为什么负权边会让Dijkstra失效如果存在负权边那么一个当前距离较大的点可能通过一条负权边“绕”到一个当前距离较小的点让那个已经被锁定的点的最短距离变得更小。锁定就错了。举个例子有三条边s到a权值为5s到b权值为10a到b权值为-20。Dijkstra先锁定s到a距离为5然后用a松弛s到b得到-15接着锁定b距离为-15。这个结果表面看没问题但只要再有一条从b到a的负权边a就应该更小可a已经被锁定了。所以负权边一出现Dijkstra就必须休息。在CSP-S里题目描述通常会明确说“边权为正整数”或“非负”这时候你完全可以放心大胆地用Dijkstra。如果题目没有明说但你能从题意推断出不会出现负权边比如求最少时间、最少费用而这些本身就是非负的那依然可以用。我自己复盘真题的时候发现CSP-S里不给负权边的情况占了绝大多数。2.3 朴素版完整实现与复杂度分析先看最原始的写法。我们用dist数组记录源点到每个点的最短距离用vis数组记录点是否已经确定了最短距离。每次从未确定的点中选一个dist最小的标记为确定然后遍历这个点能到达的所有点做松弛操作。#include bits/stdc.h using namespace std; const int INF 0x3f3f3f3f; const int MAXN 1005; int g[MAXN][MAXN]; // 邻接矩阵存图 int dist[MAXN]; // 最短距离 bool vis[MAXN]; // 是否已确定 int n, m, s; void dijkstra(int s) { memset(dist, 0x3f, sizeof(dist)); memset(vis, false, sizeof(vis)); dist[s] 0; for (int i 1; i n; i) { int u -1, 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) { if (dist[u] g[u][v] dist[v]) { 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) { if (dist[i] INF) cout INF ; else cout dist[i] ; } return 0; }这种写法找最小点的过程是O(n)的整体复杂度O(n²)对点数不超过1000或2000的场合够用。但它的问题很明显每一次找最小值都扫描全部点图一大就扛不住了。而且邻接矩阵存图要求n不能太大n100000的时候矩阵根本开不下。所以CSP-S里真正的重头戏是堆优化。3. 必会的优化堆优化的三个关键细节3.1 复杂度对比优化到底省在哪里朴素版的时间浪费在“找最小dist值”上每次都要O(n)地扫一遍。堆优化的思路就是用一个优先队列小根堆来维护“当前所有未确定点的dist值”每次取堆顶就是当前最小值时间复杂度从O(n)降到O(log n)。整体的复杂度变成了O((nm)log n)。这个优化增量在数据规模一大就体现得很明显。比如n10^5m10^5的场景朴素版要做10^10次左右的扫描判断直接超时而堆优化版本大约只执行10^5次入队出队每次log级别非常轻松。CSP-S提高组的图论大题很多时候n和m都在这个量级所以堆优化你是绕不开的。3.2 优先队列的写法与代码模板堆优化的写法现在已经比较固定了我直接给出我平时在考场上一字不差默写的模板。#include bits/stdc.h using namespace std; const int INF 0x3f3f3f3f; const int MAXN 100005; struct Edge { int to, w, next; // 终点、边权、下一条边的编号 } edges[MAXN * 2]; // 无向图开双倍空间 int head[MAXN], edgeCnt 0; int dist[MAXN]; bool vis[MAXN]; int n, m, s; void addEdge(int u, int v, int w) { edgeCnt; edges[edgeCnt].to v; edges[edgeCnt].w w; edges[edgeCnt].next head[u]; head[u] edgeCnt; } void dijkstra(int s) { memset(dist, 0x3f, sizeof(dist)); memset(vis, false, sizeof(vis)); dist[s] 0; // 小根堆pair距离, 点编号 priority_queuepairint, int, vectorpairint, int, greaterpairint, int pq; pq.push({0, s}); while (!pq.empty()) { int u pq.top().second; int d pq.top().first; pq.pop(); if (vis[u]) continue; vis[u] true; for (int e head[u]; e ! 0; e edges[e].next) { int v edges[e].to; int w edges[e].w; if (dist[u] w dist[v]) { dist[v] dist[u] w; pq.push({dist[v], v}); } } } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n m s; 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] ; } return 0; }注意几个地方优先队列想用小根堆要用greaterpairint,int别写成默认的less那是大根堆pair比较时先比第一维距离再比第二维编号所以距离优先没问题入队时不需要刻意判断vis我在出队的时候判一次就够了这是很多教材里写法不一样的地方后面会细说。3.3 vis数组要不要关于“出队判重”的争论这个问题我见过太多人纠结了。有的写法是入队的时候判断vis有的写法是出队的时候判断还有的干脆不用vis数组。我自己在考场上用的是“出队判重”也就是代码里那样从堆顶拿出元素后先看这个点是不是已经被确定过最短距离如果是就直接continue。理由很简单同一个点可能会被压入堆多次。比如点v先被点u1更新dist[v]10入队后来又被点u2更新dist[v]8再次入队。堆里同时存在(8, v)和(10, v)两条记录。当(8, v)出队并确定为最终答案后(10, v)就是一条过期的记录如果不判vis就会把v再处理一遍浪费一次遍历甚至可能导致某些包含负权边的错误图虽然Dijkstra本来就不适用于负权边中出现逻辑问题。所以你看到“出队时if(vis[u]) continue;”这个判断不要觉得它多余它是堆优化Dijkstra的标准写法能有效避免重复处理同一个点。4. 链式前向星考场上的建图标准解4.1 为什么不推荐用vector存图不少同学学了vector存图之后就一直用vectorpairint,int g[MAXN]来存。代码写起来确实简洁遍历也方便。但到了CSP-S的高压环境里我对vector有几个担心。第一vector扩容的时候会动态分配内存中间偶尔会有一点性能抖动。虽然有reserve可以缓解但万一忘了写碰上大数据量可能连续扩容好几次这段时间就浪费了。第二vector本身就占内存每个元素还有额外的元数据在n和m都到10^5甚至10^6的时候内存可能比链式前向星多不少。第三最关键的一点——在很多OI赛场环境里链式前向星是最底层的、最不容易被卡的方式也最能锻炼你手写数据结构的稳定性。链式前向星本质上是用数组模拟链表。head[u]存储从u出发的第一条边的编号然后每条边通过next指针指向下一条以u为起点的边。这样所有起点相同的边就串成了一条链遍历的时候沿着next不停走就行。4.2 链式前向星的模板和建图过程我直接给出一个标准模板。建图之前要先初始化head数组为0edgeCnt为0。addEdge的时候新边的编号每次递增然后让新边的next指向当前head[u]再把head[u]更新为新边的编号。这个“新增的边永远插在链表头部”的过程就是链式前向星的精髓。void addEdge(int u, int v, int w) { edgeCnt; edges[edgeCnt].to v; edges[edgeCnt].w w; edges[edgeCnt].next head[u]; // 新边next指向旧的链表头 head[u] edgeCnt; // 更新链表头为新边 }遍历从u出发的所有边for (int e head[u]; e ! 0; e edges[e].next) { int v edges[e].to; int w edges[e].w; // 处理 v 和 w }注意一个非常容易踩的坑如果你写的是无向图每条边需要addEdge两次一次u到v一次v到u所以edgeCnt会加到2m。那么edges数组就要开2倍MAXM或者直接开MAXN*2。我见过不少选手就是因为只开了MAXM结果无向图当有向图的空间用数组越界在考场上莫名其妙地RE。开数组的时候宁多勿缺。5. 真题视角一道典型CSP-S风格题目的完整解法5.1 题目描述模拟CSP-S风格题目这道题综合了“抽象最短路模型”和“分层图”思想出题风格非常CSP-S。题目大意如下n个城市之间有一些高速公路每条路有通行时间和费用。你从城市1出发目标到城市n要求在总费用不超过K元的前提下使得通行总时间最短。求这个最短时间。n ≤ 10000m ≤ 50000K ≤ 10边权均为正整数。这道题如果直接把它当成求最短路来做你会发现“费用限制”这个条件没法直接在普通的图上处理。怎么办呢分层图。5.2 分析过程与模型建立把“费用”这一维度加到状态里。设dist[i][k]表示从1号城市出发到达城市i且总费用恰好不超过k时的最短时间。建图的时候把原图的边复制K1层层k表示当前已经花费了k元费用。从城市u层k到城市v层kw如果kw K那么这条边就是原图边权的通行时间如果你在同层内部做转移那就是表示费用不变的情况下继续走。实际上更直接的做法是把每个“城市编号当前费用”的组合看成一个节点原图的边u-v权值为w费用为cost在分层图里就是从(u, k)到(v, kcost)连一条边权为时间time的边。这样我们就在一个K1层的扩展图上求从(1, 0)到(n, 任意不超K的层)的最短路。因为所有边权都是正数这是经典的Dijkstra适用场景。用堆优化的Dijkstra跑一遍这个分层图即可。5.3 完整代码实现#include bits/stdc.h using namespace std; const int INF 0x3f3f3f3f; const int MAXN 10005; const int MAXK 15; struct Edge { int to, time, cost, next; } edges[MAXN * 20]; int head[MAXN], edgeCnt 0; int dist[MAXN][MAXK]; // dist[点][费用] bool vis[MAXN][MAXK]; int n, m, K, s, t; void addEdge(int u, int v, int time, int cost) { edgeCnt; edges[edgeCnt].to v; edges[edgeCnt].time time; edges[edgeCnt].cost cost; edges[edgeCnt].next head[u]; head[u] edgeCnt; } void dijkstra() { memset(dist, 0x3f, sizeof(dist)); memset(vis, false, sizeof(vis)); // 优先队列存三元组时间、节点、费用 priority_queuetupleint, int, int, vectortupleint, int, int, greatertupleint, int, int pq; dist[s][0] 0; pq.push({0, s, 0}); while (!pq.empty()) { auto [curTime, u, k] pq.top(); pq.pop(); if (vis[u][k]) continue; vis[u][k] true; for (int e head[u]; e ! 0; e edges[e].next) { int v edges[e].to; int newTime curTime edges[e].time; int newCost k edges[e].cost; if (newCost K newTime dist[v][newCost]) { dist[v][newCost] newTime; pq.push({newTime, v, newCost}); } } } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n m K; s 1; t n; for (int i 0; i m; i) { int u, v, time, cost; cin u v time cost; addEdge(u, v, time, cost); addEdge(v, u, time, cost); } dijkstra(); int ans INF; for (int k 0; k K; k) { ans min(ans, dist[t][k]); } if (ans INF) cout -1 endl; else cout ans endl; return 0; }这段代码是完整的C17写法用到了结构化绑定auto [curTime, u, k]来读优先队列里的tuple代码更清晰。如果你们的评测机还不支持C17那就用三个变量手写一个结构体来存。5.4 易错点复盘这个题我复现过好几次大家最容易出错的地方第一是dist[t][k]只看了某一层的答案忘了统计所有层的min第二是优先级队列里忘记把费用维度也作为状态之一去判vis导致同一节点不同费用状态的重复计算第三是题目给的“恰好费用为K”还是“最多费用为K”要看清楚有的版本要精确限制到某几层有的则要算所有层的min。分层图这个东西思想上其实就是把额外限制转化成一维状态然后在这个更高维的图上跑最短路。每次遇到一个“限制条件”的时候先想想能不能把它压进状态里这就是CSP-S图论大题常用的一招。6. 实战避坑那些年踩过的Dijkstra大坑6.1 大坑清单第一个坑初始化用的是0x3f而不是0x7fffffff。0x3f3f3f3f是一个约等于10^9的数两个0x3f3f3f3f相加不会溢出int大约是2.1×10^9还在int范围内但0x7fffffff加上一个正数直接就溢出变负数了。所以只要涉及dist[u]w的运算INF必须用0x3f3f3f3f。这个坑我在初学的时候踩过后来就再也不碰0x7fffffff了。第二个坑有向图和无向图搞混。写最短路的时候题目说“道路”那就是无向图addEdge要加两次。题目说“航线”通常是有向图只加一次。如果加错了最短路会少算方向最后答案错得不着边际还很难排查。第三个坑读入的时候有重边。有的题目里u到v可能有多个权值如果不做处理直接加进图里Dijkstra还能跑但多了一条大边性能可能略受影响其实Dijkstra本身不依赖重边处理也能跑对因为dist[v]会取到那个更小的。但千万不要把重边的多条边都当成独立的边去松弛那样没意义但也不会错只是浪费一点时间。真正的问题是如果题目说“u到v没有边”但你存图的时候忘了初始化INF那松弛的时候要么用了0要么用了垃圾值就会出错。第四个坑节点编号从0开始还是从1开始。CSP-S大多数题目习惯从1到n但有些题会从0到n-1。如果用习惯的1到n去写然后数组开了n下标n越界直接RE。我的习惯是读题的时候第一件事确认编号范围然后数组多开5个甚至10个。6.2 考场上的调试策略Dijkstra在考场上如果写错了怎么快速定位我的经验分三路排查。先拿样例跑如果样例都不对优先检查建图。手算一个小数据比如只有3个点2条边自己手动模拟一遍dist的变化看代码跑出来的中间dist是不是符合预期。其次检查优先队列的排序方向很多人写greater结果用成了大根堆导致每次取的点是最大的答案完全乱掉。第三检查vis数组的位置。如果是出队判重那入队的时候不要判vis如果入队的时候判了vis那一个点只会入队一次出队的时候其实不需要再判但为了保险很多选手两种都写上去。其实两种写法都能AC关键是别写混了。最后我强烈建议在本地写一个随机数据对拍程序。用暴力Floyd或者朴素Dijkstra当“标程”随机生成小规模数据把堆优化Dijkstra的结果和标程对拍。只要数据范围小暴力一定正确跑几百次对拍基本能确认自己的Dijkstra实现是没问题的。6.3 变式与进阶方向Dijkstra本身虽然算法固定但在题目里有很多变形。比如求次短路可以在dist数组之外再维护一个second数组记录每个点的次短路然后在Dijkstra的松弛过程中同时更新最短路和次短路比如求最短路径数量可以在松弛时额外记录一个cnt数组当dist更新时cnt[v]cnt[u]当dist相等时cnt[v]cnt[u]再比如分层图最短路就像上面第5节写的那样。在CSP-S的备赛过程中我总结出一个很务实的观点Dijkstra不只是一个算法模板它背后那种“贪心选最短”“状态扩展”“松弛更新”的思维方式是会反复出现在拓扑排序、最小生成树、动态规划等多种题型里的。你把Dijkstra练熟了等于同时练通了好几个算法。7. 从备赛到考场Dijkstra的应试心法7.1 默写模板的底线要求到了CSP-S这个阶段堆优化Dijkstra要能做到闭着眼睛默写而且每次都一次通过编译。我说的“默写”不是背代码而是当你看到题目的那一瞬间脑子里就自动过一遍建图方式、节点下标、优先队列类型、dist初始化、vis判重位置、遍历边的写法甚至数组大小要开多大都能立刻反应出来。我建议所有备赛的选手都做这样一件事把堆优化Dijkstra模板、链式前向星模板、邻接表模板、朴素Dijkstra模板这几个模板各自写五遍以上直到写得滚瓜烂熟。写的过程中强迫自己思考每一行代码为什么存在而不是机械抄写。这样上考场遇到最短路题的时候你根本不需要在写模板上花时间可以把全部精力放到读懂题意、设计状态上面。7.2 读题和建模比模板更重要模板熟练了只是第一步。真正决定你能不能AC一道题是你的建模能力。同样的“最短路”外壳套上“费用限制”“时间限制”“必须经过某些点”“每条边只能走一次”等条件之后得出来的模型千差万别。所以每次做题我都提醒自己先看数据范围判断n和m能不能用Dijkstra再看边权是否为非负最后才是套模板。我和不少选手交流下来发现一个通病太急着上代码图一画个大概就开始写写到一半发现状态设计不对又停下来改。这是竞赛大忌。最好是先在草稿纸上把状态定义、转移方式、边界条件写清楚确定所有细节之后再上手写代码。Dijkstra这类题往往建模比实现重要得多。7.3 心态与平时训练建议考场上最怕的不是算法不会而是算法会了但写崩了。Dijkstra写崩最常见的情况无非就是数组开小、vis写错、优先队列类型写错这几种。平时训练的时候每次提交后如果WA了别急着看题解先用样例和小数据对拍自己定位问题把“排查问题”也当成训练的一部分。这样一来到了真正比赛的时候就算一时出错也能快速找回状态。平时刷题的时候建议多练几个经典的Dijkstra变式题次短路、分层图、路径计数、带状态的最短路。每练一道就在脑子里把Dijkstra的“状态图”想象一遍时间长了你对最短路的感觉就会从“会写模板”变成“能用模型解决一切最短路问题”。我在带训练的时候经常跟选手说一句话Dijkstra不是背模板就能拿分的它是一面镜子能照出你对状态设计和图论建模的理解有多深。这句话放在CSP-S的备考里尤其应验。
