企业官网建设流程全解析

刷算法题的人应该都见过这么一类题目：给一张带权图，限制一个资源上限，让你在满足限制的前提下求另一个指标的最值。LeetCode 1928 这道「规定时间内到达终点的最小花费」就是非常典型的代表，它把图论的路径搜索和动态规划的时间维度状态合并在一起，既考验你对状态定义的理解，也考验代码实现时对边界的敏感度。我刷这道题的时候卡了两次，一次是初始化没想清楚，一次是双向边拆开之后漏了对反向路径的处理，后面把 DP 状态一理顺，发现整个题其实非常清爽。

这篇文章会把这道题的完整思路、状态设计、递推公式、代码实现、复杂度分析全部拆开讲，还会把我实际踩过的坑和网上常有人问的细节一并整理出来。适合三类读者：正在准备算法面试、刷 DP 和最短路径变种题的选手；学动态规划但总是想不明白为什么用时间维度 + 城市维度建状态的初学者；以及想快速看懂题解、不想被各种混淆写法绕晕的备赛党。

1. 题目到底在问什么：图上的双约束优化

1.1 题意还原与输入输出结构

先把这个题剥成最朴素的描述：有n个城市，编号从0到n-1，每个城市有一个通行费，记作passingFees[i]，你经过这个城市就要付费。城市之间有若干条双向道路，每条路都需要消耗一定时间。你现在从城市0出发，要在不超过maxTime的时间内到达城市n-1，求所有合法路线中通行费总和的最小值。如果根本不可能在规定时间内到达，就返回-1。

输入结构一般长这样：

• maxTime：一个整数，表示允许的最大总耗时；
• edges[i] = [u, v, t]：表示城市u和v之间有一条耗时为t的双向道路；
• passingFees[i]：表示进入城市i需要支付的费用，起点和终点都算。

费用和时间这两个约束是同时存在的：时间超过maxTime的路径直接非法，费用不是唯一的优化目标，必须在合法时间内取费用最小。这种模型在现实中很常见，比如规划一次跨城市出行，既要在预算时间内到达，又想尽量省钱；或者外卖配送、物流调度这类场景，时间窗口是硬条件，成本是软目标。

1.2 为什么是动态规划而不是普通最短路

很多人第一反应是直接 Dijkstra。确实，如果只求最短时间或者只求最小费用，Dijkstra 都是标准解法。但这里的问题是双指标优化：一个指标是时间，一个指标是费用。Dijkstra 的贪心逻辑要求堆顶元素一旦出队，它的答案就是最终最优的，不过这个性质在这里的前提是"每一条边增加的费用 / 时间是固定的，优化目标唯一"。可这道题里，时间有硬上限，费用是另一个维度，你没法保证从堆顶取出的"费用最小的点"最后真的能走到终点，因为它可能早就超时了；同理，"时间最小的点"也不一定费用最优。

举个例子你就明白了：一条直达道路，时间刚好等于maxTime，费用很高；另一条绕路的路径，时间短但费用低。如果只看当前时间最短的节点去贪心，可能选了那条绕路，却错过直达的合法方案。DP 则不一样，它把所有可能的"时间点 + 城市"都拆成独立状态，逐个枚举转移，保证不会漏掉任何一条路径，也不会因为贪心顺序丢失正确性。

所以这道题的核心识别标志就是：有个约束维度（时间）+ 一个优化维度（费用），且约束维度的上限不大。只要maxTime在可控范围内，dp[t][v]这种二维状态就是最自然的解法。

2. 动态规划的核心：状态设计、转移方程与无后效性

2.1 状态定义：dp[t][v] 的含义与合理性

要解决双约束问题，最常见的套路就是把其中一个维度放进状态里，让另一个维度成为 DP 的值。这里我把"时间"作为状态维度，定义：

dp[t][v]表示恰好在时间t到达城市v时，能取到的最小通行费总和。

为什么要用"恰好"，而不是"不超过"？这是个很关键的理解点。如果你定义成"在时间不超过 t 时到达城市 v 的最小费用"，那么转移的时候你很难判断当前节点接下来的时间余量到底是多少，状态之间会相互污染。而定义成"恰好"之后，时间信息就被精确地记录在状态里，后面转移只需要加上w就能得到新的时间点，逻辑非常干净。

初始化也很直观：dp[0][0] = passingFees[0]，表示在时间0从城市0出发，此时已经支付了出发城市0的通行费。其余所有状态初始化为一个很大的数，代表不可达。

这里需要多嘴一句，有的题解会把起点费用延后到转移时再加，导致最后答案计算时处理起来很绕。我实际写下来感觉最不容易出错的写法就是：起点费用在初始化就计入，之后每转移到一个新城市v，额外加上passingFees[v]即可。这样答案直接就是dp[t][n-1]的最小值。

2.2 转移方程：枚举边、累加时间与费用

有向边和无向边的处理不太一样。解题目里明确说"Here,edges[i] = [u, v, time_i]denotes a bidirectional road"，所以每一条边要拆成两条方向来处理，不然你会漏掉v -> u的转移。

假设当前状态是dp[t][u]，它表示在时间t到达城市u的最小花费。从u出发，走一条到v、耗时为w的边，新的时间就是t + w。如果t + w <= maxTime，说明这条路还在时间限制内，那么到达v的总费用就是：

dp[t][u] + passingFees[v]

用这个值去尝试更新dp[t+w][v]，取最小值：

dp[t+w][v] = min(dp[t+w][v], dp[t][u] + passingFees[v])

写成循环就是：外层枚举所有时间t，内层遍历所有城市u，再内层遍历u的所有邻接边。如果某个dp[t][u]还是初始的无穷大，说明在时间t根本无法到达u，直接跳过即可。

注意：这里不需要做像 Bellman-Ford 那样"备份当前轮状态"的操作。因为每条边的耗时w至少为 1，所以dp[t+w][v]的更新只会影响未来更大的时间点，绝不会反过来影响当前时间t下的其他状态。时间递增的外层循环天然保证了这种无后效性。

最终答案就是所有dp[t][n-1]中的最小值。如果这个最小值依然是无穷大，说明在规定的maxTime内根本走不到终点，返回-1。

2.3 时间维度的选择：为什么是时间，而不是城市

有人会问：那我定义成dp[v]表示到达城市v的最小费用，用类似 SPFA 的方式迭代行不行？理论上可以，但你需要额外记录每个城市当前的最短到达时间，否则没法判断叠加时间后是否超限。这么做不仅状态本身仍然要带着时间信息，而且由于这个题没有负权边，你用 SPFA 式的反复松弛反而容易陷入无效更新。

把时间作为第一维还有一个很好的性质：你不需要对城市之间的到达顺序做拓扑排序，因为时间是天然有序的。哪怕图里有环，比如0 -> 1 -> 0 -> 1，每走一步时间都会增加，所以环不会导致状态重复，只会被时间上限自然拦截。这也是为什么这类"限制步数 / 限制时间 / 限制点数"的题目，都会导向 DP 而不是纯图搜索。

maxTime的规模决定了这个做法是否可行。LeetCode 1928 的maxTime一般在几千以内，n也不会特别大，所以二维数组 (maxTime + 1) * n是完全能开的。如果哪天maxTime特别大，比如 10^9，那 DP 的空间和时间就彻底炸了，那种情况得换思路，比如分层图上做剪枝搜索，这是后话，至少这个题的标准解法就是二维 DP。

3. 代码实现与完整过程

3.1 建图细节：双向边要拆成两条单向边

实现前先把图建好。拿到edges之后，对每一条[u, v, w]，在u的邻接表里加上(v, w)，同时在v的邻接表里加上(u, w)。

这里有个常见的低级错误：只建了一条方向，导致从0出发的路径一旦需要走反向边就全部断掉，答案直接变成-1，还不容易排查。所以我建议建图后顺手检查几个样例，比如0 -> 1和1 -> 2这种链路，确保两个方向都在邻接表里。

如果不想用邻接表，也可以直接在 DP 循环里遍历所有边，对每条边做两个方向的转移：

如果 dp[t][u] 可达，则尝试更新 dp[t+w][v] 如果 dp[t][v] 可达，则尝试更新 dp[t+w][u]

这种写法代码更短，但每次都要扫一遍全部边，效率略低。数据规模小的时候无所谓，数据规模大的时候邻接表明显更高效，因为很多边和当前不可达的城市根本无关。

每种语言写起来稍有差别，但结构完全一样。我用 C++ 写了一个参考实现，就是讲思路时说的那种标准写法：

class Solution { public: int minCost(int maxTime, vector<vector<int>>& edges, vector<int>& passingFees) { int n = passingFees.size(); // INF 要比任何可能的费用总和都大 const int INF = 1e9 + 7; // dp[t][v]：恰好时间 t 到达城市 v 的最小通行费 vector<vector<int>> dp(maxTime + 1, vector<int>(n, INF)); // 起点城市 0 的费用，在初始时就计入 dp[0][0] = passingFees[0]; // 建邻接表，双向道路拆成两条单向边 vector<vector<pair<int, int>>> graph(n); for (const auto& e : edges) { int u = e[0], v = e[1], w = e[2]; graph[u].push_back({v, w}); graph[v].push_back({u, w}); } // 按时间递增枚举所有状态 for (int t = 0; t <= maxTime; ++t) { for (int u = 0; u < n; ++u) { if (dp[t][u] == INF) continue; // 尝试从 u 走向所有邻居 v for (const auto& [v, w] : graph[u]) { int nextTime = t + w; if (nextTime > maxTime) continue; dp[nextTime][v] = min(dp[nextTime][v], dp[t][u] + passingFees[v]); } } } // 答案是所有时间内到达终点 n-1 的最小费用 int ans = INF; for (int t = 0; t <= maxTime; ++t) { ans = min(ans, dp[t][n - 1]); } return ans == INF ? -1 : ans; } };

这段代码提交是能过的，而且我觉得它的可读性比一些压缩过变量的版本要好得多，很适合作为面试时的板子。

3.2 模拟一次转移过程：一个具体的小例子

空讲公式容易晕，我跑一个小例子说明递推到底是怎么发生的。假设有 3 个城市0、1、2，通行费分别是[5, 10, 20]，道路和时间：

• 0 -> 1，耗时2
• 1 -> 2，耗时3
• 0 -> 2，耗时5

maxTime = 5。起点0在时间0的复杂度是dp[0][0] = 5。

先处理时间t = 0，城市0可达。走0 -> 1，时间变成2，费用变为5 + 10 = 15，所以dp[2][1] = 15。走0 -> 2，时间变成5，费用变为5 + 20 = 25，所以dp[5][2] = 25。

再处理t = 2，城市1可达，费用15。走1 -> 2，时间变成2 + 3 = 5，费用变为15 + 20 = 35，所以尝试更新dp[5][2]，但已有的25更小，因此不更新。

最后在时间0 到 5里找到达2的最小值，答案是25，对应的是0直达2那条路。

这个例子的意义在于演示：即使绕路的两段拼起来也能在时限内到达，DP 依然会老老实实比较两条路线的费用，然后取更小的那个。不像贪心算法，DP 不会因为某条路径"看起来耗时少"就草率地认定它最优。

3.3 时间复杂度和空间复杂度分析

时间上，外层循环maxTime + 1次，内层先遍历n个城市，再遍历每个城市的度。总复杂度理论上可以认为是O(maxTime * (n + E))，其中E是双向边拆开后的边的总数，也就是edges.size() * 2。代码里我用的是邻接表，所以整张图被完整扫描一遍的总次数就是maxTime * (n + E)这个量级。

空间上，开了一个maxTime + 1行、n列的二维数组，因此空间复杂度是O(maxTime * n)。以maxTime = 1000、n = 1000为例，1001 * 1000个int大约是 4MB 左右，完全能轻松放进内存。

曾有读者问我能不能滚动数组优化空间，把dp[t]这一维滚动掉。结论是可以的，但有一定代价。因为一条边的耗时可能不同，你从dp[t]转移到的dp[t+w]不一定就是下一层，而可能是下很多层。如果只保存最近一层的dp，那么在时间t之后某个时间点回来更新时，原来的状态可能已经被覆盖了。所以真要滚动，需要使用一个"待更新队列"或者借助类 Dijkstra 的搜索方式，这就已经偏离 DP 的简洁形态了。实际面试或比赛中，maxTime * n的二维数组通常可以接受，所以我更推荐先写不优化的版本，保证正确性优先，然后再谈优化。

4. 常见问题与排查技巧实录

4.1 初始化与 INF 的选取

这题的坑往往不出在转移上，而出在最不起眼的地方。初始化时，dp数组要全部填成一个很大的数，我习惯用1e9 + 7或INT_MAX / 2。INT_MAX直接用来加会导致整型溢出，所以不要图省事用INT_MAX去累加。INT_MAX / 2也可以，只要确保任何合法费用和INF相加之后仍然远大于真实答案即可。

另一个隐蔽的问题是：起点城市 0 的费用到底要不要算进去？题目原文写的是 "including the starting and ending cities"，所以一定要算。如果写题解时把这个地方看漏，样例可以通过，但换一组数据就出问题。以n = 1为例，起点就是终点，费用就是passingFees[0]，不管maxTime是多少，答案都应该是passingFees[0]。这个边界用例很适合用来验证你的初始化有没有写错。

4.2 什么时候返回 -1 才算对

返回 -1 的场景只有一种：在maxTime时间内无论如何都到不了终点。但很多人在实现时把"答案不存在"和"dp 仍是 INF"搞混，导致多写了不必要的时间判断。

比如，有些题解会在每一轮时间结束后检查dp[t][n-1]有没有变小，如果没有就提前退出循环。这个优化要小心使用：因为存在多个不同时间点到达终点的情况，比如直达在t=5到达费用 30，绕路在t=3到达费用 20。如果只看单一时间点身后的变化，可能会误判，而实际上其他时间点还有更优解。我建议最稳妥的做法是：把所有时间维度上的dp[t][n-1]全部算完，最后统一取最小值，整个过程不做提前终止。

只有在极大规模数据下，为了效率尝试剪枝，才可以在某条路径的费用已经超过当前已知答案时跳过，如下面这个判断：

if (dp[t][u] >= ans) continue;

这个剪枝不会影响正确性，因为费用只会增加不会减少，但ans仍然要放在最后统一更新。

4.3 为什么不能用 Dijkstra 直接改一改

这个问题几乎每一版题解下面都有人问。Dijkstra 的堆优化写法确实可以处理一些路径长度和花费的双限制问题，但核心前提是"贪心选择不会导致漏解"。在这道题里，费用最优和时间最优不一定落在同一条路径上，某一时刻你从堆里弹出的节点，可能是当前路径费用最小的，但这不代表从它往下走能拼出全局费用最小且时间合法的路径。另一个更符合 DP 直觉的比喻是：你手里有两张表，一张记录"时间有多短"，一张记录"费用有多低"，两者没法合并成一个排序维度。除非你引入启发式函数，比如用A*做带剪枝的搜索，那又另当别论。

4.4 踩过的坑：双向边、重复到达同一城市、大时间上限

我实际踩过一次反向边漏加的错误。排查方法很简单，自己构造一个只有两个城市的用例：maxTime = 5，道路0 -> 1耗时1。如果建图只建了0 -> 1，那dp在正向转移时没问题；但如果你加一条道路1 -> 0，然后想规划从0走到1再绕回0再走到1的路线，那么反向边缺失就会直接导致dp无法更新。这类问题调试起来很容易一眼瞟过，所以我习惯把"双向边"这一句注释直接写在建图旁边。

另外还有一个细节：由于图中有环，同一城市可能在不同时间点被多次到达，这是合法的。比如dp[3][1] = 5，dp[6][1] = 8，两条路径都能走到城市 1，只是耗时不同，费用也不同。DP 不能简单地认为"既然城市 1 已经被访问过，就可以不用再访问第二次"——在这个题的模型里，访问时间不同，后面路径的剩余时间预算就不同。这也是为什么有些人用 visited 数组标记剪枝会出问题的原因。只有当某个状态既时间更大又费用更大，即严格被其他状态支配时，才可以安全剪枝，但这种检查比较麻烦，比赛中一般不值得做。

最后说一个关于语言细节的事：Python 写dp[mx + 1][n]这种大列表，如果数据规模大一点很容易踩到运行时间红线，而 C++ 的vector<vector<int>>在同样规模下通常更稳。如果习惯用 Python 刷题，可以尝试把二维数组换成一维和二维混合的字典，或者改用列表推导式并尽量少在循环里做嵌套属性访问。这道题我在 C++ 版本上运行耗时约几十毫秒，在 Python 下需要稍微注意常数优化。

5. 从这道题延伸开去：一类"时间 / 步数 / 预算"限制题的通用解

这种"限制一个维度的最大值，求另一个维度的最小值"的模型，在 LeetCode 上不是孤例。比如有一道很经典的题是求最多经停 K 站的最便宜航班，用的状态就是dp[k][v]，表示经过不超过k次转移到达城市v的最小费用，其结构和本题几乎一模一样，只是把时间维度换成了步数维度。再比如一些背包类问题，把"花费的硬币数"作为状态维度，把"购买到的价值"作为优化目标，也是同一个套路。

所以当你再看到这类题时，可以快速做一个条件判断：是否有一个维度是可枚举且范围可接受的整数（时间、步数、剩余预算、已选数量等）。如果答案是可以，那么二维 DP 往往就是最简单直接的解法。状态定义里放一个约束维度，转移时另一个约束变成条件判断，优化目标作为 DP 的值，这种思路几乎可以套用到所有"双限制求最优"的问题上。

我做这类题时还有一个习惯：先不急着写代码，先在纸上画一个表格，横轴是时间，纵轴是城市，然后手动填几行。一旦你在表格里填对了起点那一格，后面的所有转移都会顺理成章地落在表格里，整个递推过程就一目了然了。这个方法也推荐给你，比你直接盯着代码想边界条件要高效得多。

最后分享一个解题顺序：先看数据范围，确认maxTime * n能否承受；再看路径定义有没有双向边；最后确认起点终点的费用是否计入。这三点都检查完，这道题的正确率基本上就已经能保证了。