题目描述 给定一张 n(n≤20) 个点的带权无向图，点从 0~n-1 标号，求起点 0 到终点 n-1 的最短Hamilton路径。 Hamilton路径的定义是从 0 到 n-1 不重不漏地经过每个点恰好一次。
输入 第一行一个整数n。 接下来n行每行n个整数，其中第i行第j个整数表示点i到j的距离（一个不超过10^7的正整数，记为a[i,j]）。 对于任意的x,y,z，数据保证 a[x,x]=0，a[x,y]=a[y,x] 并且 a[x,y]+a[y,z]>=a[x,z]。
输出 一个整数，表示最短Hamilton路径的长度。
样例输入 复制样例数据 4 0 2 1 3 2 0 2 1 1 2 0 1 3 1 1 0 样例输出 4
提示 从0到3的Hamilton路径有两条，0-1-2-3和0-2-1-3。前者的长度为2+2+1=5，后者的长度为1+2+1=4
这是一道状压dp， 首先看i的范围是到i i << n，这个是代表2的n次方， f[x][y]把x转成二进制，从右往左看，为1就代表选了这个点 看个例子，f[9][y] 9的二进制是1001，此时就选择的是0和3 f[i^1<<j][k]这个表示将i的第j位取反，找到它的最大值，然后再加上此时j点和k点的距离
#include <stdio.h> #include <string.h> #include <algorithm> using namespace std; int a[22][22]; int f[1048577][21]; int n; int main() { scanf("%d",&n); for(int i = 0;i < n;i++){ for(int j = 0;j < n;j++){ scanf("%d",&a[i][j]); } } memset(f,0x3f,sizeof(f)); f[1][0] = 0; for(int i = 0;i < 1 << n;i++){ for(int j = 0;j < n;j++){ if(i >> j & 1){//表示i的二进制第j位为1 for(int k = 0;k < n;k++){ if(i >> k & 1){ // 表示i的二进制第k位为1 f[i][j] = min(f[i][j],f[i^1<<j][k]+a[j][k]); } } } } } printf("%d",f[(1<<n)-1][n-1]); return 0; }