动态规划训练之七

状压模板题，不多述，复习一下而已

code：

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
using namespace std;
const int maxn=20;
int map[maxn][maxn],num,n,ans,nums;
int f[maxn][1<<18];
 
void dp(){
	memset(f,0x3f,sizeof(f));
	for(int i=1;i<=n;i++)f[i][1<<(i-1)]=map[0][i];
	nums=(1<<n)-1;
	for(int i=0;i<=nums;i++)//枚举所有可能的状态；
		for(int j=1;j<=n;j++)
			if(i&(1<<(j-1))) //枚举当前状态下到了第j个结点 
				for(int k=1;k<=n;k++) {//从j之k,找出到k的最优值。 
				  if((i&(1<<(k-1)))==0) //如果第k结点还到，那么到达k,并更新其值。
				  	f[k][i|(1<<(k-1))] =min(f[k][i|(1<<(k-1))],f[j][i]+map[j][k]);
				}
	ans=1<<20;
	for(int i=1;i<=n;i++)
		ans=min(ans,f[i][nums]+map[i][0]);
	cout<<ans<<endl;
}
int main(){
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
	cin>>n;
	n--;
	for(int i=0;i<=n;i++)
		for(int j=0;j<=n;j++)
			cin>>map[i][j];
		dp();					
	return 0;	
}