UVa 13116 传送迷宫最短路：分组懒广播与Dijkstra优化

最近刷 UVa 的时候碰到 13116 Multistory Labyrinth 这题第一反应以为是个三维迷宫 BFS结果仔细一读题发现完全不是那么回事。它把“楼层”这个概念抽象成了矩阵里的数字同数字的房间之间可以互相传送移动又受楼层差限制本质上是个带传送门的最短路问题。做这题最有价值的不是 BFS 或者 Dijkstra 本身而是“同组节点只扩展一次”的优化思路这个思路在很多迷宫变种题里都能复用。这篇就来完整拆一下题目模型、算法选型和实现细节适合理清最短路优化逻辑、准备进阶图论题的选手参考。1. 把迷宫模型拆干净楼层、移动与传送规则先别急着写代码把题目翻译成人话。1.1 输入怎么读终点在哪里输入给的是一个 R 行 C 列的矩阵每个格子上有一个整数这个整数代表“楼层号”。起点是左上角 (0,0)终点是右下角 (R-1,C-1)。楼层号可能出现很大的值也可能是负数题目里没有保证值域很小所以后面存储分组时不能想当然开一个大数组。你要回答的问题只有一个从起点走到终点最少需要多少时间。每次移动消耗 1 单位时间没有别的代价。1.2 两种移动的成本与限制移动方式有两种这是理解题意的关键。第一种是普通移动往上、下、左、右走到相邻格子。但这里有一个限制——如果当前格子的楼层是 a目标格子的楼层是 b那么只有 abs(a-b) 1 才能走。也就是说你可以在同一楼层平移也可以从 3 楼走到 2 楼或 4 楼但不能从 3 楼一步跨到 5 楼。这个限制非常符合直觉楼层差距太大你没法直接走过去得找电梯或楼梯。第二种是传送如果两个格子的楼层号相同你可以从其中一个直接跳到另一个哪怕它们相隔十万八千里也只要 1 单位时间。这相当于每一层楼内部有一套传送系统把所有同一楼层的房间连成了一个完全图。把这两种规则合起来看这个迷宫的本质是你在地面上按楼层相邻规则走动遇到同楼层的房间可以瞬间位移。难点在于同一楼层可能有大量格子如果每次到达某个格子都把同楼层所有格子扫一遍复杂度会非常难看。1.3 一维化让代码和脑回路都少绕一圈处理二维网格最短路我习惯先把坐标压成一维下标id r * C c。这样 BFS 或者 Dijkstra 的队列里存的就是一个整数不用每次手动维护一个 pairint,int也方便用一维数组存距离。从一维下标还原坐标也很简单r id / Cc id % C。这题的分组存储也依赖一维化读入每个格子时按楼层号把下标塞进对应的组里。后面做传送扩展时直接拿到“这个楼层所有格子”的列表。2. 为什么直接 BFS 会翻车图论建模的复杂度分析很多同学一看到“每次移动代价都是 1”第一反应就是 BFS。但这里有个陷阱。2.1 传送门让隐式图变得极稠密如果没有传送门这就是一个普通的网格最短路BFS 的复杂度是 O(RC)非常轻松。但传送门的存在改变了一切。每层楼有 k 个格子这 k 个格子之间两两都可以传送相当于一个 k 个点的完全图边数是 k(k-1)/2。如果有若干层楼分别有 k1、k2、... 个格子总边数是 Σ O(ki²)。最坏情况下矩阵里一大半格子都是同一个楼层号那 ki ≈ N边数高达 O(N²)。此时如果显式建边内存和建图时间直接爆炸。即使不显式建边用 BFS 时每访问一个格子都去遍历整个同楼层组同样会让复杂度退化成 O(N²)。在一些输入规模较大的题里比如 R*C 到几万甚至更多时O(N²) 一定超时。2.2 朴素 BFS 和朴素建边的双重困境我把两种笨办法的代价分别说一下。第一种显式建完全图。每层楼的 k 个点之间都 push 一条边权为 1 的边然后跑普通最短路。这个方案在建边阶段就会超时超内存因为边数不可控。第二种不建边但是 BFS 出队一个格子时暴力扫描同楼层所有格子。这个方案时间上不可接受最坏每层楼有 N 个格子每访问一个格子都要扫一遍同组总操作量 O(N²)队列本身还要处理 N 个节点。一旦 N 到 10^5 级别基本跑不动。这两种方案其实都忽略了一个关键性质同一楼层分组之间并不需要把所有边都实际展开。2.3 正确的复杂度目标接近 O(N log N)我们需要一个方案让每个格子最多入队常数次并且每个楼层分组最多被完整遍历一次。这样总复杂度可以做到 O((N 总分组遍历量) log N)也就是 O(N log N)完全能接受。这个目标看起来很理想但实现有一个核心难点如何保证每个楼层分组只遍历一次同时不丢解。3. 核心解法Dijkstra 分组懒广播这题最漂亮的地方就在这一步。3.1 为什么选 Dijkstra 而不是 BFS虽然边权都是 1选 BFS 在原理上没错但 BFS 的层序扩展不容易配合“分组懒广播”的优化逻辑。Dijkstra 按距离从小到大的顺序弹节点保证了当某个节点第一次从优先队列里弹出时它的距离已经是最短距离。这个“第一次弹出即最短路”的性质正是我们做分组广播的正确性基础。注意如果传送成本也是 1那么整张图边权都是正数Dijkstra 完全适用。如果某些变种题把传送成本改成 0那就得退化成 0-1 BFS不过那是另一个话题。3.2 每个楼层分组只需要广播一次关键引理假设当前弹出节点 u它所在楼层是 color。我们要不要扫描 color 这一整组的所有格子尝试把它们的距离更新为 dist[u] 1结论是color 这一组只需要在第一次弹出该组节点时扫描一次后面再遇到同组节点直接跳过传送扩展。为什么Dijkstra 的弹出顺序保证第一个弹出的 color 组节点它的距离 d 是该组所有节点里的最短距离。用 d 1 去尝试更新同组所有节点得到的是该组所有节点通过传送门能拿到的最好上界。如果组里某个节点 x 已经通过普通移动得到更短路径那么 dist[x] 已经小于 d 1不会被覆盖如果 x 还没更短路径那 d 1 就是当前能给到的最优值。之后当 color 组另一个节点 y 从堆里弹出时它的距离一定不小于 d。用 dist[y] 1 去广播得到的候选值不小于 d 1不可能再刷新任何同组节点的距离。换句话说第二次、第三次广播都是无效劳动。所以正确做法是用一个标记数组记录“这个楼层已经被广播过”第一次弹出时遍历整组之后不再遍历。这个优化本质上是把“完全图的所有边”合并成了“一个虚拟源点到所有同组节点的星形边”。完全图的 O(k²) 条边被压缩成 O(k) 条广播边还不损失正确性。这里有一个容易踩坑的细节遍历整组时不能直接把同组所有节点的距离设置为 d 1。因为 d 1 只是一个候选最短路径同组节点可能早就通过普通移动获得了更短的 dist也可能稍后通过其他楼层传送获得更短路径。正确做法是每次发现dist[v] d 1才更新并把更新后的节点重新压入优先队列。每个格子可以因为普通移动入队多次也可以因为所在楼层第一次广播时入队一次。一个楼层组只会被完整遍历一次所以所有组的遍历总量是 O(N)不会退化。3.3 可运行的 C 主体代码我用 C 写了一个最小可运行版本直接说重点。#include bits/stdc.h using namespace std; const int INF 0x3f3f3f3f; const int dx[4] {-1, 1, 0, 0}; const int dy[4] {0, 0, -1, 1}; int main() { int T; scanf(%d, T); while (T--) { int R, C; scanf(%d%d, R, C); int N R * C; vectorint floor(N); mapint, vectorint group; // 楼层 - 格子下标列表 for (int r 0; r R; r) { for (int c 0; c C; c) { int id r * C c; scanf(%d, floor[id]); group[floor[id]].push_back(id); } } vectorint dist(N, INF); dist[0] 0; priority_queuepairint,int, vectorpairint,int, greaterpairint,int pq; pq.push({0, 0}); mapint, bool colorDone; // 该楼层是否已经广播过 while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (d ! dist[u]) continue; // 过期节点 int r u / C, c u % C; // 普通移动相邻且楼层差 1 for (int k 0; k 4; k) { int nr r dx[k], nc c dy[k]; if (nr 0 || nr R || nc 0 || nc C) continue; int v nr * C nc; if (abs(floor[v] - floor[u]) 1) continue; if (dist[v] d 1) { dist[v] d 1; pq.push({dist[v], v}); } } // 传送广播同楼层只处理一次 int color floor[u]; if (!colorDone[color]) { colorDone[color] true; for (int v : group[color]) { if (dist[v] d 1) { dist[v] d 1; pq.push({dist[v], v}); } } } } printf(%d\n, dist[N - 1] INF ? -1 : dist[N - 1]); } return 0; }这段代码的核心就一块if (!colorDone[color])包裹的广播逻辑。其它部分就是标准 Dijkstra。如果楼层号范围不大比如保证在 1 到 1000 之间可以把mapint, vectorint换成vectorvectorint group(MAXF)把colorDone换成vectorbool能省掉 map 的 log 开销。但如果题面没给值域用离散化更稳妥。3.4 另一种建模思路虚拟楼层节点除了“分组懒广播”这题还有一种理解方式拆出虚拟节点。对每个楼层 color 建一个虚拟点把该楼层所有实际格子连到虚拟点边权 1从虚拟点连回所有实际格子边权也为 1。这样原来任意两个同层格子之间的传送等价于“格子 - 虚拟点 - 格子”的两步路径总代价 2和直接传送的 1 不一样所以这个拆法不能直接照搬。如果传送代价是 0则可以用“进虚拟点 1、出虚拟点 0”或者反过来。但这题传送代价是 1虚拟拆点会导致代价偏移。所以在实现上我推荐直接用懒广播而不是虚拟拆点。虚拟拆点的思路更适合用来理解“为什么可以把完全图压成星形边”但不适合直接作为这题的答案。4. 实现细节与避坑清单看代码只有几十行但真写起来有不少细节。4.1 分组存储用 map 还是离散化我上面的代码用了mapint, vectorint。这样写稳妥但每个节点入组时要 O(log M) 插入M 是不同楼层数。如果数据量很大这个 log 成本累计起来也可观。更快的做法是先读一遍整个矩阵把楼层号收集起来排序去重做离散化映射然后再读一遍矩阵或者存下原始楼层值读完后统一映射。这样分组可以用vectorvectorint group(K)其中 K 是不同楼层数量查找分组下标是 O(1)。考虑到不少题是多组数据输入规模可能很大我建议能离散化就离散化。尤其当楼层号范围超过 10^6 时千万别开值域数组否则内存直接爆。虽然我给的示例代码用 map 是为了简洁但题解里我一般会按离散化实现。4.2 已处理标记放在哪个时机“标记已广播”这个动作必须放在第一次遇到该楼层节点、准备遍历整组之前。如果你先遍历了整组再设置标记那没问题但如果你只设置标记、忘记遍历整组那这层楼的传送门就完全没用了。还有一个小坑有些实现会在读入时就对每个楼层做标记初始化然后在普通移动里判断“如果目标楼层已经被广播过就不再加入队列”这是错的。因为普通移动和传送广播是两回事一个节点即使所在楼层已经广播过它依然可以被普通移动到达也必须继续从它身上做普通移动扩展。换句话说colorDone只影响“同楼层传送”这个动作不影响其它移动。4.3 传送扩展时不能直接把同组点标成最短我前面强调过这里再说一次。假设当前楼层 color 第一次被弹出距离是 d。正确做法是用 d 1 去尝试松弛同组所有节点。有些初学者会写成“同组所有节点距离都等于 d 1”这会导致结果偏大还是偏小如果同组某个节点 x 原本有一条更短的路径比如通过普通移动走了两步就到了distance 是 2而 d 1 是 5那直接覆盖会让答案变大。更危险的是如果你在第一次广播时把同组节点标成“已完成”那么以后即使有别的路径以更小代价到达它你也不会再处理它结果就错了。所以广播后节点仍然要正常入堆让 Dijkstra 自己决定最终最短路。4.4 边界条件终点就在起点、无解输出如果 R1, C1起点就是终点答案应该是 0。上面的代码里起点在初始化时已经入堆dist[0] 0最后输出 dist[N-1] 0没问题。如果终点不可达比如网格被不可穿越的楼层差挡住了且起点终点楼层号不同也没有任何可传送路径dist[N-1] 会保持 INF。题目如果没有保证有解建议输出 -1 或者按题目要求处理。我示例代码里写了-1但实际提交前要看清输出格式。另外起点本身也需要考虑传送如果起点所在楼层有很多格子第一次弹出起点时colorDone[color] 还是 false会触发一次广播把所有同层格子都拉进队列。这是对的不要跳过。5. 常见错误与排查技法速查做题过程中我整理过一张排查表直接给结论。症状可能原因解决方案提交超时每次弹出节点都遍历同楼层所有格子退化成 O(N²)改用 colorDone 标记每组只广播一次答案偏大把同组节点第一次广播后直接标为已完成错过了后续更短路径广播后继续入堆不要标记为 finished答案偏小传送广播时不判断dist[v] d 1无条件更新必须做松弛判断内存爆楼层号很大但开了vectorvectorint group(MAXF)离散化或使用 map/unordered_map结果一直是 0 或非常小把传送代价当成了 0传送也是 1按题意处理普通移动不生效判断楼层差时写成而不是 1确认条件是 abs(a-b) 1除了对照表我还会用微型样例验证逻辑。拿一个 1 行 4 列的矩阵举例3 3 3 3起点是下标 0终点是下标 3。第一次弹出 0 时广播楼层 3下标 1、2、3 的距离都变成 1。下标 3 直接变 1所以答案是 1。如果把传送代价理解错就会得到 3一测就能发现问题。再看一个需要普通移动的例子1 2 31 和 3 楼层差 2不能直接走。但 2 和 1、3 都差 1所以路径是 1 - 2 - 3答案 2。这个样例可以验证普通移动的条件有没有写反。我自己调试时还会顺手打印 dist 数组检查每个位置的值是否符合手算预期。Dijkstra 的 bug 往往不是算法本身而是边界判断和标记时机多打印两步就能定位。6. 写题解时我踩到的一个很实在的坑最后分享一个我实现时卡了很久的细节。一开始我把colorDone[color] true放在了优先队列弹出节点的“普通移动处理”之后。看起来没什么问题但后来发现如果把传送广播放在普通移动之前效率会更好逻辑也更安全因为优先队列里可能有多个同楼层节点等待弹出越早广播越早给同楼层其它节点一个候选上界它们入堆后也能更早被弹出。虽然最终复杂度一样但放在前面能让收敛过程更稳定。其实更关键的问题是colorDone的检查应该在普通移动之前还是之后从正确性上说两者都正确。但从 Dijkstra 的性质来想一个节点弹出时它的距离已经确定此时立刻处理该楼层广播和先做几步普通移动再做广播广播所用的 d 都是同一个值结果完全一样。不过我在第一版代码里犯过一个错误我在colorDone判断里直接遍历group[color]但遍历时没有跳过当前节点 u导致dist[u]被赋成d 1然后if (d ! dist[u])在下一轮弹出时把 u 判成过期节点虽然结果有时碰巧对但逻辑上很脏。所以广播遍历时最好还是加上if (v u) continue或者依靠松弛判断挡住但加一行判断更清晰。这题做完之后我最大的体会是遇到“同属性节点两两可达”的图论题就不要傻傻连完全图而是想办法把一组节点的所有边压缩成一个广播动作。很多看似复杂的迷宫和传送门问题最后都能用这个套路把复杂度从 O(N²) 拉回 O(N log N)。这种题刷一题比刷十题模板 BFS 都有用。