最近刷UVa时撞上13116这道Multistory Labyrinth，第一眼以为就是个走迷宫，BFS莽一下就行，结果仔细读完题发现完全不是那么回事。这道题把“楼层”这个概念实打实嵌进了网格迷宫模型里，层与层之间靠传送点衔接，整张图带权，还可能带负分。这段时间我把这道题从建模到DP重头到尾撸了一遍，踩了不少坑，也整理出了一套能直接照抄的解法思路。如果你也在做图论DP、DAG最长路这类练习，或者正在刷UVa题库，这篇文章应该能帮你少走几条弯路。
1. 题意拆解与核心考点
1.1 多楼层迷宫在题目里到底是个什么结构
先从题目结构说起。Multistory Labyrinth不是普通的二维迷宫，它是一个由多层平面网格堆叠起来的立体结构，每一层都是一张独立的网格图。你从某一层的某个格子出发，可以沿着上下左右四个方向在当前楼层内移动，也可以踩上某些特殊格子，通过这些传送点直接跳到其他楼层去。每到达一个新格子，就会获得（或者失去）该格子上标注的分数，最终目标是到达指定的终点格子，并让总得分尽可能大。
这里要注意，楼层不是孤立的。传送点把层与层连接起来，整张地图变成了一张由跨层边和同层边构成的带权图。网格本身是节点，每一步移动则相当于一条边。因为移动是带收益的，所以这不是一个单纯求最短路径的问题，而是一个求最大累计收益的问题。
这类题最大的迷惑性在于：看起来像迷宫，实际上考的是图论建模和动态规划。如果你一上来就写BFS或者DFS搜索所有路径，在数据范围稍微大一点的情况下会直接炸掉，因为路径数量是组合级的，暴力枚举根本撑不住。
1.2 为什么一眼看出这是DAG最长路
判断一道题能不能用DAG上的DP来解，关键看图里有没有环。我在读题的时候重点确认的就是这一点：跨层传送方向是不是单向的。
把楼层按顺序编号为0到L-1，如果传送方向只能从编号小的楼层去编号更大的楼层（或者反过来），那么任意一条路径从整体趋势上看一定是逐层推进的，不可能出现绕了一圈又回到同一楼层同一格子的情况。而同层内移动虽然看起来是来回走动的，但如果你把时间顺序算进去，路径一旦通过传送门上升或下降一层，就不可能再回到之前的楼层——除非存在反向跨层边，那就另当别论了。
这道题的前提恰恰就是传送方向单向且楼层逐级推进。因此整个图天然无环，是一个标准的有向无环图。在DAG上求带权最长路，不需要Dijkstra，不需要SPFA，直接用动态规划扫一遍就能出答案，复杂度是线性的。这也是整个解法的核心突破口。
1.3 与经典网格题的本质区别
以前我们做的网格题，比如求最短步数、求可达性、求方案数，大多是在无权图上跑的，BFS一把梭就完事。但Multistory Labyrinth这一类题引入了“边权”的概念，而且权值有正有负。
带权图上的最优路径问题就需要分情况讨论了。如果所有边权非负，Dijkstra可以处理；如果图里可能有负权边但无负环，SPFA能用，但最坏情况复杂度很难看；如果图本身是DAG，那就什么都不用纠结，记忆化搜索或者拓扑序DP是最优解，连优先队列都不用。
这道题恰好落在第三种情况里，所以我选DP方案而不是其他方法，不是因为它简单，而是因为它在数学上最契合问题结构。后面我会详细拆解完整的建图方式和两个可选的实现版本。
2. 建模方案：把迷宫变成一张带权DAG
2.1 节点编号的心法
要把二维网格叠成三维图，第一步是编号。编号方案直接决定后面所有代码好不好写，我推荐用一维编号。
假设每层有R行C列，共R乘C个格子。楼层编号floor从0到L-1，行号r从0到R-1，列号c从0到C-1。那么每个格子的全局编号可以设计为：
int id(int floor, int r, int c) { return floor * (R * C) + r * C + c; }这样设计的好处在于，楼层越高，编号区间越大。0层的格子编号是0到R乘C减1，1层的格子从R乘C开始，依此类推。后面做拓扑排序或者记忆化搜索时，我们能很方便地从节点编号直接倒推出它属于哪一层、哪一行哪一列，不必单独维护坐标映射。
我建议顺手再写一个反向解析函数，调试时打印节点信息会非常方便：
int getFloor(int id) { return id / (R * C); } int getRow(int id) { return (id % (R * C)) / C; } int getCol(int id) { return id % C; }这个编号方案还有一个隐藏好处：如果题目要输出路径，我们只用一个数组存前驱节点的编号，最后就能倒推出完整路径，连结构体都不用定义。
2.2 楼层内部的边权怎么定
楼层内部的移动规则相对简单：从当前格子走到上下左右相邻的格子，如果目标格没越界，就可以走。每进入一个格子，背包里的分数就加上该格子的分值，所以边的“代价”本质上就是目标格子的分值。
这里有一个特别容易搞混的约定问题：起点格子的分数要不要计入总得分。我在实践里习惯按“进入一个格子即获得该格子的分值，起点不计算，终点计算”来建模。如果题目待确认，就老老实实把答案加减一个起点分值来对应不同约定。看清楚题目给出的样例和说明，因为很多WA都是一开始约定没对齐导致的。
楼层内的建边代码如下：
int dr[4] = {-1, 1, 0, 0}; int dc[4] = {0, 0, -1, 1}; for (int f = 0; f < L; f++) { for (int r = 0; r < R; r++) { for (int c = 0; c < C; c++) { int u = id(f, r, c); for (int k = 0; k < 4; k++) { int nr = r + dr[k], nc = c + dc[k]; if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue; int v = id(f, nr, nc); g[u].push_back({v, score[f][nr][nc]}); } } } }注意这里我只建了出边，没建反向边。对于求最长路来说，正向边方向就是路径移动方向，反向边是给输出路径用的，后面单独说。
2.3 跨层传送门的边权处理
跨层传送是整个题目的题眼，也是最容易出错的地方。传送门通常出现在特定层级的特定格子，踩上去之后会瞬时传送到另一层楼的某个固定格子。传送的目的是跨越空间，所以这条边的“收益”按题目表述处理，可能是目标格子的分值，也可能另有单独设定。我在本文约定它等于目标格的分值，因为这是最常见也最合逻辑的一种设定。
建边逻辑是当遍历到格子（f, r, c）时，如果它对应着一组传送规则，就把这一组规则解析出来，找到目标楼层tf、目标行tr、目标列tc，然后给编号u的节点添加一条有向边到编号v = id(tf, tr, tc)的节点，边权为score[tf][tr][tc]。
值得多想一步的是传送门的存储方式。UVa题目输入一般会给很多组“传送点”描述，如果你在建模循环时每次都遍历一遍传送表，数据一多就会慢很多。我的做法是先建一个三维数组portal[L][R][C]，值为-1表示没有传送门；如果有传送目标，就存一个targetId。这样在建图时只需要O(1)查询，整体复杂度还是O(L乘R乘C)。
还有一个小细节，传送方向是从本层传到目标层。虽然大多数情况下都是往下层传，但写代码时不要写死方向判断，直接把解析出来的目标节点当作普通节点建边就好。万一题目存在“从低层传向高层”的传送门，只要整张图没有成环，DP依然成立；如果成环了，题目性质就变了，后面我会专门讲。
2.4 用一个不超过三层的微型迷宫手工推一遍
光说理论容易飘，我拿一个极小的例子快速过一遍建图逻辑。假设有2层，每层是2乘2的网格，每格分值随手填一下：
0层：A(1) B(2) / C(3) D(4) 1层：E(5) F(6) / G(7) H(8)
再假设0层的C格是一个传送门，能传到1层的E格。
建图之后大概是这样：
- 0层内部：A可以到B和C；B可以到A和D；C可以到A、D，以及跨层到E；D可以到B和C。
- 1层内部：E到F和G；F到E和H；G到E和H；H到F和G。
- 跨层边：把节点C指向节点E，边权为E的分值5。
从A出发，如果目标是H，一条路径是A -> C（得3分）-> E（得5分）-> G（得7分）-> H（得8分），总得分是23分。另一条路径在0层绕一下可能有不同的分数组合。这已经可以看出模型的意义：我们根本不用关心迷宫图形的样子，只要把图建出来，剩下的问题就是求最长路。
3. 求解算法：DAG最长路DP实战
3.1 建好图后为什么不能直接BFS或Dijkstra
边权有正有负，这是关键。BFS要求所有边权相同，最短路径才成立；Dijkstra要求非负权，因为它的贪心前提是“当前距离最小的节点未来不可能被更小的距离更新”，负权会把这个前提打破。你拿Dijkstra去跑带负权的图，常常会得到次优解，而且样例还不一定能测出来，非常坑。
那SPFA行不行？技术上可行，但没必要。SPFA虽然能处理负权边，但最坏情况下复杂度会退化到O(VE)，在L、R、C都拉满的题目上很容易超时。DAG最长路能用线性DP解决，你不会想用SPFA把可以线性解决的问题写成二次复杂度。
记忆化搜索和拓扑排序DP，本质都是利用“节点之间存在偏序关系”这个性质，让每个节点只被计算一次，从而把指数级的搜索空间压到O(N+E)。这就是DAG动态规划的核心竞争力。
3.2 版本一：记忆化DFS实现
定义dp[u]表示从节点u出发，走到终点能得到的最优分数。注意这里的状态含义是“从当前节点出发”，所以递归边界很自然：如果u已经是终点，直接返回该节点的分值；否则枚举u的所有出边，计算进入下一个节点v之后的最佳分数，再加上跨过去那条边的收益，取最大值。
伪代码如下：
const int NEG = -1e9; int dp[MAXN]; bool vis[MAXN]; int dfs(int u) { if (u == target) return scoreAt(u); if (vis[u]) return dp[u]; vis[u] = true; dp[u] = NEG; for (Edge e : g[u]) { dp[u] = max(dp[u], e.w + dfs(e.to)); } return dp[u]; }这里有几个点需要细节处理。终点节点会优先返回自身分值，而不是试图往外走，这个逻辑必须放在枚举出边之前，否则终点有出边时会被继续递归，绕出环来就全乱了。另外，如果某个节点根本走不到终点，dp[u]会一直是NEG，调用方需要判断这个状态是否合法。
递归深度是一个隐患。多楼层迷宫节点总数可能达到几十万甚至上百万，DFS的递归深度取决于拓扑链长度，当链路很长时，默认系统栈可能会爆。我实际测试过，这一题如果在本地编译器里跑，一般还比较稳；但提交到UVa的在线评测环境，不一定给你开足够的栈空间。所以更保险的版本是写成非递归的拓扑排序DP，这也是我实战里更常用的方案。
3.3 版本二：拓扑排序迭代DP
如果图天然按楼层编号有序，而且所有跨层边都是从低层到高层，那么节点编号本身就可以当拓扑序用。这种情况下，你甚至不需要建拓扑序数组，直接按楼层从高到低或者从低到高遍历一遍就行。
更通用的写法是：建图之后用一个入度数组做标准的Kahn拓扑排序，得到拓扑序列。然后在拓扑序的逆序上做DP，因为拓扑序里的方向是从前向后，而dp[u]依赖u的后续节点v，所以得从后往前推。
代码如下：
vector<int> topo; queue<int> q; int indeg[MAXN]; for (int i = 0; i < N; i++) for (Edge e : g[i]) indeg[e.to]++; for (int i = 0; i < N; i++) if (indeg[i] == 0) q.push(i); while (!q.empty()) { int u = q.front(); q.pop(); topo.push_back(u); for (Edge e : g[u]) if (--indeg[e.to] == 0) q.push(e.to); }需要注意拓扑排序的前提是有向无环。如果图中存在环，Kahn算法会输出少于N的节点数，这就是一个很好的判环信号。拿到拓扑序之后，DP就可以写了。dp[v]表示从终点到v的最优值，换个角度定义也无妨，关键是状态转移要一致。
vector<int> best(N, NEG); best[target] = scoreAt(target); for (int i = (int)topo.size() - 1; i >= 0; i--) { int u = topo[i]; if (best[u] == NEG) continue; for (Edge e : g[u]) { best[e.to] = max(best[e.to], best[u] + e.w); } }这个写法的好处是没有系统栈风险，而且你可以在得到dp的过程中顺便记录前驱节点，一举两得。相比记忆化搜索，我觉得迭代DP在竞赛环境里更“皮实”。
如果题目中的楼层顺序天然可做拓扑序，也可以省去Kahn排序，直接先用一个数组标记传送方向保证无环，然后按楼层降序遍历，比Kahn少一倍的常数时间。
3.4 输出完整路径是加分项
题目不一定要求输出路径，但调试过程中输出路径几乎是必需的。我的办法是维护一个pre数组，对应该节点上一步走的哪个前驱节点。在逆序DP推进时，一旦发现best[e.to]被更新，就直接记录：
pre[e.to] = u;最后从起点开始，沿着pre跳，直到终点，就能还原完整路径。这里要注意起点和终点是否预先定义，如果起点无法到达终点，pre链会在某个环节断掉，输出前需要判断。
输出路径时我还踩过一个坑：如果更新发生在等号右边，也就是出现多个相同最优路径时，题目没有特殊要求，任选一条即可；但如果你用了“大于就更新”，遇到并列情况就会保留第一次找到的路径，行为稳定可复现，调试起来舒服得多。
4. 避坑指南与调试实录
4.1 起点分数到底计不计
这是我在群里看到问得最多的问题之一。不同题目对“走到某格得到分数”的起点处理可能不同。这道题我的建模约定是：起点不算分，每移动到下一个格子时把目标格子的分值累加。但如果你是按“经过每个格子都计分，包括起点”来写的，答案所有的路径表达式里会统一多一个起点分数，差一个常数。提交WA的时候，先检查自己起点处理与题意是否一致，别急着怀疑算法。
我自己调试时用过一招：把起点到终点的几步路径全部打印出来，手动按约定算一遍总分，和程序输出比对，不一致就说明某个边权或者起点计数逻辑出了问题。
4.2 传送成环导致的隐性Bug
虽然题目保证无环，但建模过程中很容易意外引入环。比如同层移动本身就是双向边，如果跨层传送门是双向的，楼层的先决条件就会被破坏。又比如传送门不小心把自己传回原楼层，如果目标格子又连着别的传送门，很容易形成大环。
即使题目说保证无环，我也建议建完图之后跑一次拓扑排序检查节点数量是不是等于N。不是的话，立刻回头查传送门输入解析有没有理解偏。这个检查只有O(N+E)的开销，却能防住最伤脑筋的隐性WA。
4.3 输入格式和EOF处理的坑
UVa的输入风格非常统一，多组case、空洞行、EOF结束。我处理多楼层迷宫输入时踩过的实际问题包括：每层网格数据之间可能有空格，也可能没有空行；传送描述每个case都有不同的条数；case结束以后不一定有明确的结束标记。
推荐的稳定读法是逐行用函数读入，然后逐段解析，不假设某一行必然存在。传送门解析时如果用cin流读，记得每一轮case开始时把所有全局数组重新初始化，特别是edge容器，用vector声明的要clear，不然上一个case的边会残留到下一个case。
我吃到过最痛的一次亏是传入数组用静态数组但忘记重置size，结果导致下一组case在遍历时越界访问，本地环境没炸，交上去就RE。后来我养成了每次case开始先自查所有动态结构清空的习惯。
4.4 负权边和INF设置的方案
DAG最长路里如果所有边权都是正的，初始化负无穷大和初始化0的区别不大；但一旦出现负分格子，节点间的路径可能因为额外绕路而变差，dp的初始值就不能设成0，必须设成一个足够小的数。
用INT_MIN直接做初始值有风险，因为你在做加法时可能溢出Int范围。更稳的做法是用一个自定义常量，比如const int NEG = -1e9;。如果节点数和边权的绝对值加起来也不会超过1e9，这个值就足够安全。这个细节平时写题不觉得，一旦遇到负数极端数据就特别能凸显问题。
4.5 常见错误速查表
我在实战排查时给自己整理过一张速查表，横纵对照一下就能快速定位问题类型。
| 症状 | 可能原因 | 检查方向 |
|---|---|---|
| 样例过但提交WA | 起点分数计入规则不一致 | 重新确认题意 |
| 输出答案明显偏大 | 图中存在环且DP朝错误方向传播 | 跑拓扑排序判环 |
| 答案整体偏小 | dp初始值没设成负无穷 | 检查NEG常量 |
| 答案永远一样 | 传送门边权漏了或者目标格分值没加 | 打印部分路径细节 |
| 本地跑得动、OJ上RE | 静态数组大小或递归爆栈 | 检查数组边界、改用迭代DP |
| 多个case之间互相污染 | 全局数组未清空或vector未clear | case开始前统一reset |
这张表不能保证一次解决所有问题，但每次调试前过一遍，能帮你省下很多重复试错的时间。
5. 跨层迷宫类题目的扩展思路
5.1 如果传送门双向或者同层，解法怎么变
跨层传送门一旦变成双向的，图里就可能出现环。带着正环的图里，最长路没有保守答案，因为你可以在环上反复转圈把分数刷到无限大。这时候DP就不再适用。处理办法通常是问自己题目的本意是不是“最多经过一个传送环”或者有步数限制，否则就要考虑缩点或者换算法思路。
如果只是存在负环，最长路的说法也会变得很微妙。竞赛题很少在这种情况下让你裸跑SPFA求最长路，而是会给一些额外的约束。遇到这种题目，先别急着套模板，看清楚限制条件再动手。
5.2 多楼层思想的通用价值
Multistory Labyrinth这题解答完，我最大的感受是它的骨架可以套用到很多问题里。一个在二维网格上不好处理的问题，通过增加“楼层”这一维度变成三维，再用“单向传送”构造出天然的拓扑顺序，最后统一转化为DAG上的DP——这是一条非常常见且实用的出题套路。
如果你后续遇到类似的“层次图最短/长路”“分层状态DP”问题，比如图论里的分层图最短路、状态机DP、带瞬移节点的BFS，核心思路都是一模一样的。先把空间展开成多层，再把层间转移建模为边，问题就从图论变成了动态规划。
我曾经拿这道题的代码框架去改一个“带飞行道具的网格寻宝题”，只改了边的生成逻辑和状态含义，整体结构几乎没动，最后很快AC。这就是建模抽象带来的复用价值。
5.3 对图论建模的心得
做这类题，最忌讳的就是拿到题目就开始写循环。先花五分钟在纸上把“节点是什么、边有哪些、权怎么算、会不会有环”这四件事想清楚，后面写代码速度快得多，调错的时间也少得多。这道题让我更深刻地体会到，建模能力才是算法竞赛里最核心的能力，数据结构和算法都是为建模服务的工具。
如果你现在刚入门图论DP，不妨找一个小的数据规模用例，手动画出节点和边，然后用程序打印出每个节点的dp值，对照着理解一遍状态转移。这个过程可能有点费时间，但效果比直接刷几十道题都好。
5.4 后续可以继续练的同类题
UVa里还有不少类似的题可以拿来巩固这套思路，比如带层次图最短路的题目、带时间维度的状态DP、带特殊传送点的BFS问题。刷题要有意识地找共同点，别贪多贪快。把一个模型吃透以后，换个场景再遇到时，你大概一眼就能认出它的本质。
我个人比较推荐的做法是：做完13116之后，再找两到三题类似结构的题，用同一套代码框架去改，体会哪些地方是变体、哪些地方是不变的核心。这样比反复刷同类型模板题有效得多。
写在最后
UVa 13116 Multistory Labyrinth这道题，表面是迷宫，内里是DAG最长路，中间隔着一层建模的窗户纸。捅破这层纸之后，你会发现它并不难，难的是在考场或者比赛状态下冷静地完成建图、定权、判环这一整套动作。建议你把我上面那段代码自己敲一遍，跑过样例，再试试不打印路径的情况下能不能一遍写对。这种手感只能靠实操磨出来，光看题解记不住太久。我自己的经验是，把这题啃透以后再遇到层状图相关的题目，思路会顺畅非常多。
的五个步骤)
