打卡信奥刷题2678P2939 Revamping Trails G 分层图最短路从原理到AC这道题我刷的时候卡了两天不是不会写Dijkstra而是没想明白为什么改造K条路就能直接套分层图。等我真正把分层图跑通、把代码改到能过的时候发现这类题完全是套路。这篇博文就从P2939 Revamping Trails G出发把分层图最短路讲透顺带把我踩过的坑全部交代清楚。先交代信息P2939是USACO 2009年2月月赛Gold组题目题名Revamping Trails中文俗称重铺小路。在洛谷和各大OJ上都能交。适合人群是正在刷USACO、备战NOIP/CSP-S、或者刚学完堆优化Dijkstra想进阶的选手。如果你连Dijkstra都还不太熟建议先把最短路的板子敲熟再来看这篇不然吸收不了。1. 题目背景与核心问题拆解1.1 题目到底在说什么Farmer John有N个牧场编号从1到N牧场之间有M条双向道路连接。每条路上走一遍要花一定时间。现在FJ可以把其中最多K条道路升级成快速路升级之后走这条路的耗时变成0。问从牧场1走到牧场N的最短时间是多少。这里有几个隐藏信息值得先抠出来边是双向的所以建图时要加两条有向边最多改造K条不是必须改造K条这意味着答案可能是用了0条、1条……K条改造中的任意一个K的值通常不大题目给的K是整个算法的关键参数图里可能有重边和自环写代码时要注意不过一般取最小边权即可。数据范围大概是N不超过10000M不超过50000K不超过20。这个范围很关键决定了解法必须做到O((NM)logM)级别暴力枚举哪K条边改造根本不可能。1.2 关键突破点在哪里我先说结论这道题的正解是分层图 堆优化Dijkstra。核心思想是把一个允许K次免费的图拆成K1层平行的图。层与层之间通过免费通道连接坐一次免费通道就相当于消耗一次改造机会。于是问题从在K个位置选边置零这种组合优化问题转化成了一个普通的最短路问题。这句话初学者往往看不懂我打个比方。把整个路径想象成坐地铁每层图就是一张普通票价的地铁路网但是每两层之间有一条零元换乘通道走一次就消耗一张免费票而总共只有K张免费票。我们需要在用0张票到N、用1张票到N……用K张票到N这些方案里找到一个最短时间。这个思路一旦建立整道题就从脑筋急转弯变成了板子题。2. 解法选型为什么分层图最短路是正解2.1 先看几个必然会TLE的歪路很多第一次接触这题的同学第一反应是枚举所有边选K条置零然后跑最短路。我们来算算复杂度。M最大50000K最大20组合数C(50000, 20)是个天文数字想都不用想。那退一步用状态压缩DP呢图是稀疏图但N上万状态根本压不住。还有一种很常见的错误思路直接跑一遍最短路把最短路径上的前K大的边置零。这个思路在限定了只走一条固定最短路的假设下是对的但问题是你预选的这条最短路径可能根本不是最优的。比如为了用满K次免费你完全可能绕一点远路去贪图几条权值很大的边免费掉。换句话说最优解对应的路径很可能不在原始最短路径上。这属于最短路的局部贪心陷阱。2.2 分层图的核心原理分层图的本质是把已经使用了多少次改造作为状态的一维并且把状态转移也用图上的边来表示。具体来说我们创建K1层图每一层都有N个节点编号从1到N。第j层表示到目前为止已经使用了j次改造机会。那么在每一层内部按原图加边边权照常表示在这层状态里走普通路在第j层和第j1层之间从第j层的节点u向第j1层的节点v连一条边权为0的有向边前提是原图存在u到v的边这条0权边表示把u到v的这条路升级为快速路消耗一次机会由于道路是双向的这层连过去和连回来的0权边都要建。这样建出来的图从第0层的节点1出发走到第j层的节点N的最短路就恰好等于从1到N恰好允许使用j次最多j次改造机会的最短时间。为什么恰好和最多可以等价因为如果你在第j层内部走了一条不用改造的路径到达了N但你还剩免费票没花你完全可以从第j层的N通过0权边跳到第j1层的N时间不变所以最多j次的答案一定不会比恰好j次差。这也就是为什么最后取min时要遍历j0到K的所有dis[NjN]的原因。2.3 两种实现路线对比路线一直接建K1层图节点数变成(K1)×N然后用链式前向星或vector邻接表存边跑一次常规Dijkstra。代码直观但是要算准数组大小且建图比较费内存。路线二不显式建分层图而是用dist[u][j]表示到达原图节点u、使用了j次机会的最短时间在Dijkstra松弛时额外处理使用一次机会的转移。这种写法省内存代码也短但思路不如第一种那么直观新手容易把自己绕进去。我自己的经验是第一次刷这道题务必用路线一。因为分层图建好之后后面跑的Dijkstra就是你背熟的板子排查问题也容易。等你把分层图思想吃透了路线二其实只是在相同逻辑上做了状态压缩实现自然就顺了。3. 核心细节解析与关键参数3.1 建图环节的尺寸计算这是最容易出bug的地方。我们算一下原图节点数N分层后节点总数totalN N × (K1)编号方案第j层的节点u映射到新编号 u j × N原图每条无向边(u,v,w)要拆成方向相反的两条有向边在每一层里都要加这两条边所以同层边数 2 × M × (K1)跨层0权边第j层的u到第j1层的v因为原边是双向的所以每一条原边都会产生两条跨层0权边u(j)→v(j1) 和 v(j)→u(j1)一共 2 × M × K 条总边数 2M(K1) 2MK 2M(2K1)。用K20、M50000来算2×50000×41 410万条边。如果你用链式前向星数组就得开到2倍于总边数因为每条边存一次就是820万左右。我在第一次写的时候就栽在这里只开了200万条边的数组结果评测直接段错误。后来学会了一个习惯先按公式算出上界再在代码里开两倍余量的数组。3.2 初始化和优先队列的类型Dijkstra要用优先队列维护当前最短距离的节点。因为距离有可能更新多次队列里会有一堆过期的脏数据所以出队时要检查auto cur pq.top(); pq.pop(); int d -cur.first; int x cur.second; if (d ! dist[x]) continue; // 过期节点跳过这里我强调一个细节INF初值要开大分层图最多有21×1000021万个点最短路长度上界是原图最大路径累加但保险起见用0x3f3f3f3f或者const long long INF 1e18。如果你用int存dist0x3f3f3f3f约10亿完全够但为了保险我建议新手直接上long longDFT不了多少空间。3.3 一个反向思考的易错点有人会问为什么跨层边是从第j层的u连到第j1层的v而不是从u连到v后直接留在原层其实两者语义不同。如果同层内部原样连边跨层连零边那从第j层的u走到第j1层的v表示你从u出发经过升级后的u→v到达v此时你换到了多使用了一次机会的新状态。这个过程是正确的。如果你把跨层零边理解成原地进入下一层那是不对的因为你需要先走一条具体的边才能消耗机会。类似的题目还有P4568飞行路线洛谷也是一模一样的分层图模型。如果你会了P2939那道题至少能秒掉思路部分。4. 实操过程与完整C代码4.1 准备工作我用的是链式前向星存图因为USACO这种老题的数据量用vector邻接表也完全没问题但链式前向星在比赛里更通用且不容易被vector的动态扩容拖慢。如果读者对链式前向星不熟可以想象成每一条边存到一个数组里next指针指向上一个从同一节点出发的边的下标加边时新边永远插在头部。4.2 建图和Dijkstra关键代码#include bits/stdc.h using namespace std; const long long INF 1e18; struct Edge { int to, nxt, w; } e[8500000]; // 开两倍余量 int head[210005], tot; void addEdge(int u, int v, int w) { e[tot] {v, head[u], w}; head[u] tot; } void buildGraph(int N, int M, int K) { memset(head, 0, sizeof(head)); tot 0; // 假设原边已经按照先读入的方式临时存起来 // 这里简化直接演示分层加边的写法 // 同层加边layer 0..K for (int layer 0; layer K; layer) { // 每条原边(u,v,w) // 第layer层的u编号是 u layer * N addEdge(u layer * N, v layer * N, w); addEdge(v layer * N, u layer * N, w); // 跨层加边除了最后一层 if (layer K) { addEdge(u layer * N, v (layer 1) * N, 0); addEdge(v layer * N, u (layer 1) * N, 0); } } }注意上面的代码是伪结构示意真实实现中你需要先把M条原边存到一个临时数组比如u[i],v[i],w[i]三个数组里再在循环里统一建图。然后是Dijkstravectorlong long dijkstra(int s, int totalN) { vectorlong long dist(totalN 1, INF); priority_queuepairlong long, int, vectorpairlong long, int, greater pq; dist[s] 0; pq.push({0, s}); while (!pq.empty()) { auto [d, x] pq.top(); pq.pop(); if (d ! dist[x]) continue; for (int i head[x]; i; i e[i].nxt) { int y e[i].to; if (dist[y] dist[x] e[i].w) { dist[y] dist[x] e[i].w; pq.push({dist[y], y}); } } } return dist; }主函数里答案取long long ans INF; for (int j 0; j K; j) { ans min(ans, dist[N j * N]); } cout ans endl;注意这里不是只取第K层的dist[N]因为最多用K次意味着可以用0到K次中的任意值把每层到达N的值都取一遍最小值。4.3 完整可交代码核心片段#include bits/stdc.h using namespace std; const int MAXN 10005; const int MAXM 50005; const int MAXK 21; struct Edge { int to, nxt, w; }; // 2 * 2M * (2K1) 稍加余量即可满足 // 这里写死大小避免动态分配 Edge e[2 * 2 * MAXM * (2 * MAXK 1) 5]; int head[MAXN * MAXK], tot; int eu[MAXM], ev[MAXM], ew[MAXM]; void add(int u, int v, int w) { e[tot] {v, head[u], w}; head[u] tot; } // 其余同上因为在洛谷实际数据中N最大10000K最大20所以MAXK设成21节点总数上限210000。我第一次提交时就是因为把MAXK的数组开小了一个导致最后一层节点的下标越界WA得很隐蔽。5. 常见问题与排查技巧实录5.1 队列里脏数据导致TLE我发现很多人的Dijkstra在稀疏图上跑得飞快但在这种分层图上突然变慢。原因往往是不做距离检查让已经过期的节点反复出队、反复更新周围节点。加了if (d ! dist[x]) continue;之后效率立刻恢复。这是老生常谈但真的管用。5.2 跨层方向写反一个人最常见的错误是跨层边写成add(u j*N, v j*N, 0)也就是零边还在同一层这完全没有改变任何东西等于免费次数根本没消耗。写完后自己检查的办法是手动构造一个小图比如N3、M3、K1的三角形图跑一遍看中间层的节点是否有入边。5.3 重边和自环的隐藏坑USACO原题数据里不排除有重边。如果你用邻接矩阵存图重边要取最小的如果用链式前向星存重边不用管因为Dijkstra会自动取更优的。自环对最短路也基本无害但注意自环的零边会消耗一次机会这一般不影响最终答案因为走自环没有意义。5.4 确保没有忘记双向边原题道路是双向的意思是同一条路往返都要能走。我见过有人只建单方向边样例过了大样例突然挂。做法是每次读入(u,v,w)后临时数组存一次建图时正反各加一遍跨层也正反各加一遍。上面的伪代码已经体现但一定要落实到自己的代码里。5.5 输出类型是否用long long虽然这道题的权值累加在用int时可能不会溢出因为每个边权值不算巨大但我习惯直接开long long。因为一旦把K扩展大一点比如K50或者K100累加值就可能突破int上限而且写long long不需要额外操心还能避免一些玄学错误。5.6 逐层答案取min五个人里面至少有一个人最终挂在输出dist[N K * N]而不是取min上。要知道用不超过K次不等价于正好用K次。当最优解不需要用完K次时第K层的dist[N]可能不是最小。比如所有边权已经是0那么第0层的答案就是0后面每一层答案也是0取min没有影响但如果第0层答案是100用了1次改造变50再用更多次并不减少而你强制看第K层就错了。取min才是正确姿势。6. 这类题目的扩展与迁移分层图最短路不止P2939一道。洛谷P4568飞行路线本质上是最多可以把K条边的费用减半/免费一模一样的分层模型。再远一点一些允许状态升级的题比如购买道具后进入新状态、切换模式消耗代价也可以往分层图角度靠。节点状态不一定是已用几次机会可以是是否拿着某把钥匙是否开启了某个开关只要状态数量不大都可以把状态作为一维叠加到图上。我个人的学习顺序建议是先吃透P2939的显式建分层图写法然后把P4568拿来当做练习题再尝试用dist[u][j]的压缩写法重写一次。整个过程不需要太多新知识主要磨的是把题目翻译成图论模型的感觉。一旦这种感觉建立起来很多题目的难度会断崖式下降。最后再分享一个小技巧刷这类题不要一上来就看题解数据范围猜算法先把问题转化成图论语言——节点是什么、状态是什么、边是什么、代价是什么。四件套列清楚解法自然浮现。P2939就是把状态还剩多少次免费机会写进图里所有问题瞬间变成了普通最短路。你下次遇到类似题目时也可以先问自己能不能把选择这一维压进图里