P1171 售货员的难题

状压dp+记忆化搜索

TSP问题：要求从出发经过所有点之后回到的最短路径。

看数据量容易想到状压dp。因为要经过所有点，所以定义状态，二进制上为则表示已经过。定义为状态为，当前在点，从出发到当前状态后，达到最终状态（在点，状态为）的最短路径。

于是显然有转移：。

同时由于最终状态锁死，排除一些不合法情况即可。

#include<bits/stdc++.h>
using namespace std;
int n,g[1010][1010],f[22][2000100];
int read(){
	char ch=getchar();int x=0,f=1;
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch<='9'&&ch>='0'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
int dfs(int x,int zt){
	if(zt&1){
		if(zt!=(1<<n)-1) return f[x][zt]=1e9+7;
		if(x!=1) return f[x][zt]=1e9+7;
		return 0;
	}
	if(f[x][zt]){
		return f[x][zt];
	}
	int res=1e9+7;
	for(int i=1;i<=n;i++){
		if(i==x) continue;
		if(!(zt&(1<<(i-1)))){
			res=min(res,dfs(i,zt|(1<<(i-1)))+g[x][i]);
		}
	}
	f[x][zt]=res;
	return res;
}
int main(){
	n=read();
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			g[i][j]=read();
		}
	}
	printf("%d",dfs(1,0));
	return 0;
}