学步园

状压DP

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int n,ed,a[16][16],f[16][1<<16];
int main(){
	memset(f,127/3,sizeof(f));
	scanf("%d",&n);ed=(1<<(n+1))-1;
	for(int i=0;i<=n;i++)
		for(int j=0;j<=n;j++)
			scanf("%d",&a[i][j]);
	for(int i=0;i<=n;i++)
		for(int j=0;j<=n;j++)
			for(int k=0;k<=n;k++)
				a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
	f[0][0]=0;
	for(int i=0;i<=ed;i++)
		for(int now=0;now<=n;now++)
			for(int next=0;next<=n;next++)
				f[now][i]=min(f[now][i],f[next][(1<<now)^i]+a[next][now]);
	printf("%d",f[0][ed]);
	return 0;		
}