图 1：本文封面，图被复制成 k+1 层，层数就是预算。
先说明属性：这是一篇历史笔试题复盘，题目出自本地历史笔试资料，与任何公司的当前招聘无关。题面：一个王国有 n 座城市，编号 0 到 n-1，任意两城之间都有一条魔法通道，通过要花给定的时间。你站在 0 号城，想去 1 号城；手里有一把魔力扫把，在一条通道上飞行可以让这条通道的时间减半，但扫把最多只能用 k 次。问最少需要多少时间，答案保留一位小数。
第一直觉为什么错：只知道「在哪个城市」不够做决定。
普通最短路里，状态就是「站在哪个城市」——同城的到达代价确定了，后面怎么走与历史无关。加了扫把之后这个性质被打破：同样站在 3 号城，「还剩 2 次券」和「券已用光」是两种完全不同的局面，前者的未来选择明显更多。只记录城市维度的距离，等于把两种局面错误地合并了。补救办法是把剩余预算也编码进状态：状态从「城市」扩成二元组「（城市，已用券数）」，已用次数有 0 到 k 共 k+1 种取值，相当于把原图复制成 k+1 层。
建图：每一步要么平移，要么下降。
在分层图上，每条原边变成两种边：不用券的边留在同层，连接同层的邻居城市，权值不变；用券的边连向下一层的对应城市，权值减半。走一条普通边是层内平移，用一次券是下降一层，层数就是用掉的预算——降到第 k 层后，向下的边不存在了，券自然用不出第 k+1 次，约束被图结构本身消化掉。在这张新图上跑标准 Dijkstra，最后取目标城市在所有层上距离的最小值（不要求把券恰好用完，用几张都行）。
把模型写成代码。
下面这份实现包含分层图 Dijkstra，以及 k=1 时枚举「哪条边被半价」的对拍真值，用 Node.js 22.15.0 直接运行（node magiccity.js）：
'use strict';
// 状态 = (城市, 已用券数)；不用券的边留在同层，用券的边连向下一层、权值减半。
function dijkstraLayered(n, k, dis) {
const layers = k + 1;
const V = n * layers;
const dist = new Array(V).fill(Infinity);
const idx = (city, used) => used * n + city;
dist[idx(0, 0)] = 0;
const done = new Array(V).fill(false);
for (let iter = 0; iter < V; iter++) {
let u = -1; // 朴素 O(V^2) 取最小未确定节点
for (let i = 0; i < V; i++) if (!done[i] && (u === -1 || dist[i] < dist[u])) u = i;
if (u === -1 || dist[u] === Infinity) break;
done[u] = true;
const city = u % n, used = Math.floor(u / n);
for (let v = 0; v < n; v++) {
if (v === city) continue;
const w = Number(dis[city][v]);
if (dist[u] + w < dist[idx(v, used)]) dist[idx(v, used)] = dist[u] + w; // 不用券：同层平移
if (used < k && dist[u] + w / 2 < dist[idx(v, used + 1)]) dist[idx(v, used + 1)] = dist[u] + w / 2; // 用券：下降一层
}
}
let ans = Infinity;
for (let used = 0; used <= k; used++) ans = Math.min(ans, dist[idx(1, used)]);
return ans;
}
// 对拍真值：k=1 时枚举「哪条无向边被半价」，逐个减半后跑普通最短路取最小
function bruteForceK1(n, dis) {
let best = dijkstraLayered(n, 0, dis);
for (let a = 0; a < n; a++) for (let b = a + 1; b < n; b++) {
const halved = dis.map((row, i) => row.map((w, j) => ((i === a && j === b) || (i === b && j === a)) ? w / 2 : w));
best = Math.min(best, dijkstraLayered(n, 0, halved));
}
return best;
}
const dis4 = [
[0, 9, 3, 6],
[9, 0, 4, 2],
[3, 4, 0, 5],
[6, 2, 5, 0],
];
console.log(`n=4 不用券：${dijkstraLayered(4, 0, dis4).toFixed(1)}`);
console.log(`n=4 k=1 分层图：${dijkstraLayered(4, 1, dis4).toFixed(1)}`);
console.log(`n=4 k=1 枚举对拍：${bruteForceK1(4, dis4).toFixed(1)}`);
console.log(`n=4 k=2 分层图：${dijkstraLayered(4, 2, dis4).toFixed(1)}`);
let seed = 42; // 规模演示与随机对拍
const rand = () => (seed = (seed * 1103515245 + 12345) % 2147483648) / 2147483648;
const n = 8, dis8 = Array.from({ length: n }, (_, i) =>
Array.from({ length: n }, (_, j) => (i === j ? 0 : 1 + Math.floor(rand() * 9))));
for (let i = 0; i < n; i++) for (let j = 0; j < n; j++) dis8[j][i] = dis8[i][j];
console.log(`n=8 k=0：${dijkstraLayered(n, 0, dis8).toFixed(1)}，k=3：${dijkstraLayered(n, 3, dis8).toFixed(1)}`);
let ok = true, checked = 0;
for (let t = 0; t < 20; t++) {
const m = 5, g = Array.from({ length: m }, (_, i) =>
Array.from({ length: m }, (_, j) => (i === j ? 0 : 1 + Math.floor(rand() * 9))));
for (let i = 0; i < m; i++) for (let j = 0; j < m; j++) g[j][i] = g[i][j];
checked++;
if (dijkstraLayered(m, 1, g) !== bruteForceK1(m, g)) { ok = false; console.log('不一致:', t); }
}
console.log(`随机对拍 ${checked} 组（n=5, k=1）：分层图与枚举${ok ? '完全一致' : '存在分歧'}`);
实测输出：
n=4 不用券：7.0
n=4 k=1 分层图：4.5
n=4 k=1 枚举对拍：4.5
n=4 k=2 分层图：3.5
n=8 k=0：6.0，k=3：3.0
随机对拍 20 组（n=5, k=1）：分层图与枚举完全一致
看四城的例子：不用券时 0 经 2 到 1 是最优，3+4=7；k=1 时把 0 到 1 的直达边（9）半价成 4.5 直接飞过去最划算；k=2 时再半价 0 到 2 的边（3 变 1.5），走 1.5+2=3.5。20 组随机图对拍里，分层图答案与「枚举哪条边半价」的暴力真值一一吻合，说明状态扩展没有漏掉任何局面。
图 2：把隐式的资源约束变成显式的坐标维度。
可能的追问。
「复杂度多少？」节点数乘 k+1、边数大约翻倍再乘 k+1，整体约为原图 Dijkstra 的 k 倍，O(k·E·log(k·V))。「为什么取各层最小值而不是只看第 k 层？」券是「最多 k 次」不是「恰好 k 次」，少用的局面散落在中间层，都要参选。「权值减半出现小数怎么办？」答案本身允许实数，题目要求保留一位小数，用浮点跑 Dijkstra 即可，本文实测输出就是这么来的。
分层图的价值不止这一道题：凡是「带资源预算的最优路径」——限定换乘次数的通勤规划、限定重试次数内完成调度的成本最优——都是同一招：把预算编码进状态维度，让约束变成坐标。回到笔试现场，建议节奏：先点破「同城不同局面」所以状态必须带上剩余次数，再讲两种边的建图规则，最后补一句复杂度与「各层取最小」的收尾细节。你第一次见这类「带次数预算」的最短路时，是想到分层图，还是先写了带状态的 DFS？欢迎聊聊。