题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3001
题意：
有n个城市，m条双向道路，每条道路走一次需要花费路费v。你可以将任意一个城市作为起点出发，然后遍历每一个城市，并保证同一个城市最多经过2次。问你遍历这些城市的最小费用是多少。
题解：
传统的TSP问题中，每个城市只能经过一次，做法为三重for循环，分别枚举城市的state、现在所处位置i、下一步要到达的城市j。
核心Code：
memset(dp,-,sizeof(dp));
dp[<<start][start]=;
for(int state=;state<(<<n);state++)
{
for(int i=;i<n;i++)
{
if(dp[state][i]!=-)
{
for(int j=;j<n;j++)
{
if(i!=j && !((state>>j)&))
{
if(dp[state|(<<j)][j]==- || dp[state|(<<j)][j]>dp[state][i]+dis[i][j])
{
dp[state|(<<j)][j]=dp[state][i]+dis[i][j];
}
}
}
}
}
}
在这道题中，与传统TSP的唯一区别是每个城市最多经过的次数由1次变为了2次。那么表示每座城市的状态state也应该相应改为用三进制数表示，每一位上的数字代表对应城市已经经过的次数。
所以把所有的二进制改为三进制就好啦 (￣▽￣)~*
注：不用对于每一个起点分别求一次dp，会T。。。在开始要把所有的dp[update(0, i)][i] = 0
AC Code：
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <queue>
#define MAX_N 15
#define MAX_S 60000
#define INF 100000000 using namespace std; const int POW[]={,,,,,,,,,,,,,,}; int n,m;
int a,b,v;
int ans;
int dis[MAX_N][MAX_N];
int dp[MAX_S][MAX_N]; void init()
{
for(int i=;i<n;i++)
{
for(int j=;j<n;j++)
{
dis[i][j]=INF;
if(i==j) dis[i][j]=;
}
}
} void read()
{
for(int i=;i<m;i++)
{
cin>>a>>b>>v;
dis[a-][b-]=min(dis[a-][b-],v);
dis[b-][a-]=min(dis[b-][a-],v);
}
} int query(int a,int k)
{
return a/POW[k]%;
} int update(int a,int k)
{
return a+POW[k];
} bool check(int state)
{
for(int i=;i<n;i++)
{
if(query(state,i)==) return false;
}
return true;
} void solve()
{
ans=INF;
memset(dp,-,sizeof(dp));
for(int i=;i<n;i++)
{
dp[update(,i)][i]=;
}
for(int state=;state<POW[n];state++)
{
for(int i=;i<n;i++)
{
if(dp[state][i]!=-)
{
for(int j=;j<n;j++)
{
if(i!=j && query(state,j)<)
{
int nex=update(state,j);
if(dp[nex][j]==- || dp[nex][j]>dp[state][i]+dis[i][j])
{
dp[nex][j]=dp[state][i]+dis[i][j];
}
}
}
if(check(state)) ans=min(ans,dp[state][i]);
}
}
}
} void print()
{
if(ans==INF) cout<<-<<endl;
else cout<<ans<<endl;
} int main()
{
while(cin>>n>>m)
{
init();
read();
solve();
print();
}
}