【题目来源】
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]=0，a[x,y]=a[y,x] 并且 a[x,y]+a[y,z]≥a[x,z]。
【输出格式】
输出一个整数，表示最短 Hamilton 路径的长度。
【输入样例】
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
【输出样例】
18
【数据范围】
对于所有测试数据满足 1≤n≤20，0≤a[i,j]≤10^7。
【算法分析】
● 本题代码是最短 Hamilton 路径 / TSP 问题的经典解法。
● 核心代码解析
（1）const int N=20; → 最多 20 个点，20 是状压 DP 的极限（2²⁰ ≈ 100 万）。
（2）int dp[1<<N][N]; → 最重要的核心！
例如，dp[state][u] 中的 state（二进制） 表示哪些点已经走过，u 表示当前停在哪个点。dp[state][u] 的值表示走完这些点的最短路径长度。比如，dp[1011][3] 表示走过点 0、1、3，当前停在点 3 的最短路径的值。dp[1<<0][0]=0表示走过点 0，当前停在点 0 的最短路径的值为 0（起点）。
（3）三层循环（状态转移）→在所有可能的局面里，尝试从每一个当前点，走向每一个能走的下一点，并记录最短路径。
for(int i=0; i<(1<<n); i++) { // 枚举所有状态 for(int j=0; j<n; j++) { // 枚举当前点 j if(!(i&(1<<j))) continue; // j 没走过，跳过 for(int k=0; k<n; k++) { // 枚举下一个点 k if(i&(1<<k)) continue; // k 走过了，跳过 int t=i|(1<<k); // 新状态：把 k 加进去 dp[t][k]=min( dp[t][k],dp[i][j]+g[j][k] ); } } }① for(int i=0; i<(1<<n); i++) → 枚举所有可能的状态。每个 i 是一个二进制数，表示哪些点走过了。
② for(int j=0; j<n; j++) → 枚举当前停在哪个点 j。
③ if( !(i & (1<<j)) ) continue; → 如果状态 i 里没有 j，说明 j 还没走过，跳过。
④ for(int k=0; k<n; k++) → 尝试从 j 走到 k，k 是下一个要走的点。
⑤ if( i & (1<<k) ) continue; → k 已经走过，不能重复走， 跳过。
⑥ int t = i | (1<<k); → 把 k 加入已走集合，得到新状态 t。
⑦ dp[t][k] = min( ... ) → 从 j 走到 k，新路径 = 旧路径 + j 到 k 的距离，保留最小值。
（4）cout << dp[ (1<<n) -1 ][n-1] << endl; → (1<<n)-1 等于二进制全 1，表示所有点都走过了。n-1 表示最后停在终点。
【算法代码】
#include <bits/stdc++.h> using namespace std; const int inf=0x3f3f3f3f; const int N=20; int dp[1<<N][N]; int g[N][N]; int n; int main() { cin>>n; for(int i=0; i<n; i++) { for(int j=0; j<n; j++) { cin>>g[i][j]; } } memset(dp,inf,sizeof dp); dp[1<<0][0]=0; for(int i=0; i<(1<<n); i++) { for(int j=0; j<n; j++) { if(!(i&(1<<j))) continue; for(int k=0; k<n; k++) { if(i&(1<<k)) continue; int t=i|(1<<k); dp[t][k]=min(dp[t][k],dp[i][j]+g[j][k]); } } } cout<<dp[(1<<n)-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/161025792
https://www.luogu.com.cn/problem/solution/P10447
