【题目来源】https://www.luogu.com.cn/problem/P1171【题目描述】某乡有 n 个村庄有一个售货员他要到各个村庄去售货各村庄之间的路程 sᵢⱼ​ 是已知的且 A 村到 B 村与 B 村到 A 村的路大多不同。为了提高效率他从商店出发到每个村庄一次然后返回商店所在的村假设商店所在的村庄为 1他不知道选择什么样的路线才能使所走的路程最短。请你帮他选择一条最短的路。【输入格式】第一行是一个整数表示村庄数 n。接下来 n 行每行 n 个整数第 i 行的第 j 个整数表示 i 到 j 的单向路径的距离 sᵢⱼ​。【输出格式】一行一个整数表示最短的路程。【输入样例】30 2 11 0 22 1 0【输出样例】3【数据范围】对全部的测试数据保证 2≤n≤201≤sᵢⱼ​10^3。【算法分析】● 本题的本质是求有向图的最小权值哈密顿回路Hamilton 回路。算法要求从村庄 1 出发不重复走遍所有村庄最后回到村庄 1求最小的总路程。但是题目给出的n20时全排列有20! ≈ 2.433×10¹⁸种路线就算剪枝也不可能跑完必然超时TLE。下面给出的是 dfs 写法的 80 分代码。#include bits/stdc.h using namespace std; const int inf0x3f3f3f3f; const int N25; int g[N][N]; bool st[N]; int ansinf; int n; // pos: current village (node) // cnt: number of villages visited so far // dis: total distance traveled so far void dfs(int pos,int cnt,int dis) { if(disans) return; if(cntn) { ansmin(ans,disg[pos][1]); return; } for(int i1; in; i) { if(!st[i]) { st[i]true; dfs(i,cnt1,disg[pos][i]); st[i]false; } } } int main() { memset(st,0,sizeof st); cinn; for(int i1; in; i) { for(int j1; jn; j) { cing[i][j]; } } st[1]true; dfs(1,1,0); coutansendl; return 0; } /* in: 3 0 2 1 1 0 2 2 1 0 out: 3 */● 本题洛谷 P1171售货员的难题的标准正解只有用状态压缩 DP 才能 AC。洛谷 P1171售货员的难题是“状态压缩DP 最短 Hamilton回路”的模板题。洛谷 P10447最短 Hamilton 路径是“状态压缩DP 最短 Hamilton路径”的模板题。仅需将洛谷 P10447最短 Hamilton 路径中的代码coutdp[(1n)-1][n-1]endl;修改为如下代码即可得到洛谷 P1171售货员的难题的代码。int ansinf; for(int i0; in; i) { ansmin(ans,dp[(1n)-1][i]g[i][0]); } coutansendl;● 本题核心代码解析1const int N20; → 最多 20 个点20 是状压 DP 的极限2²⁰ ≈ 100 万。2int dp[1N][N]; → 最重要的核心例如dp[state][u] 中的 state二进制 表示哪些点已经走过u 表示当前停在哪个点。dp[state][u] 的值表示走完这些点的最短路径长度。比如dp[1011][3] 表示走过点 0、1、3当前停在点 3 的最短路径的值。dp[10][0]0 表示走过点 0当前停在点 0 的最短路径的值为 0起点。3三层循环状态转移→在所有可能的局面里尝试从每一个当前点走向每一个能走的下一点并记录最短路径。for(int i0; i(1n); i) { // 枚举所有状态 for(int j0; jn; j) { // 枚举当前点 j if(!(i(1j))) continue; // j 没走过跳过 for(int k0; kn; k) { // 枚举下一个点 k if(i(1k)) continue; // k 走过了跳过 int ti|(1k); // 新状态把 k 加进去 dp[t][k]min( dp[t][k],dp[i][j]g[j][k] ); } } }① for(int i0; i(1n); i) → 枚举所有可能的状态。每个 i 是一个二进制数表示哪些点走过了。② for(int j0; jn; j) → 枚举当前停在哪个点 j。③ if( !(i (1j)) ) continue; → 如果状态 i 里没有 j说明 j 还没走过跳过。④ for(int k0; kn; k) → 尝试从 j 走到 kk 是下一个要走的点。⑤ if( i (1k) ) continue; → k 已经走过不能重复走 跳过。⑥ int t i | (1k); → 把 k 加入已走集合得到新状态 t。⑦ dp[t][k] min( ... ) → 从 j 走到 k新路径 旧路径 j 到 k 的距离保留最小值。4cout dp[ (1n) -1 ][n-1] endl; → (1n)-1 等于二进制全 1表示所有点都走过了。n-1 表示最后停在终点。【算法代码状态压缩DP 最短 Hamilton 回路】#include bits/stdc.h using namespace std; const int inf0x3f3f3f3f; const int N20; int dp[1N][N]; int g[N][N]; int n; int main() { cinn; for(int i0; in; i) { for(int j0; jn; j) { cing[i][j]; } } memset(dp,inf,sizeof dp); dp[10][0]0; for(int i0; i(1n); i) { for(int j0; jn; j) { if(!(i(1j))) continue; for(int k0; kn; k) { if(i(1k)) continue; int ti|(1k); dp[t][k]min(dp[t][k],dp[i][j]g[j][k]); } } } //coutdp[(1n)-1][n-1]endl; int ansinf; for(int i0; in; i) { ansmin(ans,dp[(1n)-1][i]g[i][0]); } coutansendl; return 0; } /* in: 3 0 2 1 1 0 2 2 1 0 out: 3 */【参考文献】https://blog.csdn.net/hnjzsyjyj/article/details/161041041https://blog.csdn.net/hnjzsyjyj/article/details/161025792https://www.luogu.com.cn/problem/P1713https://www.cnblogs.com/yinyuqin/p/14028156.htmlhttps://www.cnblogs.com/tuchen/p/13829388.htmlhttps://www.cnblogs.com/LJB666/p/11223989.htmlhttps://www.cnblogs.com/linxiaoxu/p/17679355.html