题目
LC 1928 规定时间内到达终点的最小花费：有
n 个城市（编号
0 .. n-1）。
edges[i] = [x, y, time] 是一条
无向边，边上只有
时间、
没有花费。另有
passingFees[v]：
每经过一座城市付一次该城市的通行费 ——
起点与终点也要付。求从
0 走到
n-1，在总时间
≤ maxTime 的前提下
最少要付多少通行费；走不到返回
-1。
输入: edges = [[0,1,10],[1,2,10],[2,5,10],[0,3,1],[3,4,10],[4,5,15]]
passingFees = [5,1,2,20,20,3]
maxTime = 30 → 11 （0 → 1 → 2 → 5：耗时 10+10+10 = 30，费 5+1+2+3 = 11）
maxTime = 29 → 48 （0 → 3 → 4 → 5：耗时 1+10+15 = 26，费 5+20+20+3 = 48）
maxTime = 25 → -1 （最快的一条路也要 26 分钟，25 分钟内根本到不了）
它看上去就是"最短路"，真正的门槛却在一处非常反直觉的地方：
通往终点有两条路 —— 一条费 11、一条费 48，差的不是"哪条便宜"，而是"来不来得及"。maxTime 只差 1 分钟（30 与 29），答案就从 11 跳到 48。这一跳就是本文的全部戏肉：为什么一维的
dp[v] 一定会算错，以及怎么用一张
分层图（官方提示）把它救回来。
一、核心洞察：dp 定义与状态转移
先说那个
错的写法：跑一次最短路，
dp[v] = 从 0 走到
v 的最少花费（边权 = 到达城市的通行费）。它对不对？看官方示例：
dp[5] = 11，可这条路要
30 分钟，在
maxTime = 29 时
根本不允许。一维写法把"它是第几时刻到的"整个丢掉了，于是
把一条超时的便宜路错当成了答案。
修法只有一句：
把时间并进状态。
不问"到某城最少花多少"，而问"在某个确定的时刻到达某城，最少花多少"。
于是定义：
dp[t][v] = 恰好在时刻 t 到达城市 v 的最小通行费；dp[0][0] = passingFees[0] —— 起点也要付自己的通行费，这是唯一的底座；- 其余全部是
∞（还没到过）；
- 按
t 正序逐层向外松弛每一条边：
dp[t][v] = 恰好在时刻 t 到达城市 v 的最小通行费
dp[0][0] = passingFees[0] （起点也要付）
dp[t + et][u] = min( dp[t + et][u], dp[t][v] + passingFees[u] )
答案 = min over t ≤ maxTime of dp[t][n-1]
语义是：
已经知道"t 时刻在 v、花了多少"，再走一步（耗时 et）到 u，就多付一笔 u 的通行费。等算
dp[t + et] 这一层时，用到的
dp[t]（更早的层）早就写好了 —— 这正是"按时刻正序推进"的含义。
def minCost(maxTime, edges, passingFees):
n = len(passingFees)
INF = float("inf")
dp = [[INF] * n for _ in range(maxTime + 1)]
dp[0][0] = passingFees[0] # 起点也要付自己的费
for t in range(maxTime + 1):
for x, y, et in edges: # 无向边，两个方向都要试
arr = t + et
if arr > maxTime: # 迟到就是迟到，剪掉
continue
if dp[t][x] < INF:
dp[arr][y] = min(dp[arr][y], dp[t][x] + passingFees[y])
if dp[t][y] < INF:
dp[arr][x] = min(dp[arr][x], dp[t][y] + passingFees[x])
ans = min(dp[t][n - 1] for t in range(maxTime + 1))
return -1 if ans == INF else ans
三个细节决定了成败：
dp[0][0] 是 passingFees[0] 而不是 0：起点也算"经过"，漏掉它答案会少一笔。同理，终点那笔 passingFees[n-1] 也在松弛里收。- 只从"已到达"的格子出发：
dp[t][v] 还是 ∞ 的格子产不出一条有效转移。这是"分层图一层层向外扩散"的本意，也顺手避开了 ∞ + fee 的溢出。
arr = t + et > maxTime 的松弛直接剪掉：时间只能往前走、不会回头，迟到就是迟到。它们不进入后续任何层。
还有一处最容易漏：
答案不在 dp[0][n-1]，而是 min over t ≤ maxTime of dp[t][n-1]。到达终点不必恰好用满
maxTime —— "早到"和"晚到"是两组独立的格子，最后要在所有时刻上取最小。
二、为什么时刻必须进状态
这一格是整个算法的地基，值得单独说清。
dp[v]（一维）回答的是"到城市
v 最少花多少"。它把
两个本来不同的事实塌缩成了一个数：
- 便宜但慢：
0 → 1 → 2 → 5，费 11，耗时 30；
- 贵但快：
0 → 3 → 4 → 5，费 48，耗时 26。
只记花费的那一维会把第一条记下来（
dp[5] = 11），却
忘了它已经超时。而"时间"这件事
不能被压缩、也不等价于花费：花 11 的代价是 30 分钟，花 48 的代价是 26 分钟 —— 两种付出各换各的，没有谁支配谁。于是两个都要留在状态里，这就是
官方提示的"分层图"：
把每一层 t 画成一排城市 0..n-1：
层 t 的城市 v ← 一条时间 et 的边 → 层 t+et 的城市 u
点 = (t, v) 边 = (x, y, time)
dp[t][v] = 到点 (t, v) 的最短路（边权 = 到达城市的通行费）
maxTime 就是这张图的
层数上限。所谓"带时间窗的最短路径"，就是"层数有上限的最短路"。
反看两个"差点踩到"的写法：
# 【LC 1928】规定时间内到达终点的最小花费：分层图上的 dp
# 错法一：一维 dp[v]。maxTime = 29 时它会返回 11 —— 但那条路耗时 30，超时
dp = [INF] * n
# 错法二：答案取 dp[maxTime][n - 1]。默认题面里 dp[5][5] = 71，
# 但真正的最小是 48（在 t = 3）—— 越晚到反而越贵
ans = dp[maxTime][n - 1]
第二条错法还有个耐人寻味的细节：同一座终点，
晚到反而更贵（
dp[5][5] = 71 > dp[3][5] = 48）。因为每一步都在付目的地城市的费，"多绕一站"未必便宜。
min over t 把这件事一次性处理干净，不必对"早到更便宜"抱任何假设。
一句话记住这题的骨架：
dp[0][0] = fees[0] 是唯一的底座，dp[t+et][u] = min( .. , dp[t][v] + fees[u] ) 是唯一的转移，层数上限 maxTime 是唯一的剪枝，答案在 min over t 上。
三、动画怎么看
动画一（
algo-viz--lc1928）：一张
分层图表格 ——
行 = 时刻 t（0 到 maxTime）、列 = 城市 v，格 = dp[t][v]。行头右对齐写
t = k，列头写
城市 v 加一行
费 f，终点那一列垫了一条浅色竖带。没到达的格子是
虚线框 + 灰 ∞，已到达的是绿底实值，底座
(0,0) 描金框。每帧一条 relax：
源格 (t, v) 描重橙框，目标格 (t+et, u) 描框（刷新成功 = 实金框，没改进 = 橙虚线框），一条虚线箭头从源格底边拉到目标格顶边；一枚金环跟着
当前最优格 dp[bestT][target] 走。下方是转移横幅，写出
dp[arr][u] = min( dp[arr][u] , dp[t][v] + fees[u] ) 的现场取值，再接一个五项统计面板（
t /
v → u /
from → cand /
已剪枝 /
答案）。done 帧把回溯出的最优状态链整条点亮。
盯住三件事：
只有"已到达"的格子才会发一帧（
dp[t][v] 还是
∞ 的格子根本不产生转移）；
arr > maxTime 的松弛不发帧，只在"已剪枝"计数里悄悄涨（默认题面涨到 11）；以及
没改进的松弛会被点名 —— "这一趟更晚也更贵，作废"。答案那格最后不在第 0 行，而在
min over t 取到的那一格。
动画二（
algo-viz--lc1928path）：同一张图、两条路的
现场对照。底图按"从城市 0 做一次 BFS 定层"排布 —— 默认那张图刚好是
col0 = {0}、
col1 = {1,3}、
col2 = {2,4}、
col3 = {5}，每条边标着耗时。两条高亮路叠上去：
橙色 = 只图便宜（不看时间，最便宜的城市序列），
绿色 = 守时间窗的最优（在
maxTime 内最省的那条）。左边一张卡写"只图便宜 · 不看时间"、右边一张写"守时间窗 · 最优"，卡里是
城市序列 · 费 X · Y分，右上角给判定（
超时 6 > 5 /
来得及 /
最优）。下方一排 chip 是
状态链（
t = k 与
城市 v）：
best 帧之后逐帧沿
前驱表从终点状态往回退，cursor 一格一格递减，已揭开的 chip 染绿、当前那格描金框 —— 路就是这么被还原出来的。
两个动画分工明确：动画一
填表（把
(t, v) 一层层算出来），动画二
对照 + 回溯（先看"便宜路"会超时多少，再从最优状态沿前驱退回起点）。
四、完整推演表
动画一：为了让表能一页放下，用一份
缩水题面（数值自拟，结构与官方示例完全相同）：
passingFees = [5, 1, 2, 20, 20, 3]edges = [[0,1,2], [1,2,2], [2,5,2], [0,3,1], [3,4,1], [4,5,1]] —— 便宜那条 0-1-2-5 每段耗时 2，昂贵那条 0-3-4-5 每段耗时 1；maxTime = 5。
于是"只图便宜"的路费 11、耗时 6（超时 1 分钟），而"守时"的路费 48、耗时 3 —— 与官方示例同款的冲突，只是数字小到能摆进表里。
t = 5 这一层还剩
dp[5][2] = 50、
dp[5][3] = 31、
dp[5][5] = 71 三个已达的格子，但它们再往外走
arr 会到 6 或 7，全部
> maxTime = 5 → 被时间窗剪掉。这些"不发帧"的松弛正是统计面板里
已剪枝 = 11 的来源。
最终 dp 表（
∞ 表示该时刻到不了）：
答案 = min over t ≤ 5 of dp[t][5] = min(∞, ∞, ∞, 48, ∞, 71) = 48，取到它的时刻
bestT = 3。注意
dp[5][5] = 71 > 48：
晚一点到反而更贵，这就是"答案必须在所有
t 上取最小"的原因。
顺前驱表回溯：
dp[3][5] = 48 ← dp[2][4] = 45 ← dp[1][3] = 25 ← dp[0][0] = 5，得到城市序列
0 → 3 → 4 → 5（耗时
1+1+1 = 3，费
5+20+20+3 = 48）—— 正是"贵但快"的那条。
动画二：同一组数据，看两条路怎么现场分高下。
"只图便宜"跑的是
边权 = 到达城市通行费的 Dijkstra，得费 11，再回头算它要花 6 分钟 —— 一拍两瞪眼：
6 > 5，作废。而守时间窗的那条费 48，却只用 3 分钟。
cheap.fee (11) ≤ best.fee (48) 这件事是必然的：
无视时间窗等于把搜索空间放大，其最优值只会更小或相等 —— 便宜是一回事，来得及是另一回事。
再沿前驱表把最优链一格一格揭开（动画二的
back 帧）：
路
不在 dp 的数值里，而藏在
prev[arr][u] = (t, v)：反复问"我是从哪个状态来的"，就退回到
(0, 0)。
五、同族题：787 / 743 / 1631 / 1514 / 1976
1928 的骨架是"
状态维 × 时间维"的 DP —— 等价于
分层图最短路。同一副骨架换个问法，就是一条完整的题链：
- LC 787 K 站中转内最便宜的航班：状态是
(已用中转数 k, 城市 v)，"最多 K 次中转"就是"最多 K+1 条边"，与 maxTime 逐字同构 —— 把"时间"换成"中转次数"、把"每城付费"换成"每条边有机票价"，两题骨架一模一样。最经典的同族。
- LC 743 网络延迟时间：单源最短路，但没有时间窗这个约束，答案是最晚被收到的那个时刻。1928 加上时间窗之后，就变成"路径长度（时间）还受一个上限"。
- LC 1631 最小体力消耗路径：路径代价是"沿途最大高度差"，不是求和 —— 换的是代价的聚合方式（
max 而非 +）。
- LC 1514 概率最大的路径：聚合是乘积，且方向是最大化（换成对数就又是求和最短路）。
- LC 1976 到达目的地的方案数：同样一张时间分层图，但问方案数，转移从
min 换成 +。
把它们排成一列看：
"层"是时间 / 中转数 / 步数，"点"是城市 / 状态；边权可能是耗时、票价、高度差；聚合可能是 min、max、乘积或计数；而"窗"就是层数的上限。 1928 只是这条坐标轴上的一个点。
六、Java 版
class Solution {
// LC 1928 标准解：分层图 DP —— 与推演表逐帧一致
public int minCost(int maxTime, int[][] edges, int[] passingFees) {
int n = passingFees.length;
final int INF = Integer.MAX_VALUE / 2; // 别用 MAX_VALUE，免得加法溢出
int[][] dp = new int[maxTime + 1][n];
for (int[] row : dp) Arrays.fill(row, INF);
dp[0][0] = passingFees[0]; // 底座：起点也要付自己的费
for (int t = 0; t <= maxTime; t++) {
for (int[] e : edges) {
int x = e[0], y = e[1], et = e[2];
int arr = t + et;
if (arr > maxTime) continue; // 迟到就是迟到，剪掉
if (dp[t][x] < INF) dp[arr][y] = Math.min(dp[arr][y], dp[t][x] + passingFees[y]);
if (dp[t][y] < INF) dp[arr][x] = Math.min(dp[arr][x], dp[t][y] + passingFees[x]);
}
}
int ans = INF;
for (int t = 0; t <= maxTime; t++) ans = Math.min(ans, dp[t][n - 1]);
return ans >= INF ? -1 : ans; // 时间窗内到不了 → -1
}
}
class Solution {
// LC 1928 的另一种视角：状态 (花费, 已用时间, 城市) 上跑小顶堆 Dijkstra
// 第一次弹出终点，那笔花费就是答案 —— 与分层图 DP 等价，还能提前终止
public int minCost(int maxTime, int[][] edges, int[] passingFees) {
int n = passingFees.length;
List<int[]>[] g = new List[n];
for (int i = 0; i < n; i++) g[i] = new ArrayList<>();
for (int[] e : edges) {
g[e[0]].add(new int[]{e[1], e[2]}); // 无向边：两个方向都加
g[e[1]].add(new int[]{e[0], e[2]});
}
int[][] best = new int[n][maxTime + 1]; // best[v][t]：花 t 时间到 v 的最小花费
for (int[] row : best) Arrays.fill(row, Integer.MAX_VALUE);
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
best[0][0] = passingFees[0];
pq.offer(new int[]{passingFees[0], 0, 0}); // {花费, 已用时间, 城市}
while (!pq.isEmpty()) {
int[] cur = pq.poll();
int cost = cur[0], t = cur[1], v = cur[2];
if (v == n - 1) return cost; // 首次弹出终点 = 最小花费
if (cost > best[v][t]) continue; // 过期条目，跳过
for (int[] nb : g[v]) {
int nt = t + nb[1];
if (nt > maxTime) continue; // 超过时间窗的边不扩
int nc = cost + passingFees[nb[0]];
if (nc < best[nb[0]][nt]) {
best[nb[0]][nt] = nc;
pq.offer(new int[]{nc, nt, nb[0]});
}
}
}
return -1;
}
}
class Solution {
// 动画二的骨架：除了花费，再记一张前驱表，把最优路还原出来
public List<Integer> minCostPath(int maxTime, int[][] edges, int[] passingFees) {
int n = passingFees.length;
final int INF = Integer.MAX_VALUE / 2;
int[][] dp = new int[maxTime + 1][n];
int[][] prevT = new int[maxTime + 1][n]; // 前驱时刻
int[][] prevV = new int[maxTime + 1][n]; // 前驱城市
for (int[] row : dp) Arrays.fill(row, INF);
for (int[] row : prevT) Arrays.fill(row, -1);
dp[0][0] = passingFees[0];
for (int t = 0; t <= maxTime; t++) {
for (int[] e : edges) {
int x = e[0], y = e[1], et = e[2];
int arr = t + et;
if (arr > maxTime) continue;
if (dp[t][x] < INF && dp[t][x] + passingFees[y] < dp[arr][y]) {
dp[arr][y] = dp[t][x] + passingFees[y];
prevT[arr][y] = t; prevV[arr][y] = x;
}
if (dp[t][y] < INF && dp[t][y] + passingFees[x] < dp[arr][x]) {
dp[arr][x] = dp[t][y] + passingFees[x];
prevT[arr][x] = t; prevV[arr][x] = y;
}
}
}
int bestT = -1;
for (int t = 0; t <= maxTime; t++) {
if (dp[t][n - 1] < INF && (bestT == -1 || dp[t][n - 1] < dp[bestT][n - 1])) bestT = t;
}
if (bestT == -1) return new ArrayList<>(); // 时间窗内无路
LinkedList<Integer> path = new LinkedList<>();
int t = bestT, v = n - 1;
while (v != -1) { // 沿前驱一路退回 (0,0)
path.addFirst(v);
int pt = prevT[t][v], pv = prevV[t][v];
t = pt; v = pv;
}
return path; // 默认题面：0 → 3 → 4 → 5
}
}
第二个写法值得单独记一笔：
把 (时刻, 城市) 当作图上的点，每条边把 (t, x) 连到 (t+et, y)，问题就是"从
(0,0) 走到某个
(t, n-1)（
t ≤ maxTime）的最短路，代价在到达点上"。这和 787「K 站中转内最便宜的航班」是同一台机器 —— 那里堆里的是
(票价, 中转数, 城市)。
七、边界情况
- 不可达 →
-1：不是"最贵"，是"无解"。官方示例三 maxTime = 25 < 26（最快路的耗时）直接返回 -1。
maxTime 小于最短路耗时：无论多贵都没用，一律 -1。时间窗是硬约束，不是惩罚项。maxTime 大过一切可能耗时：约束失效，退化成"纯按费用最短路"，此时一维写法才碰巧正确。- 起点也要付
fees[0]：漏了它答案会少一笔；终点也要付 fees[n-1]，同理。
- 无向边：
edges[i] = [x, y, time] 两个方向都要松弛，只加一个方向是最常见的静默错误。
- 重边：约束允许
(x, y) 出现多次（不同 time）。同一对城市之间应取耗时最小的那条，多出来的那些不会用上。
- 无自环：约束保证
x ≠ y，所以不必担心原地打转；但也意味着每一步必然推进时间，不会出现"零耗时"平层。
n = 2：只有一条边，答案就是 fees[0] + fees[1]（若 et ≤ maxTime），否则 -1。passingFees[v] 恒正：这意味着多绕一站一定多花钱，不存在"绕路省钱"的负权情形，Dijkstra 的贪心成立。
八、复杂度
n 是城市数、
E = edges.length、
maxTime 是时间上限。DP 的
O(maxTime × E) 来自"每一层（共
maxTime + 1 层）× 每条边都被松弛一次"；空间要存整张
dp 表，因为边的耗时不同，更新会落到
任意未来的层上，无法只留一层。按约束（
maxTime ≤ 1000、
n ≤ 1000、
E ≤ 1000）总规模约
10^6，绰绰有余。
九、常见坑
- 用一维
dp[v]：只记花费、丢掉"第几时刻到的"，会把超时的便宜路错当答案。本题的头号坑 —— 官方示例里 maxTime 只差 1 分钟，答案就从 11 跳到 48。
- 答案取
dp[maxTime][n-1]：到达终点不必用满时间。默认题面里 dp[5][5] = 71，但答案是 dp[3][5] = 48 —— 晚到反而更贵。必须 min over t ≤ maxTime。
- 忘了起点/终点也要付
passingFees：起点那笔在底座里，终点那笔在每次松弛的 + passingFees[u] 里。漏任何一笔答案都不对。
- 从
∞ 的格子出发做松弛：会算出 ∞ + fee，用 int 还可能溢出成负数。先判 dp[t][v] < INF 再松弛。
- 不剪超时的边：
arr = t + et > maxTime 的松弛必须丢掉 —— 时间不回头，迟到就是迟到。
- 无向边只加一个方向：
edges[i] = [x, y, time] 两个方向都要试，只加一边会漏解。
INF 取 Integer.MAX_VALUE：INF + fee 直接溢出。取 MAX_VALUE / 2，或末判 ans >= INF。- 误以为"早到一定比晚到便宜"：不成立（默认题面里
dp[5][5] > dp[3][5]）。好在 dp 表把同一城市的每个时刻各存一份，不依赖这条假设。
- 重边只留了耗时最大的那条：应取耗时最小的；否则会白白把某些可达路判成超时。
十、面试怎么答
第一段 · 定义与转移：
dp[t][v] =
恰好在时刻 t 到达城市
v 的最小通行费，
dp[0][0] = passingFees[0]、其余
∞，
dp[t+et][u] = min( dp[t+et][u], dp[t][v] + passingFees[u] )，
t 正序推进，答案
= min over t ≤ maxTime of dp[t][n-1]。
开头就要说清"为什么必须是二维" —— 时间不可压缩，一维
dp[v] 会把超时的便宜路错当答案。
第二段 · 三处剪枝与底座：只从"已到达"的格子出发（避开
∞ 与溢出）；
arr > maxTime 的边直接剪；起点与终点都要付自己的通行费。这三条
决定了答案对不对，比把代码写快更重要。
第三段 · 换个视角：小顶堆 Dijkstra，状态是
(花费, 已用时间, 城市)，按花费出堆，
第一次弹出终点即答案 —— 与分层图 DP 等价，且能提前终止。这正是 787「K 站中转内最便宜的航班」的同款机器（那里状态是
(票价, 中转数, 城市)）。
追问连跳：
- 把"时间上限"换成"
中转次数上限" → LC 787，逐字同构；
-
去掉时间窗、只要最短路 → LC 743；
- 代价从"求和"换成"
取最大" → LC 1631；换成"
乘积最大" → LC 1514；
- 问
方案数 → LC 1976，把
min 换成
+。
一句话收尾："1928 只有一台机器 —— 一张
分层图，时间当层、城市当点，
dp[t][v] = 恰在 t 到 v 的最少花费；把时间窗当剪枝、把
min 套在最外层。所谓'带时间窗的路径规划'，就是'
层数有上限的最短路'。"
结语
1928 的全部难度浓缩在一个反直觉上：
时间不能被压缩。一维的
dp[v] 把"第几时刻到达"丢掉了，于是"便宜但慢"的路会被错记成答案 —— 官方示例里
maxTime 只差 1 分钟（30 与 29），答案就从 11 跳到 48。把时刻并进状态、摊成一张
分层图之后，一切都变成一次普通的逐层松弛；剩下的两条提醒是：
起点和终点都要付费，以及
答案要在所有 t 上取最小 —— 因为"晚到"可能更贵。
从
(0,0) 一步一步扩散到
(bestT, n-1)，再从终点沿前驱退回起点 —— 这就是带时间窗的路径规划的全部。
下一篇见。