1. 项目概述从“最优旅行”到经典图论问题最近在整理历年算法竞赛的真题翻到了第十届蓝桥杯国赛的这道“最优旅行”。乍一看标题还以为是什么旅游规划或者路径推荐的应用题但仔细一读题发现它其实是一个披着“旅行”外衣的、非常经典的图论问题。这道题的核心是要求我们在一个带权有向图中找到从起点到终点的最短路径但有一个关键的约束条件路径上经过的节点城市数量必须恰好等于一个给定的值k。这就不再是简单的 Dijkstra 或者 Floyd 能直接解决的了它引入了“步数”这个维度将问题升级为了一个“带约束的最短路径”问题或者更具体地说是一个“恰好经过 k 个节点的最短路径”问题。对于刚接触图论不久的同学可能会觉得有点懵。最短路径我知道BFS、Dijkstra但怎么还带“恰好走k步”的要求这就像让你从家到公司不仅要求路程最短还规定你必须恰好经过5个红绿灯一下子就把问题的复杂度提上来了。这道题的价值就在于它非常典型地展示了如何将动态规划的思想与图论模型相结合来解决这类带有额外约束的优化问题。它考察的不仅仅是你会不会背模板更考察你是否能理解状态定义并设计出正确的状态转移方程。在实际的软件开发中类似的场景其实很多比如网络数据传输中要求经过特定数量的中转节点且延迟最小或者物流配送中要求访问固定数量的站点后抵达目的地等其核心建模思路是相通的。接下来我就结合这道真题把它的解题思路、代码实现、以及一些容易踩的坑掰开揉碎了讲清楚。我们会从最朴素的暴力搜索思路开始逐步优化到标准的动态规划解法并探讨其时间复杂度和优化空间。无论你是正在备赛的选手还是对算法感兴趣的开发者相信都能从中获得启发。2. 问题核心解析与建模思路2.1 题意重述与输入输出分析首先我们必须把题目从自然语言精确地翻译成数学模型。题目通常是这样描述的给定一个有n个节点的有向图节点编号从1到n。同时给出一个m条边的列表每条边由起点u、终点v和权重w代表距离、成本等组成。然后给定一个起点s一个终点t以及一个整数k。我们的目标是找到一条从s到t的路径使得这条路径恰好经过k个节点注意起点和终点都计入节点数并且这条路径上所有边的权重之和最小。如果不存在这样的路径则输出-1。这里有几个关键点需要立刻明确这也是容易出错的地方“恰好经过 k 个节点”这意味着路径的节点序列长度是k。例如k3那么路径必须是s - x - t这样的形式一共3个节点。k1则意味着起点就是终点路径长度为0除非题目允许自环否则通常认为不可达除非 st。有向图边的方向是固定的u-v不等于v-u。权重距离通常为正整数这保证了后续一些算法如Dijkstra的前提成立。节点数 vs 边数路径的约束是节点数而不是边数。一条有k个节点的路径包含k-1条边。输入格式一般如下n m s t k u1 v1 w1 u2 v2 w2 ... um vm wm输出一个整数即最短距离若不可达则输出-1。2.2 从暴力搜索到动态规划的思维推导最直观的想法是暴力搜索比如使用DFS遍历所有从s出发、深度为k-1因为走k-1条边到达t的路径然后取距离最小值。但这种方法的时间复杂度是O(n^(k-1))当n和k稍大时比如 n100, k10就完全不可接受了。我们必须寻找更高效的算法。这时动态规划DP就该登场了。DP的核心思想是将原问题分解为子问题并存储子问题的解以避免重复计算。对于这道题一个非常自然的状态定义是dp[i][j]表示从起点s出发恰好经过i个节点到达节点j的最短距离。这里i表示路径的节点数阶段j表示当前所在的节点状态。dp[k][t]就是我们最终要求的答案。那么状态如何转移呢考虑我们如何到达状态dp[i][j]。要恰好用i个节点走到j那么上一步即前i-1个节点我们一定在某个节点p上并且从p到j有一条直接的边。所以我们可以遍历所有指向j的入边(p, j, w)用dp[i-1][p] w来更新dp[i][j]。状态转移方程如下dp[i][j] min { dp[i-1][p] w(p, j) }其中p是所有存在边(p, j, w)的节点。初始状态dp[1][s] 0因为从s出发经过1个节点就是自己到达s距离为0。对于其他节点j ! sdp[1][j]应初始化为无穷大表示不可达。有了状态定义和转移方程我们就可以从i2开始逐步计算到ik最后dp[k][t]就是答案。如果dp[k][t]仍然是无穷大则输出 -1。2.3 算法选择与复杂度分析上述DP解法的时间复杂度是O(k * m)。其中外层循环i从 2 到k共k-1轮内层循环需要遍历所有m条边对于每条边(u, v, w)它可能用来更新dp[i][v]即作为p-j的边。所以总复杂度是O(k*m)。空间复杂度是O(k * n)用于存储DP表。这里有一个常见的优化点由于dp[i][j]只依赖于dp[i-1][...]我们可以使用滚动数组只保留两个一维数组prev和curr将空间复杂度优化到O(n)。具体来说在计算第i层时prev数组存储第i-1层的结果curr数组存储正在计算的本层结果计算完成后交换两者。注意为什么不用 Dijkstra因为 Dijkstra 算法解决的是无阶段约束的单源最短路径问题。它无法在寻找最短路径的同时保证路径的节点数恰好为k。DP 方法通过增加“阶段”这一维度完美地刻画了这个约束。3. 核心算法实现与代码详解理论清晰了我们来看代码怎么写。我会给出两种版本的实现一种是直观的二维DP便于理解另一种是优化了空间的滚动数组版本更适用于竞赛环境。3.1 基础二维动态规划实现首先我们需要处理输入并用合适的数据结构存储图。由于转移时需要根据终点j快速找到所有入边(p, j, w)使用邻接表存储“反向图”是一个高效的选择。也就是说我们存储的是graph[v] list of (u, w)表示所有指向节点v的边。#include iostream #include vector #include cstring #include algorithm using namespace std; const int INF 0x3f3f3f3f; // 用一个较大的数代表无穷大 int main() { int n, m, s, t, k; cin n m; cin s t k; // 构建反向邻接表 graph[v] {(u, w), ...} vectorvectorpairint, int graph(n 1); for (int i 0; i m; i) { int u, v, w; cin u v w; // 存储反向边方便DP时根据终点v找到前驱u graph[v].emplace_back(u, w); } // dp[i][j]: 恰好经过i个节点到达j的最短距离 vectorvectorint dp(k 1, vectorint(n 1, INF)); // 初始化经过1个节点只能到达起点s距离为0 dp[1][s] 0; // DP过程 for (int i 2; i k; i) { // 阶段节点数从2到k for (int j 1; j n; j) { // 状态当前节点j // 遍历所有能到达j的边 (p, j, w) for (auto [p, w] : graph[j]) { // 如果前一个状态可达则尝试更新 if (dp[i-1][p] ! INF) { dp[i][j] min(dp[i][j], dp[i-1][p] w); } } } } // 输出结果 int ans dp[k][t]; if (ans INF) { cout -1 endl; } else { cout ans endl; } return 0; }代码要点解析INF 的设置0x3f3f3f3f是一个常用的值因为它大约等于10^9且其两倍仍在32位整数范围内不会溢出。用memset初始化时这个值的每个字节都是0x3f也很方便。反向建图这是关键技巧。在状态转移dp[i][j] min(dp[i-1][p] w)时我们需要所有以j为终点的边。如果正向建图对于每个j我们需要遍历所有节点p检查是否有边(p, j)复杂度是O(n)总复杂度会升至O(k*n^2)。反向建图让我们可以直接获得j的所有入边将内层循环复杂度降为O(入度(j))总复杂度O(k*m)。边界条件dp[1][s] 0是唯一的初始可行状态。注意如果k1且st答案就是0上述代码也能正确处理。3.2 空间优化滚动数组技巧当n和k较大时比如 n1000, k1000O(k*n)的空间约4MB可能可以接受但使用滚动数组是更优雅且节省空间的做法。#include iostream #include vector #include cstring #include algorithm using namespace std; const int INF 0x3f3f3f3f; int main() { int n, m, s, t, k; cin n m; cin s t k; // 构建反向邻接表 vectorvectorpairint, int graph(n 1); for (int i 0; i m; i) { int u, v, w; cin u v w; graph[v].emplace_back(u, w); } // 使用滚动数组prev代表i-1层curr代表i层 vectorint prev(n 1, INF); vectorint curr(n 1, INF); // 初始化i1的情况 prev[s] 0; // DP过程 for (int i 2; i k; i) { // 初始化当前层为无穷大 fill(curr.begin(), curr.end(), INF); for (int j 1; j n; j) { // 计算dp[i][j] for (auto [p, w] : graph[j]) { if (prev[p] ! INF) { curr[j] min(curr[j], prev[p] w); } } } // 滚动当前层变成下一轮的前一层 swap(prev, curr); } // 注意循环结束后prev存储的是第k层的结果因为最后交换了一次 // 如果k1prev就是初始化的结果也正确。 int ans prev[t]; if (ans INF) { cout -1 endl; } else { cout ans endl; } return 0; }滚动数组的细节我们只需要两个数组prev和curr。初始时prev代表i1的情况即dp[1]。在计算i层时我们基于previ-1层计算curri层。计算完i层后通过swap(prev, curr)让prev指向刚算好的i层为下一轮计算i1层做准备。最终prev存储的就是dp[k]的结果。3.3 一个完整的测试案例假设输入如下4 5 1 4 3 1 2 1 2 3 1 3 4 1 1 3 4 2 4 2表示有4个节点5条边。从1出发到4恰好经过3个节点。 图的结构是1-2 (1)2-3 (1)3-4 (1)1-3 (4)2-4 (2)我们手动推导一下要求恰好3个节点即走2条边。可能的路径有1 - 2 - 4 (节点1,2,4)距离 1 2 31 - 3 - 4 (节点1,3,4)距离 4 1 5最短距离是3。运行我们的DP程序dp[1][1] 0。计算dp[2][j]dp[2][2] dp[1][1] w(1,2)011dp[2][3] dp[1][1] w(1,3)044dp[2][4] dp[1][2] w(2,4)但dp[1][2]是 INF所以不可达。计算dp[3][j]即最终需要的dp[3][4] min(dp[2][2]w(2,4), dp[2][3]w(3,4)) min(12, 41) min(3,5)3程序输出3符合预期。4. 常见问题、边界情况与实战技巧即使理解了算法在实现时还是会遇到各种坑。下面是我在实战和教学中总结的一些典型问题和技巧。4.1 初始化与不可达的判断这是最容易出错的地方之一。dp[1][s] 0是唯一的起点。其他所有状态包括dp[1][j] (j!s)和dp[i][j] (i2)的所有位置都必须初始化为无穷大INF。因为“恰好经过 i 个节点”是一个很强的约束在没计算之前我们不知道是否可达。k1的情况如果k1那么路径只能是s到s且不经过任何边。此时只有当s t时答案是0否则是 -1。我们的代码中初始化dp[1][s]0其他为 INF。所以如果k1直接输出dp[1][t]若st则为0否则为 INF输出-1。这一点一定要在代码注释或思维中明确因为很多测试用例会包含这个边界情况。INF 值的选择与判断如前所述使用0x3f3f3f3f作为 INF。在判断是否可达时使用if (ans INF)或if (ans INF/2)。后者更安全因为如果在状态转移中出现了 INF 加上一个权值的情况可能会发生整数溢出尽管概率小。更稳健的写法是if (ans INF/2)。4.2 关于“节点数”与“边数”的陷阱题目要求是“恰好经过 k 个节点”。这意味着路径的顶点序列长度是 k。有些题目可能会表述为“恰好经过 k 条边”或“恰好经过 k-1 条边”这会导致状态定义和初始化的不同。“恰好 k 个节点”DP 阶段i从 1 到kdp[1][s]0。“恰好 k 条边”DP 阶段i从 0 到kdp[0][s]0经过0条边在起点。务必在读题时用笔圈出这个关键信息。一个简单的记忆方法如果起点和终点都算节点那么“节点数” “边数” 1。4.3 图存储方式的选择与性能影响我们选择了反向邻接表。为什么不用正向邻接表正向邻接表graph[u] {(v, w), ...}存储的是从u出发的边。在计算dp[i][j]时我们需要所有能到达j的节点p。如果使用正向表对于每个j我们需要遍历所有其他节点p检查graph[p]中是否有到j的边。这需要O(n * 平均出度)在最坏情况下稠密图就是O(n^2)。反向表直接给出了j的所有入边复杂度是O(入度(j))总复杂度稳定在O(k*m)。m是边数在稀疏图中远小于n^2。因此当DP转移依赖于当前状态的前驱时考虑构建反向图是一个通用优化技巧。4.4 负权边与算法失效我们的DP算法以及状态转移方程dp[i][j] min(dp[i-1][p] w)要求图中不能有负权环。注意是“负权环”而不是简单的“负权边”。含有负权边算法本身仍然可以执行因为DP是按阶段推进的。但是其物理意义可能发生变化“最短距离”可能没有下界并且对于“恰好k个节点”的约束负权边可能导致问题。通常竞赛题中边权均为正。含有负权环如果存在一个环其总权重为负那么理论上可以沿着这个环无限绕行使得“路径”权重趋于负无穷即使有节点数约束也可能通过绕环来“刷低”距离。这时我们的DP模型就失效了因为它无法处理这种带负环的约束路径问题。这类问题通常需要更复杂的算法如最小费用流或针对性的DP。所以在应用此DP模型前务必确认题目边权为非负或者明确不存在负权环。4.5 路径还原与方案输出有时题目不仅要求最短距离还要求输出具体路径。这需要在DP过程中记录“决策”即dp[i][j]是从哪个p转移过来的。我们可以用一个二维数组pre[i][j]来记录。在更新dp[i][j]时如果dp[i-1][p] w dp[i][j]那么不仅更新距离同时记录pre[i][j] p。输出时从终点t开始根据pre[k][t]找到前一个节点依次回溯到起点s再反转序列即可。需要注意的是如果存在多条距离相同的最短路径pre数组只会记录其中一条取决于代码中min更新的顺序。如果题目要求输出所有方案或特定方案则需要更复杂的处理。5. 算法扩展与变种思考“最优旅行”这道题提供了一个很好的模板。掌握了它你可以解决一大类“带约束的最短路径”问题。下面看看几个可能的变种5.1 变种一恰好经过 k 条边的最短路径这就是将约束从“节点数”改为“边数”。状态定义变为dp[i][j]表示从s出发恰好经过i条边到达j的最短距离。初始化dp[0][s] 0其他为 INF。转移dp[i][j] min(dp[i-1][p] w(p, j))。答案dp[k][t]。可以看到只是阶段i的起始值从1变成了0。代码结构几乎完全一样。5.2 变种二节点访问次数限制每个节点最多经过一次这是旅行商问题TSP的简化版。如果k较小比如 15我们可以使用状态压缩DP。状态dp[mask][j]其中mask是一个二进制数表示已经访问过的节点集合包括jj是当前所在节点。初始化dp[1(s-1)][s] 0。转移对于状态(mask, j)尝试访问一个未访问过的节点v如果存在边(j, v, w)则dp[mask|(1(v-1))][v] min(..., dp[mask][j] w)。答案遍历所有mask中恰好有k个1即访问了k个节点且当前节点为t的状态取最小值。这个算法复杂度是O(2^n * n^2)当n20时可以考虑。5.3 变种三求方案数最短路径的条数在求最短距离的同时询问有多少条不同的最短路径满足“恰好k个节点”。这需要在DP表中增加一个计数数组cnt[i][j]。dp[i][j]定义不变。cnt[i][j]表示从s出发恰好经过i个节点到达j且距离为dp[i][j]的路径条数。初始化cnt[1][s] 1其他为0。转移在更新dp[i][j]时如果发现一条更短的路径dp[i][j] dp[i-1][p] w则cnt[i][j] cnt[i-1][p]。如果发现一条距离相等的路径dp[i][j] dp[i-1][p] w则cnt[i][j] cnt[i-1][p]。答案cnt[k][t]。注意取模如果题目要求。5.4 从算法竞赛到实际工程在实际的软件开发中比如物流路径规划、网络路由选择我们很少会遇到如此严格的“恰好k个节点”的约束。但**“带约束的优化”**这一思想是通用的。约束可能是“途经某些特定点”、“时间窗口限制”、“资源如电量限制”等。这时DP的状态设计就需要包含这些约束信息例如dp[time][node][fuel]表示在某个时间、某个节点、剩余某资源量下的最优解。这类问题的求解往往更复杂可能会用到启发式算法如遗传算法、模拟退火或专业求解器。但理解基础DP模型能帮助你清晰地定义问题状态这是设计更高级算法的基础。回过头看“最优旅行”这道题它就像一把钥匙帮你打开了“动态规划”与“图论”结合的大门。其核心——定义状态dp[阶段][状态]然后根据状态间的转移关系进行递推——是解决无数优化问题的通用范式。吃透这一道题其价值远大于机械地刷十道题。在下次遇到类似问题时不妨先问问自己约束条件是什么它可以被表示为DP的一个维度吗状态如何转移想清楚这些问题就解决了一半。