给定一张
n
n
个点的带权无向图，点从 0~n-1 标号，求起点 0 到终点 n-1 的最短Hamilton路径。 Hamilton路径的定义是从 0 到 n-1 不重不漏地经过每个点恰好一次。
输入格式
第一行输入整数
n
n
。
接下来
n
n
行每行
n
n
个整数，其中第
i
i
行第
j
j
个整数表示点
i
i
到
j
j
的距离（记为a[i,j]）。
对于任意的
x,y,z
x,y,z
，数据保证 a[x,x]=0，a[x,y]=a[y,x] 并且 a[x,y] a[y,z]>=a[x,z]。
输出格式
输出一个整数，表示最短Hamilton路径的长度。
数据范围
1≤n≤20
1≤n≤20
0≤a[i,j]≤
10
7
0≤a[i,j]≤107
输入样例：
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
给定一张
n
n
个点的带权无向图，点从 0~n-1 标号，求起点 0 到终点 n-1 的最短Hamilton路径。 Hamilton路径的定义是从 0 到 n-1 不重不漏地经过每个点恰好一次。
输入格式
第一行输入整数
n
n
。
接下来
n
n
行每行
n
n
个整数，其中第
i
i
行第
j
j
个整数表示点
i
i
到
j
j
的距离（记为a[i,j]）。
对于任意的
x,y,z
x,y,z
，数据保证 a[x,x]=0，a[x,y]=a[y,x] 并且 a[x,y] a[y,z]>=a[x,z]。
输出格式
输出一个整数，表示最短Hamilton路径的长度。
数据范围
1≤n≤20
1≤n≤20
0≤a[i,j]≤
10
7
0≤a[i,j]≤107
输入样例：
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
给定一张
n
n
个点的带权无向图，点从 0~n-1 标号，求起点 0 到终点 n-1 的最短Hamilton路径。 Hamilton路径的定义是从 0 到 n-1 不重不漏地经过每个点恰好一次。
输入格式
第一行输入整数
n
n
。
接下来
n
n
行每行
n
n
个整数，其中第
i
i
行第
j
j
个整数表示点
i
i
到
j
j
的距离（记为a[i,j]）。
对于任意的
x,y,z
x,y,z
，数据保证 a[x,x]=0，a[x,y]=a[y,x] 并且 a[x,y] a[y,z]>=a[x,z]。
输出格式
输出一个整数，表示最短Hamilton路径的长度。
数据范围
1≤n≤20
1≤n≤20
0≤a[i,j]≤
10
7
0≤a[i,j]≤107
输入样例：
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
代码： #include<iostream> #include<cstring> #include<algorithm> using namespace std; const int N = 20,M = 1<<20;//M相当于1*（2^20） 也就是十进制的1048576 int n; int f[M][N],weight[N][N]; int main(){ cin >> n; for(int i = 0;i < n;i ) for(int j = 0;j < n;j ) cin >> weight[i][j]; memset(f,0x3f,sizeof f);//无穷大 f[1][0] = 0;//一开始还没有走过任何的路程所以初始化为零 //first我们枚举下所有的状态 for(int i = 0;i < 1<<n;i ) for(int j = 0;j < n;j ) //判断末端整数位个位数字是不是1，右移到个位与上一，判断是0还是1 //如果个位是1就是合法的 if(i >> j & 1) //枚举下整数 //当前状态是i,看下state_k（后面）这个状态 把第j位减去，还没有走到j for(int k = 0;k < n;k ) //判断整数位是否状态为1 if(i - (1<<j) >> k & 1) //如果是1则符合条件 f[i][j] = min(f[i][j],f[i - (1 << j)][k] weight[k][j]); cout << f[(1 << n) - 1][n - 1] << endl; return 0; }
