acwing91：最短哈密顿路径

(n)个点的带权无向图，编号(0sim n-1)，求起点(0)到终点(n-1)的最短哈密顿路径，哈密顿路径定义是从(0)到(n-1)不重复的经过每个点恰好一次

[f[i][j]表示状态为i，现在处于j点的最短路\ 边界f[1,0]=0~~~ans=f[(1<<n)-1,n-1]\ f[i][j]=min{f[i~xor~(1<<j),k]+w[k,j]}(0le k<n,((1>>j)&1)=1)\ ]

(j)只能被恰好经过一次，所以一定是刚刚经过的，故上一时刻“被经过的状态”对应二进制数的第(j)位赋值为(0)，也就是(i~xor~(1<<j))。另外，上一时刻所处位置可能是(i~xor~(1<<j))中任意一个是(1)的数位(k)，从(k)到(j)需要(w[k][j])的代价

#include<cstdio>
#include<cstring>
#define N 20
using namespace std;
int n,w[N][N],f[1<<N][N];
inline int min(int a,int b){return a < b ? a : b;}
int main(){
	scanf("%d",&n);
	for(int i = 0;i < n;++i)
		for(int j = 0;j < n;++j)
			scanf("%d",&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]);
	printf("%d",f[(1<<n) - 1][n - 1]);
}