题目描述
给定一张 n 个点的带权无向图,点从 0∼n−1 标号,求起点 0 到终点 n−1 的最短 Hamilton 路径。
Hamilton 路径的定义是从 0 到 n−1 不重不漏地经过每个点恰好一次。
1≤n≤20,0≤a[i,j]≤1e7
输入:
第一行输入整数 n。
接下来 n 行每行 n 个整数,其中第 i 行第 j 个整数表示点 i 到 j 的距离(记为 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 路径的长度。
样例
输入:
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
算法
(状态压缩) $O((n^2)*(2^n))$
可以使用递归,直接暴力计算。
但是n<=20,肯定超时
于是我们想到了可以把当前情况使用 状态压缩 记录下来,即 状压
将每个点是否被遍历过使用01记录下来,
再用二进制将它变成一个整数。
因为1<<20不会爆,所以算法可以实现。
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N=29;
int w[N][N],f[1<<20][N],n;
int main(){
cin>>n;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
cin>>w[i][j];
memset(f,0x3f,sizeof(f));
f[1][0]=0;
for(int i=1;i<1<<n;i++)
for(int j=0;j<n;j++)if(i>>j&1)
for(int k=0;k<n;k++)if((i^1<<j)>>k&1)
f[i][j]=min(f[i][j],f[i^1<<j][k]+w[k][j]);
cout<<f[(1<<n)-1][n-1];
return 0;
}