刷题打卡到了第2761道题库里跳出一道编号P3753的题名字叫“国事访问”。坦白讲第一眼看到这个标题我以为是政治新闻结果点进去发现是一道中规中矩的图论题。但这道题最坑的地方在于题面写得特别像“最短路”实际上考的却是状态压缩动态规划。我当时差点用SPFA直接交还好忍住了认真推了一遍才把真正的模型摸清楚。这篇博文就把这道题的完整复盘写下来从题面拆解、状态设计、C实现到调试过程中踩过的三个坑一次性讲透。如果你正在练状压DP或者刷到“必须访问若干点然后到终点”这类变种题这篇应该能帮你节省不少时间。1. 题面到底想让你干什么别被“访问”两个字带偏1.1 从题目背景还原出真正的输入输出模型我按自己的理解把题面重新叙述一遍细节细节可能与OJ上的原文有出入但核心模型是一样的给定N个国家和M条双向外交通道每条通道有一个通行成本。元首从国家A出发必须访问K个指定的关键国家顺序可以任意最后到达国家B。每个国家可以重复经过求最小总成本。数据范围我记得大概是N在50以内M在500左右关键国家K不超过15边权可以达到10的9次方。这里有个关键点关键国家必须全部访问但访问顺序是自由的。从A到B的最短路本身好算只要跑一次算法就行。但强制点名要访问的K个点之后问题性质就完全变了。你可以把K个关键点看作是“任务清单”任务是“每个点至少进去一次”而不是要求你在这些点之间走出一条简单路径。普通的最短路算法解决不了这种“强制性”因为最短路的终点只有一个中间经过哪些点并不会影响求出来的距离。我把数据范围和复杂度预估算了一下如下表所示参数取值范围对算法的影响国家数N≤50可以做Floyd全源最短路O(N^3)完全没问题通道数M≤500边权较大注意重边和自环关键国家数K≤152^K 32768可以放心做子集DP边权≤10^9int够用但INF和加法要小心溢出目标访问全部关键国后到B不允许跳过任何关键国1.2 我第一眼差点踩进去的坑把它当成普通最短路刚读完题我的第一反应是“这不就是求A到B的最短路嘛K个关键点算什么”。但我很快意识到这样完全错误。举个极端例子假设有5个关键点你从A出发先沿最短路走到第3个关键点发现绕了一大圈后面再去其他关键点总花费可能反而更高。最短路的路径不会考虑“这个点我还没访问过”这件事所以直接用最短路的结果是错的。还有一点容易误解这不是旅行商问题TSP的裸题。TSP要求每个点只经过一次回到起点求最小环路这道题允许重复经过、不要求回到出发点而且最终必须停在B。换句话说这道题的难点不是“路径规划”本身而是“怎么在访问集合里做决策”。我当时意识到这一点之后就知道得换个思路问题的本质是K个关键点的访问顺序决策。K最大只有15这种“子集顺序”的组合天然适合用状态压缩DP来解。2. 状态设计推演为什么是“子集掩码 当前所在点”两维2.1 从一个掩码看到全部访问情况状态压缩DP的出发点很简单用一个整数的二进制位来表示“哪些关键点已经被访问过”。假设K5掩码mask 0b10110就表示第1、2、4号关键点从低位开始数已经被访问过。掩码的值域是0到2^K-1K15时最多32768个状态完全能塞进一个二维数组里。光有掩码还不够。掩码只告诉我们“已经去过哪些点”但没告诉我们“现在人在哪里”。后面继续访问其他点时花费取决于当前位置到下一个点的距离所以DP的第二维必须记录当前最后停留的关键点。这样一来状态定义就很清楚了dp[mask][i] 已经访问过mask中的关键点当前停在第i个关键点时的最小总花费其中mask的第i位必须为1因为只有已经到过第i个点才可能“当前停在第i个关键点”。2.2 为什么不能让“已经访问了几个点”当状态可能有同学说那我记录dp[i][k] 已经访问了i个点当前在第k个点行不行不行。关键在于“已经访问了哪几个点”的信息完全丢失了。比如你现在访问了3个点当前在第4号关键点但你不知道第4号是否已经被访问过也不知道你访问的是哪三个点。这会导致重复访问同一个点也合法状态无法区分转移的时候会出现严重的后效性。“访问过哪个集合”这一信息在图中是不可压缩的。唯一可行的办法就是把集合本身显式记录成状态这正是子集DP的核心思想。你可以把它理解成打开了一张“勾选过的清单”每次移动后勾掉一个新节点回退时清单信息始终保留。这个“清单”就是mask。2.3 Floyd预处理把原图“压平”成一张完全图确定了DP之后还有一个前置工作任意两个状态之间转移需要的是任意两个关键点之间的最短距离。原图是一张稀疏图直接在做DP时多次跑最短路肯定不划算。因此我选择先做一次Floyd全源最短路把任何两个国家之间的最短距离算出来。Floyd做完之后原图就抽象成了一张“完全图”任意两个关键点之间都有直接的“虚拟边”边权等于它们之间的最短路。这样在状态转移时就能直接查表不需要反复推算路径。这个预处理的好处是DP阶段完全不需要关心原图的连通细节只关心两两距离简单干净。实际写Floyd的时候无限大的处理要充分注意。我用0x3f3f3f3f作为INF因为两个INF相加会溢出成负数所以代码里在转移前要判断距离是不是INF。3. 完整C实现与三个必须注意的编码细节3.1 核心代码Floyd加状压DP的完整实现下面这段代码是我在OJ上AC时用的版本关键位置我都加了注释。它完整可复现但请你先自己推一遍模型再来抄否则遇到变体题容易翻车。#include bits/stdc.h using namespace std; const int MAXN 55; const int INF 0x3f3f3f3f; int n, m, K, A, B; int dist[MAXN][MAXN]; // 经过Floyd后的最短路 vectorint keyNode; // 关键国家的原始节点编号已去重 // 将关键节点原始编号映射到 0~K-1 int id[MAXN]; int dp[1 15][15]; int main() { scanf(%d%d%d%d%d, n, m, K, A, B); --A; --B; memset(dist, 0x3f, sizeof(dist)); for (int i 0; i n; i) dist[i][i] 0; for (int i 0; i m; i) { int u, v, w; scanf(%d%d%d, u, v, w); --u; --v; // 有重边时取最小值 dist[u][v] min(dist[u][v], w); dist[v][u] min(dist[v][u], w); } // Floyd for (int k 0; k n; k) for (int i 0; i n; i) { if (dist[i][k] INF) continue; for (int j 0; j n; j) dist[i][j] min(dist[i][j], dist[i][k] dist[k][j]); } // 读入关键节点注意去重 setint st; for (int i 0; i K; i) { int x; scanf(%d, x); --x; st.insert(x); } keyNode.assign(st.begin(), st.end()); K (int)keyNode.size(); // 去重后更新K if (K 0) { printf(%d\n, dist[A][B] INF ? -1 : dist[A][B]); return 0; } memset(id, -1, sizeof(id)); for (int i 0; i K; i) id[keyNode[i]] i; // 初始化dp数组 memset(dp, 0x3f, sizeof(dp)); for (int i 0; i K; i) { int from A; // 特判A本身也是关键点之一 if (A keyNode[i]) from A; // 距离为0 dp[1 i][i] dist[A][keyNode[i]]; } int full 1 K; int ans INF; // 状态转移枚举mask和最后停留的关键点 for (int mask 1; mask full; mask) { for (int last 0; last K; last) { if (!(mask (1 last))) continue; if (dp[mask][last] INF) continue; // 剪枝当前花费已经不小于已有答案没必要继续 if (dp[mask][last] ans) continue; for (int nxt 0; nxt K; nxt) { if (mask (1 nxt)) continue; int w dist[keyNode[last]][keyNode[nxt]]; if (w INF) continue; // 两点间不连通跳过 int to dp[mask | (1 nxt)][nxt]; to min(to, dp[mask][last] w); } } } // 最后一段从最后一个关键点到B for (int last 0; last K; last) { int w dist[keyNode[last]][B]; if (w INF) continue; ans min(ans, dp[full - 1][last] w); } printf(%d\n, ans INF ? -1 : ans); return 0; }3.2 INF的取值与加法溢出问题上面代码里我用了0x3f3f3f3f这个值本身是1061109567略大于10亿。题目边权最大能到10亿两个小于等于10亿的数相加会超过21亿逼近int上限2147483647两个INF相加就一定会超过int上限变成负数。这种负值一旦混进DP表min函数会把一个极小的负数当成“最优答案”后面所有转移全部错乱。解决办法就是代码里那两个if (w INF) continue;的判断。做任何加法之前先确认参与运算的距离不是INF。我之前在别题上栽过跟头这次写的时候特别小心。有的同学喜欢开long long数组那也能规避溢出但既然这道题int够用我觉得用int加判断更利落完全没必要为了省事让整个数组都变long long。3.3 重边、自环以及起点终点本身就是关键点M条通道里可能包含重边比如两个国家之间给了一模一样的双向通道或者给出两条不同成本但两端相同的边。我的做法是读入时直接取min覆盖保证dist[u][v]始终是最小值。自环也不影响读入uv时更新一次dist[u][u]虽然它本来就是0min一下也没关系。还有一个很容易被忽略的角落起点A或终点B本身在关键点列表里。如果A就是某个关键点那从A出发时这个关键点已经被访问过了不应该再算一遍从A到它自己的往返成本。我的初始化代码里dist[A][keyNode[i]]在AkeyNode[i]时天然等于0所以结果没错但如果你用别的写法比如先让所有人从A跑到第i个关键点就可能多算一段。遇到这类题建议把这种特殊情况单独列出来想清楚别丢分。3.4 去重关键点一个让我多查半小时的地方题目明确说“K个关键国家”但我第一次交的时候WA了。我以为是我DP写错了反复查了半天最后写了个对拍程序才发现输入数据里可能有重复的关键国家编号比如关键点列表是1 2 1 3。我的原代码会把“国家1”当成两个不同的位置导致状态空间多算了一维访问集合不得不多绕一圈回到同一个点答案自然偏大。修复方式是读入后用set去重再把K更新成去重后的个数。这个做法既简单又安全后来遇到类似“指定必须访问的点”的题目我都会先下意识去个重。如果你不想写set排序加unique也行。4. 调试实录TLE和WA排查链路全过程4.1 第一次WA我差点怀疑Floyd写错了第一版代码写完样例过了信心满满提交结果第6个测试点WA。我当时的第一反应是Floyd写错了于是先把dist数组输出对照发现从任意点到任意点的最短路完全正确。接着我怀疑是不是路径重复访问导致状态爆炸又把K打印出来看发现样例正好K2重复访问不影响结果。最后是通过对拍找到的问题。我写了一个暴力版本用DFS枚举关键点的全排列每个排列计算相邻关键点最短距离之和加上起点到第一个、最后一个到终点的距离。用随机生成的小图N5、K3对拍暴力程序答案总是比我的DP还小而且小不少。这说明我DP算出来的“最优解”里藏了额外的花费。慢慢排查下来终于定位到去重问题。暴力程序用set自动去重我的DP直接用原始K计算状态把重复的国家当成了不同节点逼着路径额外多访问一次答案自然偏大。修复后对拍DP和暴力结果完全一致。4.2 第二次WAINF加法溢出带来的“负最优解”去重问题解决后我以为稳了结果提交又WA了一组大数据。这次更诡异某些点的答案竟然是负数。我盯着代码想了一会儿立刻意识到是dp[mask][last] dist[keyNode[last]][keyNode[nxt]]溢出问题。当dp[mask][last]和dist都是0x3f3f3f3f时相加结果超过int上限变成负数然后min就把这个负数写进了to。修复方法很简单转移前判断dist是否为INF同时dp[mask][last]已经在上一步过滤过。但这里有个教训用0x3f3f3f3f做INF虽然方便memset但一定要警惕“两个INF相加”这件事。我在其他题目里甚至见过需要判断dp INF之后再继续的情况这套习惯应该在平时刷题时养成。4.3 TLE从vector容器到原生数组的提速我最初实现时用的是vectorvectorint dp(1K, vectorint(K, INF))逻辑完全正确但跑K15的数据已经有点吃力有人可能会疑惑这数据量不是很小吗问题是OJ上可能不止一组测试数据加上输入输出开销vector二维分配的空间零散分布缓存命中率偏低。后来我把dp改成原生二维数组int dp[115][15]瞬间快了不少。再配合一个剪枝当dp[mask][last]已经大于等于当前最优答案ans时后面的转移只可能继续增大花费直接跳过。这个剪枝在K较大时效果明显尤其是当正确答案远小于路径总距离的情况下能砍掉大量无效状态转移。我把调试过程中遇到的问题整理成一张表方便你快速对照问题表现根因修复方式关键节点重复大数据点WA重复点被当成两个独立点读入后用set去重INF加法溢出答案出现负值两个INF相加超过int上限转移前判断wINF再continue运行超时大K数据集卡死vector容器分配局部性差换成原生二维数组并加剪枝4.4 对拍脚本的思路我这次能快速定位问题很大功劳归给对拍。对拍其实很简单写一个暴力程序用小数据范围枚举所有可能路径再写一个数据生成器随机生成N和M以及关键点最后写一个shell循环不断比较暴力程序与DP程序的输出。只要两者不一致就说明DP有bug。暴力程序对于K≤8时完全可行因为K的全排列最多40320个。随机生成图时我会刻意让图不连通或者加入重复关键点这样更容易暴露边界问题。这个方法我已经在几十道题上用过想提高AC率的同学真的建议学一下。5. 复盘这道题给我留下的三点方法论5.1 认出“必须访问某些点”家族题型的统一套路“在图中访问若干指定节点求最小成本”这类题几乎都有一个固定的解题套路先跑Floyd或多次Dijkstra把任意两点最短距离求出来把原图变成完全图然后对指定节点数量做状态压缩DP。这个套路既能解“访问完指定点后到终点”也能解“访问完指定点后回到起点”——后者只是把终点改成起点其他完全一样。如果你在比赛里碰到这种题先观察K的范围。K≤20基本可以放心状压K20就要考虑其他方法比如最小斯坦纳树、Meet in the Middle之类。这道题K15的设计其实就是在明牌告诉你“我就是想让你做状压别用奇奇怪怪的东西”。5.2 动手写代码前先把状态转移写成公式我有一个习惯拿到题先不急着开编辑器先在草稿纸上把DP式子写下来。比如本题的关键式子只有两个一个初始化一个转移。式子写完代码只是翻译工作。很多同学一上手就写for循环写到一半发现状态定义有问题或者转移漏了情况反而更浪费时间。在草稿上想清楚两件事就够了状态包含哪些信息转移需要哪些信息。信息对上了代码自然就顺了。5.3 提交前先做“边界数据自测三连”平时刷题我会在提交前特意构造三组数据一是K0即不需要访问任何关键点二是起点A或终点B就在关键点列表里三是图不连通导致某些关键点之间距离INF。这三组数据都能在几分钟内帮我排查掉一大半低级bug。本题K0的情况如果没有单独处理full - 1会等于0循环里可能访问到未初始化的状态非常危险。最后再分享一个小技巧。对于这类状态转移比较复杂的DP我在不确定的时候会先写记忆化搜索版本就是DFS加数组缓存。搜索版本逻辑直观调试方便确认正确后再改成递推版本追求常数。我这个人比较懒但如果这道题一开始就用搜索版本可能连去重问题都能更早暴露。希望这篇P3753的完整复盘能帮你少踩几个坑刷题路上每个WA都有它的价值。