题源洛谷 P15803 [GESP202603 七级] 物流网络题目链接1. 背景在算法竞赛中带特殊优惠条件的最短路问题一直是一类高频考点。这类题目往往在经典最短路模型上附加一条“减免规则”比如“路径上最大边权免费”“最多跳过一条边”等。乍看之下我们可以在状态中记录优惠信息直接用分层图或扩维BFS解决但当减免规则与边的某种“属性”如景观评分、优先级相关时状态维度可能膨胀导致时间或空间无法承受。本题正是这样一个典型例子每条边既有运输费用又有景观评分优惠规则是“免除路径上景观评分最高的那条边的费用”。如果直接把“最高评分边”作为状态你根本不知道当前路径上哪条边评分最高除非记录整个路径的评分信息——这显然不现实。本题在GESP七级中定位为“普及/提高”难度核心考察的是将复杂条件转化为标准最短路模型的能力以及枚举优化的工程技巧。本文将通过这道题带你从“暴力枚举每条边免费”出发逐步优化到“倒序枚举 动态邻接表”的优雅解法并顺带对比一个常见的84分BFS错误思路帮你避开那些“看起来对但跑得慢/错得悄无声息”的坑。2. 核心思想章节2.1 问题转化谁才是“最高评分”的那条边直觉上一条路径的费用 路径上所有边费用之和 − 路径上最大评分边的费用。我们不妨换个视角如果我知道路径上哪条边被免除了那么问题就变成一个普通的最短路——只需把那条边的费用视为0跑一遍Dijkstra即可。关键来了我们并不知道最优路径到底免的是哪条边。但我们可以“猜”——枚举每一条边假设它就是最优路径上被免除的那条然后求一次最短路最后取所有结果的最小值。因为最优路径上一定存在某条边作为最大评分边所以枚举所有边一定不会漏解。这就是最朴素的“枚举免除边 跑最短路”框架。2.2 朴素枚举的致命弱点如果直接枚举m mm条边每次对整张图跑一遍O ( ( n m ) log ⁡ n ) O((nm)\log n)O((nm)logn)的Dijkstra总复杂度是O ( m ( n m ) log ⁡ n ) O(m (nm)\log n)O(m(nm)logn)。在n , m n,mn,m达到5 × 10 3 5\times 10^35×103级别时2.5 × 10 7 2.5\times 10^72.5×107乘以对数在C中勉强可过但若数据再大一些就会超时。但本题n , m ≤ 5000 n,m \le 5000n,m≤5000这种朴素做法其实也能过5000 × ( 5000 5000 ) log ⁡ 5000 ≈ 5 × 10 8 5000\times (50005000)\log 5000 \approx 5\times 10^85000×(50005000)log5000≈5×108常数优化好勉强可行。不过题目给出的AC代码中采用了一个更巧妙的优化按评分排序后倒序枚举动态移除边。2.3 倒序枚举用“减法”代替“加法”我们注意到每次枚举时我们只关心“当前被免除的那条边是否在图中是评分最高的”。如果我们先将所有边按评分升序排序然后从评分最高的边开始往下枚举那么在枚举第i ii条边时所有评分比它高的边即i 1 ∼ m i1 \sim mi1∼m已经被移出图了剩下的边评分都不超过第i ii条。这样第i ii条边自然而然就是当前图中评分最高的边正好符合“免除最高评分边”的语义。更重要的是这种“倒序”策略让我们可以动态维护邻接表每枚举一条边跑完Dijkstra后直接从两端点的邻接表中pop_back()删掉它下一轮图中就不存在比它评分更高的边了。相比每次重新建图这种方式节省了O ( m ) O(m)O(m)的重建开销并且代码非常简洁。小结将“路径上最高评分边免单”转化为“枚举免单边”再通过排序倒序实现图的动态缩减是本题的核心降维思路。3. 算法模板章节3.1 算法到底在干什么—— 直觉解释想象你有一堆公路每条公路旁边挂着一个“评分牌”景观评分。物流公司说“你走的这条路线里评分最高的那条路我免费。”为了找到最便宜的路线你可以这样尝试先把所有路按评分从低到高排成一列。从评分最高的那条路开始假设它就是免费路然后在这张图上暂时移除所有比它评分更高的路因为那些路不可能成为免费路跑一遍最短路记下费用。接着把这条路删掉继续处理评分次高的路重复上述过程。最后在所有记下的费用中取最小值。这个过程就像一层层剥洋葱每次剥掉最外层的“最高评分”考察当前内核中的最短路。3.2 万能模板 —— 伪代码 实战代码伪代码读入 n, m 及每条边的 (u, v, w, b) 按 (b, w) 升序排序边编号 1..m 建立邻接表每条边以 (目标点, 编号) 存入两端 ans INF for i m downto 1: // 此时图中包含边 1..i边 i 的评分是当前图中最高 dist dijkstra(免除边 i) ans min(ans, dist[n]) // 从图中移除边 i 从 e[i].u 的邻接表中 pop_back 从 e[i].v 的邻接表中 pop_back 输出 ans 或 -1完整AC代码C带注释#includebits/stdc.husingnamespacestd;#defineintlonglongtypedefpairint,intPII;// (距离, 城市编号)constintN5005;structEdge{intu,v,w,b;// 端点、费用、评分}e[N];// 存储所有边编号从1开始intn,m;vectorPIIadj[N];// 邻接表每个元素为 (邻接点, 边编号)intdist[N];boolst[N];priority_queuePII,vectorPII,greaterPIIheap;intans1e18;// 排序规则评分低的在前评分相同则费用低的在前boolcmp(Edge x,Edge y){if(x.by.b)returnx.wy.w;returnx.by.b;}// Dijkstrax 为被免除费用的边编号voiddijkstra(intx){memset(st,0,sizeof(st));memset(dist,0x3f,sizeof(dist));dist[1]0;heap.push({0,1});while(!heap.empty()){auto[d,u]heap.top();heap.pop();if(st[u])continue;st[u]true;if(un){ansmin(ans,dist[n]);break;// 终点确定可提前结束}for(auto[v,id]:adj[u]){intw(idx?0:e[id].w);// 被免除边费用为0if(dwdist[v]){dist[v]dw;heap.push({dist[v],v});}}}}signedmain(){ios::sync_with_stdio(false);cin.tie(nullptr);cinnm;for(inti1;im;i){cine[i].ue[i].ve[i].we[i].b;}sort(e1,em1,cmp);// 构建邻接表注意存储的是边编号for(inti1;im;i){adj[e[i].u].push_back({e[i].v,i});adj[e[i].v].push_back({e[i].u,i});}// 倒序枚举从评分最高的边开始for(intim;i1;i--){dijkstra(i);// 移除边 i为下一轮做准备adj[e[i].u].pop_back();adj[e[i].v].pop_back();}if(ans1e18)cout-1\n;elsecoutans\n;return0;}3.3 例题实现 —— 本题完整运行流程以样例为例3 3 1 2 10 5 2 3 20 6 1 3 100 1排序后边顺序为1: (1-3, w100, b1)2: (1-2, w10, b5)3: (2-3, w20, b6)倒序枚举i3评分最高边2-3图中包含所有边Dijkstra免除边3得路径1-2(10)2-3(免费)10ans10。移除边3图中只剩边1和边2。i2边1-2免除边2得路径1-2(免费)2-3(20)20ans保持10。移除边2图中只剩边1。i1边1-3免除边1得路径1-3(免费)0ans更新为0。最终输出0。3.4 对比实现 —— 为什么那个BFS只得了84分题目附带了一个84分的BFS版本核心思想是在状态中记录当前路径的最大评分边的费用并据此计算实际支付费用。代码结构如下// 84分版本错误/超时原因分析structState{intv,w,b,bw;};// 当前点、累计费用、最大评分、最大评分边的费用queueStateq;voidbfs(){memset(dist,0x3f,sizeof(dist));q.push({1,0,0,0});while(!q.empty()){auto[u,w,b,bw]q.front();q.pop();if(w-bwdist[u])continue;dist[u]w-bw;if(un)ansmin(ans,w-bw);for(autoedge:adj[u]){if(edge.bb||(edge.bbedge.wbw)){q.push({edge.v,wedge.w,edge.b,edge.w});}else{q.push({edge.v,wedge.w,b,bw});}}}}为什么错误这个BFS实际上是按“累计费用”进行搜索的但队列的先进先出无法保证按距离递增扩展且dist[u]的定义是“到达u时的实际支付费用”但转移时依赖于路径上的最大评分边不同路径到达同一城市时最大评分边可能不同因此dist[u]并不是一个单调的最优值直接用if(w-bw dist[u]) continue;剪枝是不安全的。这会导致漏掉某些可能更优但当前支付费用稍大的路径。同时它没有利用优先队列扩展顺序混乱在稠密图中还可能超时。所以它只得了84分说明部分数据能过但存在正确性或效率问题。正确的做法一定是Dijkstra枚举因为我们将优惠条件“外挂”到枚举中每次求解的是标准最短路保证正确性。3.5 变体清单变体场景处理方法与本题的差异免除路径上费用最大的边同样枚举边按费用排序倒序评分改为费用最多免除k条边k小分层图状态多一维表示已免次数本题只免1条无需分层免除路径上第k大评分的边需要排序后二分前缀判断更复杂本题只免最大边权有负值不能Dijkstra需Bellman-Ford或SPFA本题费用为正要求输出具体路径记录前驱节点即可本题只求费用3.6 什么时候不能用图不连通Dijkstra无法到达n答案保持INF输出-1但算法仍可运行。费用为负Dijkstra失效需换用Bellman-Ford但枚举框架仍适用。免除边不唯一若有多个最大评分边题目说“只免除其中一条”我们的枚举完美覆盖因为每条边都试了一次且每次只免一条。m非常大如10 5 10^5105O ( m 2 log ⁡ n ) O(m^2\log n)O(m2logn)难以承受需考虑更优算法如二分答案最短路或用数据结构优化枚举本题范围较小所以此方法可行。4. 底层逻辑章节4.1 为什么“倒序枚举动态删边”是正确的正确性证明设最优路径为P PP其上的最大评分边为e ∗ e^*e∗评分为b ∗ b^*b∗。在按评分升序排序后所有评分高于b ∗ b^*b∗的边都不可能出现在P PP上否则最大评分就不是e ∗ e^*e∗。因此当我们倒序枚举到边e ∗ e^*e∗时图中已经删除了所有评分高于它的边而e ∗ e^*e∗本身还在。此时P PP上的所有边都存在于图中且e ∗ e^*e∗是当前图中评分最高的边因为比它高的都已删除。于是当我们在这一轮跑Dijkstra时将e ∗ e^*e∗费用视为0一定能求出包含P PP的最短路至少不会比P PP差。因此该轮的结果 ≤ 最优解。而每一轮得到的结果都是某条合法路径的费用免费边就是当前最高评分边所以最终答案 ≥ 最优解。结合两者相等。故算法正确。4.2 与经典问题“去掉一条边求最短路”的对比经典问题“给定图去掉一条边后求最短路”通常用“最短路树”或“必经边”概念但本题去边的依据不是“必须去掉某条边”而是“去掉评分最高的边”具有动态性。经典问题往往枚举每条边分别跑最短路和本题思路一致但本题借助评分排序实现了“去边”的天然顺序省去了重新建图。4.3 隐含约束边评分的传递性题目未保证评分互异若有相同评分排序后顺序任意但倒序枚举时相同评分的边会依次被移除。假设最优路径包含两个相同最大评分边那么只要枚举到其中任意一条作为免费边另一条仍正常计费路径合法。因为排序后这些边相邻无论先枚举哪一条图中都包含它们除非已移除但移除顺序是固定的可能会造成某些组合的遗漏分析若两条边评分相同当枚举第一条假设编号较大时第二条还在当枚举第二条时第一条已被移除。如果最优路径需要免除第一条而第二条也相同评分但并未免除那么免除第一条时路径是合法的结果会被记录。所以不会漏解。5. 决策表不同思路的适用场景场景方案时间复杂度空间复杂度优点缺点n,m ≤ 5000本题数据倒序枚举 DijkstraO ( m 2 log ⁡ n ) O(m^2 \log n)O(m2logn)约5 e 8 5e85e8可过O ( n m ) O(nm)O(nm)实现简洁正确性高对更大数据可能超时n,m ≤ 2000追求更稳朴素枚举每条边每次重新建图跑DijkstraO ( m 2 log ⁡ n ) O(m^2 \log n)O(m2logn)但常数较大O ( n m ) O(nm)O(nm)思路直接易调试重建图开销大只关心最大边权免费且边权范围小按边权分块用线段树维护最短路可降至O ( m log ⁡ 2 n ) O(m \log^2 n)O(mlog2n)复杂效率高实现难度大且本题不需要要求免除的边是路径最大评分但评分范围小如1~K可枚举评分阈值用二分最短路判定O ( K ⋅ ( n m ) log ⁡ n ) O(K \cdot (nm)\log n)O(K⋅(nm)logn)简单可应对更大K评分范围大时不适用允许免除任意一条边无评分限制分层图最短路O ( ( n m ) log ⁡ n ) O((nm)\log n)O((nm)logn)O ( n m ) O(nm)O(nm)最优本题规则为“最大评分”不适用6. 工程视角在实际工程中类似“减免最高费用”的逻辑并不少见比如快递运费减免快递公司推出“首重免费续重收费”但首重是按体积还是重量如果按“最大体积”免除则可抽象为本问题。网络路由中的流量工程在SDN网络中可以指定某条“最拥塞”的链路不计费以优化整体成本。游戏中的道路建造玩家在规划路线时系统允许“最高等级道路免费”从而鼓励玩家探索不同组合。供应链中的关税优惠一批货物经过多个国家其中关税最高的那个国家给予免税求最小总关税。这些场景都可以转化为“枚举被优惠的关键元素 最短路/动态规划”的模式本题的方法具有很强的迁移价值。7. 小结核心公式答案 min ⁡ e ∈ E ( Dijkstra ( G ∖ { e ′ ∣ b ( e ′ ) b ( e ) } , 免除 e ) ) \text{答案} \min_{e \in E} \Big( \text{Dijkstra}(G \setminus \{e\mid b(e) b(e)\}, \text{免除 } e) \Big)答案e∈Emin​(Dijkstra(G∖{e′∣b(e′)b(e)},免除e))其中E EE按b bb升序排列倒序枚举时G GG自动缩减。核心认知遇到“路径上某种属性的极值被优惠”时优先考虑枚举那个极值元素把优惠条件转化成一次性的零权边。排序 倒序删除是一种通用的“按属性降维”技巧能大幅简化图的动态维护。不要轻易将状态扩展到路径属性中除非你能保证状态压缩的单调性否则容易写出像84分BFS那样的“看起来对实则错”的代码。这道题教会我们的不是Dijkstra本身而是如何将动态的优惠规则转化为静态的枚举代价并利用排序来优化枚举顺序。希望你在遇到类似问题时能想到这层“剥离最高分”的思路。本文完如果你觉得有帮助欢迎点赞、收藏、转发让更多算法爱好者看到~有任何疑问或建议请在评论区留言交流。