最短哈密顿路径（位运算+dp）
原题链接：https://www.acwing.com/problem/content/description/93/
题意：求从点0到点n-1的最短哈密顿路径，即0~n-1这n个点每个点必须且只能经过一次。
起点为0，终点为n-1，问你最短路径长度
题解： 设f[i][j]表示从0开始，途中经过了i这个二进制表示的数中位为1的所有点后，到达了j这个点的最短路径
举个例子i为111001110，那么这时候第1，2，3和6,7,8这6个点就经历过了。这时候到达了j这个点，其中j可能是123678中任意一个
那么我们需要考虑：在到达j这个点之前，到达的点是k，即到达f[i][j]这个状态的时候我们先到达了
那么
代码：
#include<bits/stdc++.h>
using namespace std;
const int N = 21;
int a[N][N];
int f[1 << N][N];
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;
int len = 1 << n;
for(int i = 1; i < len; 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) //去掉j这个点后，如果k这个点存在，这个状态才会存在
f[i][j] = min(f[i][j], f[i - (1 << j)][k] + a[k][j]);
printf("%d\n", f[(1 << n) - 1][n - 1]);
return 0;
}
查看12道真题和解析
投递萤石等公司10个岗位
