【题目来源】https://www.luogu.com.cn/problem/P10447【题目描述】给定一张 n 个点的带权无向图点从0∼n−1标号求起点 0 到终点 n−1 的最短 Hamilton 路径。Hamilton 路径的定义是从 0 到 n−1 不重不漏地经过每个点恰好一次。【输入格式】第一行输入整数 n。接下来 n 行每行 n 个整数其中第 i 行第 j 个整数表示点 i−1 到 j−1 的距离记为 a[i−1,j−1]。对于任意的 x,y,z数据保证 a[x,x]0a[x,y]a[y,x] 并且 a[x,y]a[y,z]≥a[x,z]。【输出格式】输出一个整数表示最短 Hamilton 路径的长度。【输入样例】50 2 4 5 12 0 6 5 34 6 0 8 35 5 8 0 51 3 3 5 0【输出样例】18【数据范围】对于所有测试数据满足 1≤n≤200≤a[i,j]≤10^7。【算法分析】● 本题代码是最短 Hamilton 路径 / TSP 问题的经典解法。● 核心代码解析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 表示最后停在终点。【算法代码】#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; return 0; } /* in: 5 0 2 4 5 1 2 0 6 5 3 4 6 0 8 3 5 5 8 0 5 1 3 3 5 0 out: 18 */【参考文献】https://blog.csdn.net/hnjzsyjyj/article/details/161025792https://www.luogu.com.cn/problem/solution/P10447