P4568 分层图 · 水流就是按 dist 从小到大填 DP 表

初始 · 时刻 0

堆顶：—

起点 (s,0) 已定稿（dist 已确定）候选（在堆里等着）还没被水碰到本步刚弹出（红）同层管道 +w 下潜一层 +0（单向）答案路径终点列 · 最后的答案格

初始状态

这一步在做什么弹出即定稿

0当前时间 / dist

水还没开始流。

实心绿 = 这一格已经定稿；虚线 = 只在堆里有个候选值，水还没流到，随时会被更小的值替换。金框是终点 t 那一列，其中最小的一格就是答案。

状态：(c,p) = 在城市 c、已用掉 p 张券。表里一格 = 楼里一个球，一共 n(k+1) 格。
无后效性：水到了 (c,p)，以后能去哪只跟 c、p 有关，跟「怎么来的」无关，所以每格可以单独求。
转移：dist[v][p] = min(dist[v][p], dist[u][p]+w)（付费），dist[v][p+1] = min(…, dist[u][p])（免费）。
顺序：同层之间能来回走，表里有环 → 没有拓扑序。但代价都 ≥ 0，小的 dist 永远不依赖大的 dist，于是「按 dist 从小到大填」就是合法顺序 = Dijkstra 弹堆 = 水波按时间漫延。
答案：题目是「至多 k 次」，答案 = min_p dist[t][p]，不是只读第 k 层。

点击 3D 里的任意一个球，会显示它是表里的哪一格、当前 dist、以及它的两条转移。Esc 取消。

点亮某一层，其余层淡出、向下的洞也藏起来。这时看得很清楚：同层的城市按网格排开，边铺满整个平面，正是那张「普通的最短路图」。

为什么「弹出顺序」就是合法的 DP 顺序

DP 的硬要求只有一条：算一格之前，它依赖的值必须已经算好。

这张表里每条转移的代价都是 w ≥ 0，所以 dist[v] ≥ dist[u]：依赖永远指向不小于自己的值。于是「从最小的格子开始填」时，当前这一格的所有前驱必然已经填完了。

如果弹出 d 之后还有更早的水 t' < d 能到它，那份水必须走一条当时还干的通道，起点 x 满足 dist[x] ≤ t' < d，可 d 是全堆最小 —— 矛盾。这就是「水只有一份、每格只扩展一次」的摊还来源。

画面上的对应：同一时刻会有好几个房间一起变湿（0 权边让水同时漏下去），但它们之间互不改进，所以一起定稿也无所谓。

为什么水只能往下漏

免费边是单向的 (u,p) → (v,p+1)：券只会越用越多，不会变少，所以第 p+1 层永远回不到第 p 层。楼的「竖直方向」天然有序。

但层内是乱窜的（无向边 + 任意正边权），所以每一层本身就是一张要跑最短路的小图。因此落地写法是把 (c,p) 当二维状态直接跑一次 Dijkstra；也有题解「外层枚举 p」，但每层内部仍然要跑一次完整的最短路。两种写法本质相同，都是这张状态图上的非负权最短路。

只读第 k 层为什么会错

题目是「至多 k 次」，走到第 p 层却相当于「恰好」用了 p 次。最短路可能只用了更少的券，而第 k 层可能是另一个（更贵的）值。

切到案例「只读第 k 层会错」：只有一条 0—1 边、权 5、k=10。奇数层的终点房是 0（用 1 张券飞过去），偶数层是 5（要凑成偶数张券，只能付一次钱）。只读第 10 层得 5，真答案 0。

这也解释了一个反直觉的小细节：奇数层与偶数层可以差很多，因为「多花 2 张券」只能靠原路来回，不能把花费再降下来。

和你的代码怎么对上

answer = min(dist[t][p]) for p in 0..k
时间 O(k(n+m) log(kn))，空间 O(nk + m)

拖动旋转 · 滚轮缩放 · 点球看状态 · ←→ 步进 · 空格 播放