P4568 分层图 · 楼房与水

当前时刻

0时间单位

拖动画布可以绕着楼转。竖直方向是免费次数 p，水平方向是城市。

点击 3D 里的任意一个球（房间），会显示它的状态编号。一个球就是一个状态 (城市, 已用次数)。

每行一层。金框是终点 t 那一列 —— 全表里最小的金框就是答案。

点亮某一层，其余层淡出。这时看得很清楚：同层的城市按网格排开，边铺满整个平面，不是一条链。

为什么 0 权边不破坏「弹出即定稿」

管道长度 ≥ 0，所以时间戳只增不减。长度为 0 的洞只会让下面的房间同时变湿，不会更早。

论证用的是 ≤ 而不是 <：设弹出的 d 全堆最小，若之后另有更早的水 t' < d 到达它，这份水必然经过一条当时还干的通道，其起点 x 满足 dist[x] ≤ t' < d，可 d 是全堆最小 —— 矛盾。

画面上的对应：水到一个房间，会立刻沿所有洞漏下去，所以同一时刻会有好几个房间一起湿。如果洞会倒赚时间（负权），水就倒流，done 立刻失效，必须换 SPFA。

为什么水只能往下，不会往回渗

免费边是单向的 (u,p) → (v,p+1)：免费次数只会变多，不会变少。所以第 p+1 层永远回不到第 p 层。

这一点让「层」方向天然有序，也解释了为什么洛谷上有一族题解可以「外层枚举 p、内层跑一遍最短路」。但同一层内部是乱窜的（无向边 + 任意边权），所以统一的二维 Dijkstra 一次就够。

只读第 k 层为什么错

题目是「至多 k 次」，走到第 p 层却相当于「恰好」用了 p 次。最短路可能只用了不到 k 次，第 k 层甚至根本不可达。

切到「只读第 k 层会错（k=10）」那个案例：第 0、2、4… 层终点房是 5，第 1、3、5… 层是 0。只读第 10 层得 5，正确答案是 0。

和你的 Dijkstra 代码怎么对上

answer = min(dist[t][p]) for p in 0..k