这段时间在整理信奥图论题单刷到P4822 [BJWC2012] 冻结时我停下来想了很久。这道题用C实现起来不算复杂但它背后那套“分层图最短路”的思想几乎贯穿了洛谷和省选里一大票同类题。如果你正在学信奥算法里的最短路径卡在图论进阶这条路上这道题是个非常合适的练手点——它不考偏门技巧拼的是你有没有把“额外状态”想清楚。本文我会从题目本质开始讲先解释为什么常规最短路不够用再给出两种可行的C实现最后把我实际调试中踩过的坑全部列出来希望帮你在刷题打卡的路上少走弯路。1. P4822到底在考什么从“冻结”技能看分层图最短路的套路1.1 题目回顾冻结技能到底在改变什么把题意复述一遍。一张无向图n个点m条边每条边有一个通过时间w。你有一种“冻结”技能最多可以用k次每次选择一条边让这条边的通过时间减半整数除法向下取整。目标是求从1号点到n号点的最短总时间。这句话乍一看就是“最短路 一个剪枝操作”但恰恰是那个剪枝操作让题目从板子题变成了建模题。原因有三个第一技能次数是有限的k次你不能对所有的边都用一遍第二使用技能之后边的权值会变小而路径选择会因此发生变化一条边值不值得走取决于你有没有把技能留给它第三最优解里那些“被减半的边”未必在原图的最短路径上甚至可能为了用掉一次技能而故意绕路。这三点加在一起就排除了所有“先跑一遍普通最短路再在路径上挑边减半”的偷懒思路。数据范围我记得是n≤50m≤1000k≤50。这个范围不算大但也没小到可以随便暴力枚举边的组合。你要枚举“哪些边被减半”的话是指数级的完全不可行但如果建模正确Dijkstra跑起来会非常轻松。所以这道题本质上不是考你优化的功力而是考你抽象状态的能力。1.2 贪心的诱惑与反例为什么不能先跑最短路再减半很多同学第一次做这道题第一反应是先跑一遍Dijkstra求出1到n的最短路然后在这条路径上挑最长的k条边减半就行了。这个想法很自然但它错在前提上——最优路径未必是原图最短路。打个比方你手里有三张优惠券不一定非要在最便宜的餐馆里用掉可能去一家略贵的餐厅用了券之后整体反而更划算。我构造过这样一个反例帮助自己理解假设1号点有一条直达n号点的边权值是100同时还有一条绕路由三条边组成每条的权值分别是40、40、40总长度是120。如果k1原图最短路是100沿着它减半之后变成50但如果你走绕路把其中一条40减半成20总代价是204040100和直连减半打平。如果把直连边权改成101绕路不变那么原图最短路是101减半后是50101/250向下取整绕路路径减半一条边后是204040100。这时候还是直连优。但如果调整一下直连边权是120绕路三条边都是40k1原图最短路是120直连减半后60绕路减半一条40后是204040100反而更差。所以光靠“先最短路再减半”不可靠的关键点在于你选的边和走的路径是耦合在一起的。正确的做法是把“用了多少次技能”变成状态的一部分让最短路算法自己在状态空间里找答案。这就是分层图模型的动机。2. 两种建图姿势显式分层图 vs 状态压缩最短路2.1 显式分层图把“技能次数”拆成维度分层图最短路这个叫法听起来玄乎实际做法非常直观原来的图是“一层”现在复制出k1层第i层代表“已经使用了i次冻结技能”时的状态。层内边的边权就是原图中的w表示这次走动不用技能层与层之间的边从第i层的u连向第i1层的v边权为w/2表示这次从u到v用掉了1次技能代价减半。因为技能只能从第i层单向走到第i1层不可能跳层所以最短路算法跑完之后到达第i层的终点就对应着一种“用了i次技能”的方案。最后把第0层到第k层的终点距离全部取一遍最小值就是答案。这个建模最巧妙的地方在于它把“次数限制”变成“层数方向限制”。你不需要在代码里额外判断“还剩几次技能”因为图的拓扑结构已经保证了你没法回到之前的层。复杂度上点数是n×(k1)边数是“层内边 跨层边”两部分都是O(m(k1))。本题n≤50k≤50点最多2550个边量也很小Dijkstra瞬间跑完。2.2 状态压缩写法同一模型的内存优化版如果觉得显式建图要开point_id数组、逐条建边太啰嗦还有一个非常常见的做法不显式复制图而是把“当前用了多少次技能”作为最短路的第二维状态。dist[u][used]表示到达点u、已经使用了used次技能所需的最短时间。转移时有两种选择不走技能边dist[to][used] min(dist[to][used], dist[u][used] w)走技能边dist[to][used1] min(dist[to][used1], dist[u][used] w/2)。这个写法的本质和分层图完全一样只是不建真实的图层Dijkstra的节点从“点的编号”变成“(点, 已用次数)”二元组。优点是不用操心节点编号分配代码量少很多缺点是你得自己想明白为什么同一个点会以不同used状态出现在堆里这其实是同一个物理点在不同“技能层”上的投影。2.3 我推荐的写法先分层图再过渡到状态DP我教新人的时候会让他们先把显式分层图写一遍因为“建图→跑最短路”这个流程和普通Dijkstra一模一样心智负担小。等理解了分层图为什么能保证“技能次数不会超过k”之后再回去写状态压缩版这时候会有一种“原来代码还能短一半”的爽感。这篇文章给出的最终代码是状态压缩版理由有两条一是它看起来更像“最短路DP”的混合体后面遇到更多进阶题时迁移更顺二是它更省内存如果哪天n和k范围变大显式建图的vector可能会被卡。3. 关键代码逐行拆解从建边到Dijkstra的完整C实现3.1 边的存储与读入无向图别漏了双向边先给出完整代码我建议你直接在洛谷交这一版#include bits/stdc.h using namespace std; const int MAXN 55; const int MAXK 55; const long long INF 0x3f3f3f3f3f3f3f3fLL; struct Edge { int to; int w; }; struct State { int u; int used; long long d; bool operator(const State other) const { return d other.d; // 小根堆 } }; int n, m, k; vectorEdge G[MAXN]; long long dist[MAXN][MAXK]; void dijkstra() { memset(dist, 0x3f, sizeof(dist)); priority_queueState pq; dist[1][0] 0; pq.push({1, 0, 0}); while (!pq.empty()) { State cur pq.top(); pq.pop(); if (cur.d ! dist[cur.u][cur.used]) continue; // 过期节点剪枝 for (const Edge e : G[cur.u]) { // 情况1不使用冻结技能 if (dist[e.to][cur.used] cur.d e.w) { dist[e.to][cur.used] cur.d e.w; pq.push({e.to, cur.used, dist[e.to][cur.used]}); } // 情况2使用一次冻结技能 if (cur.used k dist[e.to][cur.used 1] cur.d e.w / 2) { dist[e.to][cur.used 1] cur.d e.w / 2; pq.push({e.to, cur.used 1, dist[e.to][cur.used 1]}); } } } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n m k; 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}); // 无向图必须双向 } dijkstra(); long long ans INF; for (int used 0; used k; used) { ans min(ans, dist[n][used]); } cout ans \n; return 0; }代码不长核心就两个松弛分支。但有几个地方新手特别喜欢写错我单独拿出来讲。3.2 为什么dist要开二维状态是点和技能次数的组合dist[u][used]而不是dist[u]的原因上面已经说了。关键点是转移的顺序有讲究吗其实没有。最短路算法靠松弛收敛不是靠一次遍历所以先走“不用技能”还是先走“用技能”都没关系。但请务必注意w/2用的是整数除法自动向下取整。题目里“时间减半”没有特殊说明默认按整除处理千万别写浮点除法再转int没那个必要还可能出精度问题。另外dist数组我开的是long long。虽然本题n只有50边权和路径长度大概率不会爆int但图论题目里养成用long long的习惯能避免很多边界问题。memset(dist, 0x3f, sizeof(dist))配合long long的INF写法是0x3f3f3f3f3f3f3f3fLL不要写成int版的0x3f3f3f3f否则memset出来的值会不对。3.3 优先队列的剪枝条件d ! dist[u][used]的来历很多Dijkstra模板里写的是if (vis[u]) continue或者if (d dist[u]) continue。这里我用的是if (cur.d ! dist[cur.u][cur.used]) continue。原因很简单同一个(u, used)状态可能被多次松弛进堆只有最新、距离最小的那次才需要弹出后继续扩展。用“不等于”而不是“大于”是为了在long long比较下更直观也避免因为某些重复状态被漏掉。如果你习惯用vis数组也可以但要注意vis也要开二维否则会错误地把“同一个点但不同技能次数”的状态混为一谈。3.4 取答案别只盯着终点第k层最后求答案时可以到达终点且用了0到k次技能都行。所以取所有dist[n][used]的最小值。这一点特别容易被忽略——有些人直接输出dist[n][k]默认“技能越多越好”。可万一某条边权是1或0减半后没有变化多用的那次技能不一定带来收益虽然通常不会让答案变大但严格来说你需要额外证明才能确定“用满k次一定不劣”。最稳妥的做法就是循环取min代码只有三行别省这个功夫。4. 这道题最容易翻车的四个细节实测踩坑记录4.1 翻车点1无向边只建了单向这是我第一次提交WA的原因之一。读题时看到“道路”两个字下意识以为是有向图结果只push了单向边。洛谷的评测不会提示你“是不是无向图”只会告诉你答案错误。检查这类错误最快的办法自造一个小样例把1和2两个点连通跑一下看看从2能不能到达1。这道题既然说了是无向图建边就必须正反各push一次。很多分层图题目的样例规模小单向边也可能侥幸通过几个点但大数据一上来就全完。4.2 翻车点2优先队列的比较器方向优先队列默认是“大根堆”所以如果要小根堆写法是重载operator返回d other.d。这个“反直觉”设定坑过几乎所有学C图论的人。我的建议是不用纠结为什么是大于直接在代码注释里写上“// 小根堆”每次复制模板的时候确认一下。另一种不容易混的写法是struct Node { int u, used; long long d; bool operator(const Node other) const { return d other.d; } }; priority_queueNode, vectorNode, greaterNode pq;这种写法语义更直白但需要include 。我用bits/stdc.h就无所谓了。4.3 翻车点3数组大小和INF的选择dist[MAXN][MAXK]的MAXK至少要开到k1因为技能次数可以是0到k一共k1种状态。如果只开成MAXK50那么当k50、used49再走技能边时used150虽然刚好不越界但dist[e.to][50]这个位置如果没开够就会访问越界结果是玄学WA或者RE。同样MAXN也要比实际点数大一点点别卡着50开留出余量。INF方面前面说了用long long的0x3f3f3f3f3f3f3f3fLL。这个值的妙处在于它足够大又能在memset时用0x3f按字节填充算出来的初始值就是可用的INF。如果你图省事直接用1e18也行但memset时就只能写memset(dist, 0x3f, sizeof(dist))配合0x3f3f3f3f3f3f3f3fLL两者必须匹配好。4.4 翻车点4把w直接减半还是w/2的语义“每条边的时间减半”在整数除法里就是w/2不管w是奇数还是偶数。不要写w - w/2那是“剩余多少”而不是“减半后的花费”。如果你把w/2误写成w - w/2样例可能也能过因为很多样例边权都是偶数但这会在隐藏数据上出错。调试时可以用这个样例验证3 3 1 1 2 3 2 3 3 1 3 7正确答案是4。不使用技能走1-3是7使用技能把1-2的3减半成1走1-2-3是134把2-3减半成1走1-2-3是314。如果你的程序输出5或7说明w/2或者建边那里写歪了。5. 从P4822出发分层图能带走的一整类信奥题5.1 同类题清单飞行路线、修路等刷完P4822可以立刻去刷这几道它们几乎是同一个思路换了一层皮P4568 [JLOI2011] 飞行路线k次免费坐飞机和本题一模一样只是把边权w改成0P2939 [USACO09FEB] Revamping Trailsk次把某条路的花费改成0也是分层图P1948 [USACO08JAN] Telephone Linesk条免费边之后求剩下的最大边权最小这题需要“分层图 二分答案”或者“分层图上跑最短路求第k1大的边权”。这些题的特点是都有一个“最多k次额外操作”的限制而这个操作会让边的某个属性发生变化减半、变0、变某个值。遇到“操作次数有限”“路径代价”同时出现的描述优先想分层图。5.2 从一道题到一类题分层图的识别信号我在信奥题单上总结了三个信号分享给你出现了“最多使用k次xx技能/免费券/优惠券”这类限定这个技能的作用对象是边或点影响的是边权或点权k的范围不大一般≤100允许开O(nk)或者O(mk)级别的状态。满足这三条大概率可以用分层图或带状态最短路解决。但如果k很大比如k≤10^9那就不能这么拆了得想费用流、贪心或者二分答案的路线那是另一个话题。5.3 刷题节奏建议怎么把打卡刷出效果最后结合我自己带刷题的经验给刷到本题的你再提几个小建议。先自己写不看题解哪怕写半小时一小时。分层图这个模型只有自己踩过坑才记得牢。AC之后把状态压缩版和显式分层图版各写一遍对比差异。写两种版本的过程中你会把“图层”和“状态维”彻底打通。一周后尝试不参考任何东西重写一次如果卡住说明还没有真正吃透回到上面的代码逐行再看。这种“一道题吃透一个模型”的刷法比连着刷十道同质题更有效率。等你把飞行路线那几道题也AC掉回头再看P4822会觉得它不过是个普通的分层图板子题。我在信奥备考阶段最受益的就是这种“一类题反复打磨到能默写”的训练方式。希望这篇题解能帮你少走点弯路把分层图这个高频考点稳稳拿下来。 
长河君 · 2026/9/15 2:58:40 · 阅读 1.2k 分层图最短路详解：从洛谷P4822冻结理解C++实现与建模套路
这段时间在整理信奥图论题单刷到P4822 [BJWC2012] 冻结时我停下来想了很久。这道题用C实现起来不算复杂但它背后那套“分层图最短路”的思想几乎贯穿了洛谷和省选里一大票同类题。如果你正在学信奥算法里的最短路径卡在图论进阶这条路上这道题是个非常合适的练手点——它不考偏门技巧拼的是你有没有把“额外状态”想清楚。本文我会从题目本质开始讲先解释为什么常规最短路不够用再给出两种可行的C实现最后把我实际调试中踩过的坑全部列出来希望帮你在刷题打卡的路上少走弯路。1. P4822到底在考什么从“冻结”技能看分层图最短路的套路1.1 题目回顾冻结技能到底在改变什么把题意复述一遍。一张无向图n个点m条边每条边有一个通过时间w。你有一种“冻结”技能最多可以用k次每次选择一条边让这条边的通过时间减半整数除法向下取整。目标是求从1号点到n号点的最短总时间。这句话乍一看就是“最短路 一个剪枝操作”但恰恰是那个剪枝操作让题目从板子题变成了建模题。原因有三个第一技能次数是有限的k次你不能对所有的边都用一遍第二使用技能之后边的权值会变小而路径选择会因此发生变化一条边值不值得走取决于你有没有把技能留给它第三最优解里那些“被减半的边”未必在原图的最短路径上甚至可能为了用掉一次技能而故意绕路。这三点加在一起就排除了所有“先跑一遍普通最短路再在路径上挑边减半”的偷懒思路。数据范围我记得是n≤50m≤1000k≤50。这个范围不算大但也没小到可以随便暴力枚举边的组合。你要枚举“哪些边被减半”的话是指数级的完全不可行但如果建模正确Dijkstra跑起来会非常轻松。所以这道题本质上不是考你优化的功力而是考你抽象状态的能力。1.2 贪心的诱惑与反例为什么不能先跑最短路再减半很多同学第一次做这道题第一反应是先跑一遍Dijkstra求出1到n的最短路然后在这条路径上挑最长的k条边减半就行了。这个想法很自然但它错在前提上——最优路径未必是原图最短路。打个比方你手里有三张优惠券不一定非要在最便宜的餐馆里用掉可能去一家略贵的餐厅用了券之后整体反而更划算。我构造过这样一个反例帮助自己理解假设1号点有一条直达n号点的边权值是100同时还有一条绕路由三条边组成每条的权值分别是40、40、40总长度是120。如果k1原图最短路是100沿着它减半之后变成50但如果你走绕路把其中一条40减半成20总代价是204040100和直连减半打平。如果把直连边权改成101绕路不变那么原图最短路是101减半后是50101/250向下取整绕路路径减半一条边后是204040100。这时候还是直连优。但如果调整一下直连边权是120绕路三条边都是40k1原图最短路是120直连减半后60绕路减半一条40后是204040100反而更差。所以光靠“先最短路再减半”不可靠的关键点在于你选的边和走的路径是耦合在一起的。正确的做法是把“用了多少次技能”变成状态的一部分让最短路算法自己在状态空间里找答案。这就是分层图模型的动机。2. 两种建图姿势显式分层图 vs 状态压缩最短路2.1 显式分层图把“技能次数”拆成维度分层图最短路这个叫法听起来玄乎实际做法非常直观原来的图是“一层”现在复制出k1层第i层代表“已经使用了i次冻结技能”时的状态。层内边的边权就是原图中的w表示这次走动不用技能层与层之间的边从第i层的u连向第i1层的v边权为w/2表示这次从u到v用掉了1次技能代价减半。因为技能只能从第i层单向走到第i1层不可能跳层所以最短路算法跑完之后到达第i层的终点就对应着一种“用了i次技能”的方案。最后把第0层到第k层的终点距离全部取一遍最小值就是答案。这个建模最巧妙的地方在于它把“次数限制”变成“层数方向限制”。你不需要在代码里额外判断“还剩几次技能”因为图的拓扑结构已经保证了你没法回到之前的层。复杂度上点数是n×(k1)边数是“层内边 跨层边”两部分都是O(m(k1))。本题n≤50k≤50点最多2550个边量也很小Dijkstra瞬间跑完。2.2 状态压缩写法同一模型的内存优化版如果觉得显式建图要开point_id数组、逐条建边太啰嗦还有一个非常常见的做法不显式复制图而是把“当前用了多少次技能”作为最短路的第二维状态。dist[u][used]表示到达点u、已经使用了used次技能所需的最短时间。转移时有两种选择不走技能边dist[to][used] min(dist[to][used], dist[u][used] w)走技能边dist[to][used1] min(dist[to][used1], dist[u][used] w/2)。这个写法的本质和分层图完全一样只是不建真实的图层Dijkstra的节点从“点的编号”变成“(点, 已用次数)”二元组。优点是不用操心节点编号分配代码量少很多缺点是你得自己想明白为什么同一个点会以不同used状态出现在堆里这其实是同一个物理点在不同“技能层”上的投影。2.3 我推荐的写法先分层图再过渡到状态DP我教新人的时候会让他们先把显式分层图写一遍因为“建图→跑最短路”这个流程和普通Dijkstra一模一样心智负担小。等理解了分层图为什么能保证“技能次数不会超过k”之后再回去写状态压缩版这时候会有一种“原来代码还能短一半”的爽感。这篇文章给出的最终代码是状态压缩版理由有两条一是它看起来更像“最短路DP”的混合体后面遇到更多进阶题时迁移更顺二是它更省内存如果哪天n和k范围变大显式建图的vector可能会被卡。3. 关键代码逐行拆解从建边到Dijkstra的完整C实现3.1 边的存储与读入无向图别漏了双向边先给出完整代码我建议你直接在洛谷交这一版#include bits/stdc.h using namespace std; const int MAXN 55; const int MAXK 55; const long long INF 0x3f3f3f3f3f3f3f3fLL; struct Edge { int to; int w; }; struct State { int u; int used; long long d; bool operator(const State other) const { return d other.d; // 小根堆 } }; int n, m, k; vectorEdge G[MAXN]; long long dist[MAXN][MAXK]; void dijkstra() { memset(dist, 0x3f, sizeof(dist)); priority_queueState pq; dist[1][0] 0; pq.push({1, 0, 0}); while (!pq.empty()) { State cur pq.top(); pq.pop(); if (cur.d ! dist[cur.u][cur.used]) continue; // 过期节点剪枝 for (const Edge e : G[cur.u]) { // 情况1不使用冻结技能 if (dist[e.to][cur.used] cur.d e.w) { dist[e.to][cur.used] cur.d e.w; pq.push({e.to, cur.used, dist[e.to][cur.used]}); } // 情况2使用一次冻结技能 if (cur.used k dist[e.to][cur.used 1] cur.d e.w / 2) { dist[e.to][cur.used 1] cur.d e.w / 2; pq.push({e.to, cur.used 1, dist[e.to][cur.used 1]}); } } } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n m k; 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}); // 无向图必须双向 } dijkstra(); long long ans INF; for (int used 0; used k; used) { ans min(ans, dist[n][used]); } cout ans \n; return 0; }代码不长核心就两个松弛分支。但有几个地方新手特别喜欢写错我单独拿出来讲。3.2 为什么dist要开二维状态是点和技能次数的组合dist[u][used]而不是dist[u]的原因上面已经说了。关键点是转移的顺序有讲究吗其实没有。最短路算法靠松弛收敛不是靠一次遍历所以先走“不用技能”还是先走“用技能”都没关系。但请务必注意w/2用的是整数除法自动向下取整。题目里“时间减半”没有特殊说明默认按整除处理千万别写浮点除法再转int没那个必要还可能出精度问题。另外dist数组我开的是long long。虽然本题n只有50边权和路径长度大概率不会爆int但图论题目里养成用long long的习惯能避免很多边界问题。memset(dist, 0x3f, sizeof(dist))配合long long的INF写法是0x3f3f3f3f3f3f3f3fLL不要写成int版的0x3f3f3f3f否则memset出来的值会不对。3.3 优先队列的剪枝条件d ! dist[u][used]的来历很多Dijkstra模板里写的是if (vis[u]) continue或者if (d dist[u]) continue。这里我用的是if (cur.d ! dist[cur.u][cur.used]) continue。原因很简单同一个(u, used)状态可能被多次松弛进堆只有最新、距离最小的那次才需要弹出后继续扩展。用“不等于”而不是“大于”是为了在long long比较下更直观也避免因为某些重复状态被漏掉。如果你习惯用vis数组也可以但要注意vis也要开二维否则会错误地把“同一个点但不同技能次数”的状态混为一谈。3.4 取答案别只盯着终点第k层最后求答案时可以到达终点且用了0到k次技能都行。所以取所有dist[n][used]的最小值。这一点特别容易被忽略——有些人直接输出dist[n][k]默认“技能越多越好”。可万一某条边权是1或0减半后没有变化多用的那次技能不一定带来收益虽然通常不会让答案变大但严格来说你需要额外证明才能确定“用满k次一定不劣”。最稳妥的做法就是循环取min代码只有三行别省这个功夫。4. 这道题最容易翻车的四个细节实测踩坑记录4.1 翻车点1无向边只建了单向这是我第一次提交WA的原因之一。读题时看到“道路”两个字下意识以为是有向图结果只push了单向边。洛谷的评测不会提示你“是不是无向图”只会告诉你答案错误。检查这类错误最快的办法自造一个小样例把1和2两个点连通跑一下看看从2能不能到达1。这道题既然说了是无向图建边就必须正反各push一次。很多分层图题目的样例规模小单向边也可能侥幸通过几个点但大数据一上来就全完。4.2 翻车点2优先队列的比较器方向优先队列默认是“大根堆”所以如果要小根堆写法是重载operator返回d other.d。这个“反直觉”设定坑过几乎所有学C图论的人。我的建议是不用纠结为什么是大于直接在代码注释里写上“// 小根堆”每次复制模板的时候确认一下。另一种不容易混的写法是struct Node { int u, used; long long d; bool operator(const Node other) const { return d other.d; } }; priority_queueNode, vectorNode, greaterNode pq;这种写法语义更直白但需要include 。我用bits/stdc.h就无所谓了。4.3 翻车点3数组大小和INF的选择dist[MAXN][MAXK]的MAXK至少要开到k1因为技能次数可以是0到k一共k1种状态。如果只开成MAXK50那么当k50、used49再走技能边时used150虽然刚好不越界但dist[e.to][50]这个位置如果没开够就会访问越界结果是玄学WA或者RE。同样MAXN也要比实际点数大一点点别卡着50开留出余量。INF方面前面说了用long long的0x3f3f3f3f3f3f3f3fLL。这个值的妙处在于它足够大又能在memset时用0x3f按字节填充算出来的初始值就是可用的INF。如果你图省事直接用1e18也行但memset时就只能写memset(dist, 0x3f, sizeof(dist))配合0x3f3f3f3f3f3f3f3fLL两者必须匹配好。4.4 翻车点4把w直接减半还是w/2的语义“每条边的时间减半”在整数除法里就是w/2不管w是奇数还是偶数。不要写w - w/2那是“剩余多少”而不是“减半后的花费”。如果你把w/2误写成w - w/2样例可能也能过因为很多样例边权都是偶数但这会在隐藏数据上出错。调试时可以用这个样例验证3 3 1 1 2 3 2 3 3 1 3 7正确答案是4。不使用技能走1-3是7使用技能把1-2的3减半成1走1-2-3是134把2-3减半成1走1-2-3是314。如果你的程序输出5或7说明w/2或者建边那里写歪了。5. 从P4822出发分层图能带走的一整类信奥题5.1 同类题清单飞行路线、修路等刷完P4822可以立刻去刷这几道它们几乎是同一个思路换了一层皮P4568 [JLOI2011] 飞行路线k次免费坐飞机和本题一模一样只是把边权w改成0P2939 [USACO09FEB] Revamping Trailsk次把某条路的花费改成0也是分层图P1948 [USACO08JAN] Telephone Linesk条免费边之后求剩下的最大边权最小这题需要“分层图 二分答案”或者“分层图上跑最短路求第k1大的边权”。这些题的特点是都有一个“最多k次额外操作”的限制而这个操作会让边的某个属性发生变化减半、变0、变某个值。遇到“操作次数有限”“路径代价”同时出现的描述优先想分层图。5.2 从一道题到一类题分层图的识别信号我在信奥题单上总结了三个信号分享给你出现了“最多使用k次xx技能/免费券/优惠券”这类限定这个技能的作用对象是边或点影响的是边权或点权k的范围不大一般≤100允许开O(nk)或者O(mk)级别的状态。满足这三条大概率可以用分层图或带状态最短路解决。但如果k很大比如k≤10^9那就不能这么拆了得想费用流、贪心或者二分答案的路线那是另一个话题。5.3 刷题节奏建议怎么把打卡刷出效果最后结合我自己带刷题的经验给刷到本题的你再提几个小建议。先自己写不看题解哪怕写半小时一小时。分层图这个模型只有自己踩过坑才记得牢。AC之后把状态压缩版和显式分层图版各写一遍对比差异。写两种版本的过程中你会把“图层”和“状态维”彻底打通。一周后尝试不参考任何东西重写一次如果卡住说明还没有真正吃透回到上面的代码逐行再看。这种“一道题吃透一个模型”的刷法比连着刷十道同质题更有效率。等你把飞行路线那几道题也AC掉回头再看P4822会觉得它不过是个普通的分层图板子题。我在信奥备考阶段最受益的就是这种“一类题反复打磨到能默写”的训练方式。希望这篇题解能帮你少走点弯路把分层图这个高频考点稳稳拿下来。