学步园

题意：你要去旅行，要经过n个点，每个点最多经过两次，每一条路径有一定的消费，求最小消费。

状态设定很简单。dp[i][j],表示i状态下j是最后到达的城市，不过最多经过两次所以要用三进制的状态0表示不经过，1表示经过一次，2表示经过两次。边界条件显然是开始出发的城市设定为0。接着状态转移就好了，注意预处理，要对每个数的三进制的位置的值处理一下。

#include<cstdio>
#include<cstring>
#include<string>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int dig[11]={1,3,9,27,81,243,729,2187,6561,19683,59049};
int bit[59050][11],dp[59050][11],n,m,gp[11][11],maxn[11];
void init()
{
	int j;
	for(int i=0;i<dig[10];i++)
	{
		int tem=i;
		for(j=0;tem;j++)
		{
			bit[i][j]=tem%3;
			tem/=3;
		}
	}
}
void DP()
{
	memset(dp,0x1f1f1f1f,sizeof(dp));
	for(int i=0;i<n;i++)
		dp[dig[i]][i]=0;
	int ans=0x1f1f1f1f,flag=1;
	for(int i=0;i<dig[n];i++)
	{
		flag=1;
		for(int j=0;j<n;j++)
		{
			if(bit[i][j]==0)
			{
				flag=0;
				continue;
			}
			for(int k=0;k<n;k++)
			{
				if(j==k||bit[i][k]==0)continue;
				int tem=i-dig[j];
				if(dp[tem][k]==0x1f1f1f1f||gp[k][j]==-1)continue;
				dp[i][j]=min(dp[i][j],dp[tem][k]+gp[k][j]);
			}
		}		
		if(flag==1)
		for(int j=0;j<n;j++)
		if(dp[i][j]!=0x1f1f1f1f)
		{
			ans=min(ans,dp[i][j]);
		}
	}
	if(ans==0x1f1f1f1f)
		printf("-1\n");
	else
	    printf("%d\n",ans);
}
int main()
{
	int x,y,w;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		
		memset(gp,-1,sizeof(gp));
		init();
		for(int i=0;i<m;i++)
		{
			scanf("%d%d%d",&x,&y,&w);
			if(gp[x-1][y-1]==-1||gp[x-1][y-1]>w)
			gp[x-1][y-1]=gp[y-1][x-1]=w;
		}
		DP();
	}
	return 0;
}