HDU ACM 5418 Victor and World（floyd+状压dp）->TSP（旅行商）有关问题

HDU ACM 5418 Victor and World（floyd+状压dp）->TSP（旅行商）问题
题意：要求从点1开始起，经过所有的点，最终回到1，求经过路程的最小值。

解析：比较经典的旅行商问题： 

1、先用floyd求出所有点之间的最短路O(n^3)。 
2、然后用状态压缩，16位每位上为1表示已走过，0表示没有走过，直接用位运算，表示所有的状态。 
dp[st][j]状态为st，最后一次走的是 j 点的最小值。 
则状态转移方程为： 
dp[st|(1<<(j-1))][j]=min(dp[st|(1<<(j-1))][j],dp[st][i]+d[i][j]) 

有2^16*n个状态，n种转移，所以复杂度为O(2^16*n*n)

#include<iostream>
using namespace std;

#define N 20
#define INF 0x3f3f3f3f

int dp[1<<N][N];             //状态DP
int d[N][N];                 //最短路
int n,m;

void floyd()
{
	int i,j,k;

	for(i=1;i<=n;i++) d[i][i]=0;
	for(k=1;k<=n;k++)
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
				d[i][j]=d[i][j]<d[i][k]+d[k][j]?d[i][j]:d[i][k]+d[k][j];
}

int tsp()
{
	int end,st,i,j,ans;

	memset(dp,INF,sizeof(dp));
	dp[1][1]=0;
	end=(1<<n)-1;

	for(st=1;st<=end;st++)
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
			{
				if(i==j) continue;
				if((1<<(i-1))&st==0 || (1<<(j-1)&st==1)) continue;
				if(dp[st][i]==INF) continue;
				dp[st|(1<<(j-1))][j]=dp[st|(1<<(j-1))][j]<dp[st][i]+d[i][j]?dp[st|(1<<(j-1))][j]:dp[st][i]+d[i][j];
			}
	ans=INF;
	for(i=1;i<=n;i++)
		ans=ans<dp[end][i]+d[i][1]?ans:dp[end][i]+d[i][1]; //加上回到起点
	return ans;
}

int main()
{
	int T,u,v,val,i;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&n,&m);
		memset(d,INF,sizeof(d));
		for(i=0;i<m;i++)
		{
			scanf("%d%d%d",&u,&v,&val);
			d[u][v]=d[u][v]<val?d[u][v]:val;        //注意这里的写法，可能不同方向的值是不一样的
			d[v][u]=d[v][u]<val?d[v][u]:val;
		}
		floyd();
		printf("%d\n",tsp());
	}
    return 0;
}