【状压DP】旅行商问题

给定一张带权有向图，要求从顶点0出发，经过每个结点恰好一次后再返回0，求边权和的最小值。

2<=n<=15

0<=d(i,j)<=1000

样例

5 8
0 1 3
0 3 4
1 2 5
2 0 4
2 3 5
3 4 3
4 0 7
4 1 6

dp[S][U]=min{dp[S∪{V}][V]+d(U,V)|V∉S&&d(U,V)!=INF},

d[(1<<n)-1][0]=0.

O(2^n*n^2)

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 16
#define INF 214748364
#define M 250
int n,m;
int v[M<<1],w[M<<1],first[N],next[M<<1],en;
void AddEdge(int U,int V,int W)
{
	v[++en]=V;
	w[en]=W;
	next[en]=first[U];
	first[U]=en;
}
int dp[(1<<N)+1][N];
int f(int S,int U)
{
	if(dp[S][U]!=-1) return dp[S][U];
	if(S==(1<<n)-1&&(!U)) return dp[S][U]=0;
	int res=INF;
	for(int i=first[U];i;i=next[i])
	  if(!(S>>v[i]&1))
	    res=min(res,f(S|(1<<v[i]),v[i])+w[i]);
	return dp[S][U]=res;
}
int main()
{
	int x,y,z;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i)
	  {
	  	scanf("%d%d%d",&x,&y,&z);
	  	AddEdge(x,y,z);
	  }
	memset(dp,-1,sizeof(dp));
	printf("%d
",f(0,0));
	return 0;
}