题目解析
本道题目包含多个子问题，如果不加以梳理，会非常复杂，并且在梳理完毕后依然编写大量代码，并且需要特别注意实现细节，非常考验「力量」（毅力）,「智慧」与「勇气」。
预处理
由于要求必须击败所有的「波克布林」，且从地下 iii 层传送至地下 i+1i + 1i+1 层须花费 111 秒的时间，所以我们可以把击败波克布林需要的时间和传送的时间预处理，后面就可以把所有的「波克布林」当成同一种去处理；把此部分花费的时间记为 cost\tt{cost}cost。
把所有的波克布林当成「特殊点」，并将其在地图中标记为 *，接下来都可以把问题转化成：访问 KKK 层地图上的所有特殊点需要最短时间，将其标记为 mint\tt{mint}mint。
那么本题的答案为 cost+mint\tt{cost + mint}cost+mint。
接下来解决如何计算 mint\tt{mint}mint 的问题。
因为计算 mint\tt{mint}mint 比较复杂，我们可以将其划分成若干个子问题。
第一层的初始化
对于除第一层以外的其他层，我们都可使用一样的方法进行转移，而第一层的起点固定为 (1,1)(1, 1)(1,1)，所以需要将第一层进行初始化，从 (1,1)(1, 1)(1,1) 处执行 BFSBFSBFS，得出从第一层 (1,1)(1, 1)(1,1) 处到达其他点的最短距离 dist\tt{dist}dist。
每一层的子问题
通过观察可以发现，每一次要解决的是相同的子问题，我们把每一层需要解决的问题分为以下 555 步：
1. 由于得到的是上一层到达每个点的最短时间，但是在本层，这些地方有可能存在障碍物或者「波克布林」，所以需要将这些点的最短时间置为 ∞\infty∞，得出处理后的 dist1\tt{dist_1}dist1 。
2. 在 dist1\tt{dist_1}dist1 的基础上，求出到达当层地图每个「波克布林」的位置所需要的最短时间 dist2\tt{dist_2}dist2 。
3. 在 dist2\tt{dist_2}dist2 的基础上，求出从击败当层的所有「波克布林」，并停留在任意一只「波克布林」所在的位置上需要的最短时间 dist3\tt{dist_3}dist3 。
4. 在 dist3\tt{dist_3}dist3 的基础上，将当层没有「波克布林」的位置重置为 ∞\infty∞，得到 dist4\tt{dist_4}dist4 。
5. 在 dist4\tt{dist_4}dist4 的基础上，求出从击败当层所有「波克布林」后到达每个点需要的最短时间。
对于第 111 步和第 444 步比较容易实现，在此不再赘述。
对于第 222 步和第 555 步要解决的均为 「多源不同权的无权最短路问题」，可以使用解决 A29348.花火大会 的方法解决，但本题的地图比较小，所以对于这个子问题可以直接使用「优先队列 BFSBFSBFS」解决。
对于第 333 步，要解决的是一个「哈密顿路径」问题，可以使用「状态压缩DP」解决。
状压DP 求解第 333 步
首先我们需要把该层上所有「波克布林」找出并存储到 boko 中。
然后需要求解任意两个「波克布林」之间的最短路。这一步可以从每个波克布林的位置执行 BFSBFSBFS
得出。
令 f[i][j]\tt{f[i][j]}f[i][j] 为该层编号为 iii 的「波克布林」和编号为 jjj 的「波克布林」之间的距离。
令 dp[i][j]\tt{dp[i][j]}dp[i][j] 表示为访问过的「波克布林」的集合为 iii（二进制表示集合法） 时停在 jjj 号「波克布林」处的最短时间。
那么转移方式为：dp[i][j]=min(dp[i][j],dp[subi][k]+f[k][j])\tt{dp[i][j] = \min(dp[i][j], dp[sub_i][k] + f[k][j])}dp[i][j]=min(dp[i][j],dp[subi ][k]+f[k][j])。
其中 subisub_isubi 表示 iii 的包含 kkk 但不包含 jjj 的子集。kkk 表示其他「波克布林」的编号。
此步完成后，我们便求出了击败当层所有的「波克布林」，并停留在任意一只「波克布里」处所需要的最短时间。
统计答案
将所有层全部处理完毕后，我们直接从处理完毕的 dist\tt{dist}dist 中取最小值，即为最终的答案。
时间复杂度分析
1. 使用BFS预处理第一层的时间复杂度为 O(NM)\mathrm{O}(NM)O(NM)；
2. 解决每层子问题的第 111 步和第 444 步的时间复杂度为 O(NM)\mathrm{O}(NM)O(NM)；
3. 解决每层子问题的第 222 步和第 555 步的时间复杂度为 O(NMlogNM)\mathrm{O}(NM\log{NM})O(NMlogNM) 或 O(NM)\mathrm{O}(NM)O(NM)；
4. 解决每层子问题的第 333 步，求出任意两个「波克布林」之间的距离复杂度为 O(XiNM)\mathrm{O}(X_iNM)O(Xi NM)；「状压DP」求击败当层所有「波克布林」并停留在任意一个「波克布林」处的时间复杂度为 O(Xi2⋅2Xi)\mathrm{O}({X_i}^2 \cdot 2^{X_i})O(Xi 2⋅2Xi )。
总的时间复杂度为 O(K⋅(XiNM+Xi2⋅2Xi))\mathrm{O}(K \cdot (X_iNM + {X_i}^2 \cdot 2^{X_i}))O(K⋅(Xi NM+Xi 2⋅2Xi ))。
AC代码
