最短路+路径计数+点权：Dijkstra状态扩展实战解析

做图论算法的人十个里有八个第一次写出能跑通的迪杰斯特拉Dijkstra剩下两个里至少有一个会卡在“最短路径条数”和“最大点权和”这种附加条件上。某OJ平台的1003号题就是这样一道经典题张无向带权图每个城市挂着救援队人数给起点和终点要求输出最短路径的条数以及所有最短路径中能集结的最大救援队人数。多数人学Dijkstra时只背了模板真遇到这种“最短路计数点权”三合一的题状态怎么维护、相等长度怎么处理、要不要重新入队很容易翻车。这篇就把整道题从题意到代码一层层拆开适合刚学完Dijkstra想进阶的读者也适合备考、刷题时被这类变体卡住的人。1. 先把需求拆明白这题到底在问什么1.1 题目场景与输入输出题面是这样的有N个城市编号从0到N-1M条无向道路给定起点C1和终点C2。每个城市有一支救援队人数用一个数组给出。每条道路有长度也就是边权。要求从C1出发到C2找出一条或几条“总长度最短”的路径输出两样东西最短路径一共有多少条以及这些路径里能带上的救援队人数最多是多少。输入格式很容易记第一行N M C1 C2 第二行N个整数表示每个城市的救援队人数 接下来M行u v w表示城市u和城市v之间有一条长度为w的无向路输出一行两个整数最短路径条数、最大救援队人数。我常用一个小样例三座城市就能把核心逻辑测出来3 3 0 2 1 2 1 0 1 1 0 2 2 1 2 1城市0有1队、城市1有2队、城市2有1队。从0到2有两条最短路径0→1→2总长2队伍数是12140→2总长也是2队伍数是112。所以输出应该是2 4这个例子够小手动就能验算后面整个过程我都会拿它走一遍。1.2 关键词拆解其实考的是状态设计题目里藏着三个关键词无向带权图、点权、路径条数。无向带权图输入的道路是无向边存图时候要正反各存一次。点权城市救援队人数属于“点权”标准Dijkstra只管边权这题要求把所有经过城市的点权累加起来比较。路径条数终点可能有多条长度相同的最短路径数量要统计出来。换句话说问题从“求出最短距离是多少”变成了“把所有最短路径都找出来并比较附带属性”。标准Dijkstra维护一个dist数组就够了而这里一个dist数组根本装不下这些信息。2. Dijkstra在解决什么这一题改在哪里2.1 从朴素贪心到堆优化Dijkstra的核心思想可以这样理解把起点当成第一个“已知点”每次从所有“还没确定最短距离”的点里挑出当前距离最小的那个把它标记为确定然后从它出发去更新相邻点。这个过程有点像消息扩散每一轮离源头更近一圈。为什么每次挑最小的那个就是最终答案因为所有边权非负一个点的距离若已经是最小值就不可能再被另一个更长的路径更新出更小的值。一旦从优先队列里弹出来它的dist就是最终值之后不会再变。朴素实现每轮要扫一遍找最小值复杂度O(N²)。堆优化的思路是用优先队列维护“候选节点”自动把最小距离的节点弹出来复杂度降到O(M log N)。现在的题目基本默认要堆优化版本虽然本题N很小用朴素版也能过但既然要学直接学堆优化版更划算。2.2 标准Dijkstra为什么应付不了这道题标准模板里每个节点只有一个状态dist[u]。走一遍之后只知道从起点到终点最短是多少厘米完全不知道有多少种走法能达到这个距离也不知道哪条路径带的救援队最多。这就是本题和模板题本质的区别不再是单一状态的更新而是三个状态打包在一起更新。打个比方标准Dijkstra像快递员找最短路线只关心路程本题像在一个城市群里赶去救人既要最快到达又要知道有多少条同样快的路还要选一条路上能集齐最多人手。条件一变原来的“最短路模板”就不够用了。2.3 用邻接表还是邻接矩阵看到N不超过500有人会用邻接矩阵500×500完全放得下。但邻接表更通用以后遇到N10⁵级别的题也能直接套。我建议直接用邻接表存vectorvector 无向边存储两次。用邻接表还有一个好处重边不用特殊处理松弛时会自然比较并保留最优。邻接矩阵遇到重边反而要自己取min多一道工序。3. 核心状态设计dist、cnt、team的更新规则3.1 三个数组的含义与初始化这题的真正考点在这里。除了常规的dist数组还要加两个数组数组含义dist[u]从起点到u的最短距离初始INFcnt[u]从起点到u的最短路径条数初始0team[u]在所有最短路径中到u时最多能带多少救援队初始0起点需要单独初始化dist[起点] 0cnt[起点] 1team[起点] 城市起点救援队人数cnt[起点]为什么是1路径计数里从起点到起点可以认为存在一条空路径方案数是1。如果这里初始化成0后面所有中转点都会跟着变成0最后终点的条数一定是0整个算法就废了。team[起点]必须包含起点的救援队因为后面每到一个新城市都只在当前总人数上加上该城市的救援队人数。3.2 主流程与两个更新分支算法框架和标准Dijkstra一致区别全在处理邻居时的分支判断。从优先队列弹出一个节点u此时u的最短距离已经确定。遍历u的所有邻接边u→v边长w用dw去和dist[v]比较分两种情况。情况一dist[v] d w说明找到了一条更短的路。这是标准的更新直接覆盖dist[v] d w; cnt[v] cnt[u]; team[v] team[u] rescue[v];注意这里是“覆盖cnt”不是“累加cnt”。因为旧的那条路已经比新路更长不再属于最短路径集合旧路径对应的方案数要全部作废。情况二dist[v] d w说明又找到一条和当前最短距离一样长的路。主指标dist[v]不变两个副指标需要合并cnt[v] cnt[u]; team[v] max(team[v], team[u] rescue[v]);cnt累加因为多个来源的方案都要计数team取max因为要求所有最短路径里最大的救援队人数不是平均值也不是累加值。这一步是题目区分度最高的地方。这里有一个关键问题dist[v]没变要不要把v重新加入优先队列我的答案是不需要。原因后面详细讲。3.3 为什么相等分支不需要重新入队这是最容易让人犯嘀咕的一点。直觉上team[v]变大了后面所有经过v的路径都应该用这个更大的team去更新不重新入队不就把信息丢了吗其实不会。因为所有能更新到v的最短路径它们的倒数第二个点u都满足dist[u] dist[v] - w。由于边权w是正数dist[u]一定严格小于dist[v]。这意味着什么意味着所有这样的u都会在v被弹出之前先被弹出、先被处理。当v从优先队列弹出来的时候所有能到v的最短路径贡献都已经汇总完毕cnt[v]和team[v]是完整的最终值。等长路径再多也不会出现“v已经弹出之后又冒出来一条等长路径”的情况。所以相等分支只要原地更新cnt[v]和team[v]就行不需要再往堆里塞一个相同dist的节点。硬塞进去虽然不会让答案错但会造成无意义的入队和出队还可能触发重复处理的麻烦。3.4 关于过期出队和visited标记堆优化带一个老坑同一个节点可能因为dist被更新在堆里存在多个不同距离的旧条目。比如一开始通过某条路得到dist10入队后来发现更短的路径dist8又入队一个(8, v)。堆里现在有两个条目。如果弹出(10, v)时不做判断就会用过期数据去更新邻居结果全乱。我处理这个问题的标准做法是出队后先做两层判断if (d dist[u]) continue; // 过期条目跳过 if (vis[u]) continue; // 已经确定过跳过 vis[u] true;只靠vis不靠谱因为旧的(10, v)可能在(8, v)之前弹出此时vis[v]还是false就会把10当成有效值处理。只靠d dist[u]过滤也不够如果两个相同dist的条目都入队虽然我们推荐的写法不会发生无法防止重复处理。两个条件一起写最稳妥。在相等分支里我还习惯加一句防御性判断if (vis[v]) continue。理论上v还没确定这个分支才会触发但加上这行能让代码在面对自环、零边权之类的意外输入时不至于把计数撑爆。3.5 状态转移总表把核心逻辑整理成一个总表写代码前对着看一遍可以少踩很多坑情形dist[v]cnt[v]team[v]是否需要入队新更短路径覆盖为dw覆盖为cnt[u]覆盖为team[u]rescue[v]需要等长新路径保持不变累加cnt[u]取max不需要4. 完整代码与一次手动模拟4.1 完整C代码下面这段代码可以直接复制编译运行注释写的是个人习惯里最不容易错的方式。#include bits/stdc.h using namespace std; const int INF 0x3f3f3f3f; struct Edge { int to, w; }; int main() { int n, m, s, t; cin n m s t; vectorint rescue(n); for (int i 0; i n; i) cin rescue[i]; vectorvectorEdge g(n); for (int i 0; i m; i) { int u, v, w; cin u v w; g[u].push_back({v, w}); g[v].push_back({u, w}); // 无向边存两次 } vectorint dist(n, INF); vectorint cnt(n, 0); vectorint team(n, 0); vectorbool vis(n, false); using P pairint, int; // 节点编号, 距离? 顺序别搞反 // 这里我统一用 pair距离, 节点编号优先队列默认比较第一元素 priority_queueP, vectorP, greaterP pq; dist[s] 0; cnt[s] 1; // 起点到起点视为一种路径 team[s] rescue[s]; // 起着点也算上车 pq.push({0, s}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (d dist[u]) continue; // 过期记录距离已经不是当前最优 if (vis[u]) continue; // 这个点的最短距离已经确定 vis[u] true; for (const auto e : g[u]) { int v e.to; int w e.w; if (v u) continue; // 自环直接跳过 if (dist[v] d w) { dist[v] d w; cnt[v] cnt[u]; team[v] team[u] rescue[v]; pq.push({dist[v], v}); } else if (dist[v] d w) { if (vis[v]) continue; // 防御性判断理论不触发 cnt[v] cnt[u]; team[v] max(team[v], team[u] rescue[v]); } } } cout cnt[t] team[t] endl; return 0; }注意优先队列里pair的第一元素必须是距离第二元素才是节点编号。如果顺序写成pairint,int但push的是{u, dist[u]}栈顶的“最小值”就按编号排序了A全部乱套。4.2 用三城市样例手动跑一遍把前面那个1 2 4的小样例拿过来一步步看状态变化。输入数据3 3 0 2 1 2 1 0 1 1 0 2 2 1 2 1初始状态dist [0, INF, INF] cnt [1, 0, 0] team [1, 0, 0] 队列: (0, 0)弹出(0, 0)处理城市0的两个邻居到城市1dist[1] INF更新为1cnt[1] 1team[1] 1 2 3入队(1, 1)。到城市2dist[2] INF更新为2cnt[2] 1team[2] 1 1 2入队(2, 2)。当前状态dist [0, 1, 2] cnt [1, 1, 1] team [1, 3, 2] 队列: (1, 1), (2, 2)弹出(1, 1)处理城市1的邻居回到城市0dist[0]0112 0不更新。到城市2边长1dw112恰好等于dist[2]进入相等分支。cnt[2]累加cnt[1]变成112team[2]取maxmax(2, team[1]rescue[2]) max(2, 31) 4。当前状态dist [0, 1, 2] cnt [1, 1, 2] team [1, 3, 4] 队列: (2, 2)弹出(2, 2)到城市0、城市1的距离都不满足更新条件结束。输出cnt[2]2team[2]4。这样就得出了正确答案2 4。手动模拟一遍的好处是能直观看到相等分支到底做了什么dist没变但cnt从1变成2team从2变成4。4.3 Java和Python实现的关键差异Java的优先队列默认是小根堆但比较器要自己写。最简洁的做法PriorityQueueint[] pq new PriorityQueue(Comparator.comparingInt(a - a[0]));如果不想写比较器也可以存一个自定义类Node实现Comparable接口按dist排序。其余逻辑和C完全一致注意Java没有结构体解构取队首是pq.poll()返回数组或对象。Python直接用heapq最省事import heapq pq [(0, s)] while pq: d, u heapq.heappop(pq) if d dist[u]: continue ...三份代码逻辑完全一样只要理解状态转移规则迁移到任何语言都很顺畅。5. 我踩过的坑常见问题与排查清单5.1 计数翻倍重复累加的典型场景这题最常见的错误就是cnt翻倍明明答案是2程序输出4。大多数情况下是因为没有过滤过期出队导致同一个节点被处理了多次每次处理都把cnt累加一遍。另一类情况是相等分支里一时手滑写了cnt[v] cnt[u]覆盖这时答案不是偏大而是偏小或者把相等分支也入队了再配合没有vis判断重复累加。自查顺序出队后有没有判断d dist[u]没有的话过期条目会污染数据。出队后有没有判断vis[u]没有的话相同dist的重复条目可能处理两次。相等分支里是还是必须是。新更短路径分支里是还是必须覆盖cnt不是累加。5.2 终点的救援队忘了加team[v] team[u] rescue[v]这一步每次到达新城市都要把该城市的救援队人数加上。有人会在最后输出前单独给team[t]再加一次救援队结果等于把终点人数算了两次答案偏大。避免方法很简单起点初始化时把起点救援队算进去每走一步到新城市就把新城市加进去终点自然包含在内不要额外处理。5.3 INF选错导致溢出如果用了INT_MAX作为INF一旦dist[u] INT_MAXdist[u] w会溢出成负数后续判断全部混乱cnt、team也会跟着变成乱七八糟的负值。建议用0x3f3f3f3f这个值大约是10亿级别两个这样的值相加大约是21亿不会超过int上限而且memset可以直接按字节填充非常方便。5.4 重边、自环、无向边只存一半无向边只存一次如果读入u v w只往g[u]里push了没有往g[v]里push从v出发的所有路径都断掉。自环v u时如果边权为正且等长分支触发会出现cnt[u] cnt[u]计数翻倍。代码里加一行if (v u) continue就解决了。重边邻接表本身不需要特殊处理等长或更短的路都走一遍更新逻辑取其最优即可只有用邻接矩阵时才需要存边权最小值。5.5 起点就是终点题目有时会考察这个边界。如果起点等于终点最短路径条数显然是1救援队人数等于起点城市人数。代码里初始化cnt[s]1、team[s]rescue[s]不进入循环直接输出结果正好正确。写自测用例时一定要加这一条很多人用普通用例能过一遇边界就丢分。6. 问题速查表现象可能原因修复方向输出的条数比答案大重复处理节点出队时过滤d dist[u]或加vis输出的条数比答案小相等分支用了覆盖改成累加team结果偏小相等分支没有取max改成max(旧值, 新值)team结果偏大终点救援队多算一次只在新到达城市时累加dist和team出现负值INF用了INT_MAX导致溢出换成0x3f3f3f3f中途断路部分点不可达无向边只存了一次保证u→v和v→u都入表自环导致计数翻倍没有跳过vu加continue判断起点终点相同但答案错误cnt起点初始化不对cnt[s]设1team[s]设起点人数7. 从1003到更多Dijkstra状态扩展的思路7.1 一题多解的其他路线求最短路径条数除了Dijkstra过程中直接维护cnt还有一种做法是先跑一遍Dijkstra求出每个点的最短距离dist然后所有满足dist[v] dist[u] w的边共同构成一张DAG在这张DAG上做拓扑序DP或记忆化搜索来统计路径条数和最大点权和。这种“先求dist再在DAG上DP”的思路也很常见尤其适合需要输出具体路径、要枚举所有最短路径的场景。但就本题而言直接在Dijkstra里维护cnt和team更简洁一次遍历搞定不需要再建图。7.2 状态维度还能怎么加“最短路计数最大值”只是一个组合。同样的套路可以扩展到最短路条数 经过节点数最多最短路条数 花费时间最短最短路条数 最少换乘次数两条最短路之间的重叠长度核心思想是固定的主指标距离不变时副指标做最优合并主指标更优时副指标直接跟随新路径重置。只要更新规则一致加多少维度都只是增加数组长度难度并不会变。7.3 从统计数量到输出具体路径如果要输出一条最短路径本身可以在更新dist时记录pre[v] u。但题目要求的是所有最短路径中的最大点权和需要的是全部候选路径的信息不能只存一个pre。更通用的做法是在等长分支里把(u, v)保存下来作为“可行前驱”最后从终点DFS回溯收集所有最短路径。注意要用vis标记或set去重否则同一条边可能被多条路径重复走输出会爆。7.4 如果边权有负值Dijkstra的贪心建立在边权非负的基础上一旦出现负权边已经确定最短距离的节点也可能被后续更小的负权边更新弹出一次的结论就失效了。这时要改用SPFA或Bellman-Ford。如果图中存在负权环“最短路径条数”这个概念本身会变成无穷大题目一般会保证数据不出现这种情况但理解边界很重要。7.5 次短路的延伸如果题目进一步要求“第二短路径长度”那就是次短路问题。每个节点不只维护最小dist还要维护次小dist更新分支从两种变成三种更新最小、更新次小、等长再更新等。思路和本题一脉相承都是在标准Dijkstra的状态集合上做扩展。把1003吃透之后再碰次短路、多条件最短路会顺畅得多。最后分享一点个人做题心得。每次写这类“最短路附加状态”的题我都会先停在代码前面想三件事起点三个状态的初始值是什么每个分支里副指标是覆盖还是合并相等分支要不要重新入队想清楚这三件事再落笔基本不会错。写完之后一定会造一组“两条路等长但队伍数不同”的用例用笔在纸上把每一步dist、cnt、team都写一遍确认没问题再提交。这套习惯帮我避开了绝大多数Dijkstra变体的坑也适合你拿去做自测参考。