做题感悟：以前也做过类似的题目，但是这里规定每个地点只能访问 2 次 ，用二进制结果超内存，然后就百度了一下原来用三进制。
解题思路：
大体的思路还是和 TSP 差不多，只是这里一个地点可以最多拜访两次 ，用三进制就可以解决这个问题，但是三进制不如二进制好处理。因为每个地点最多可以拜访两次，so ~> 不可以用Floyd 预处理。先预处理出来三进制的各个状态，以及各个状态的各位的状态。dp[ S ] [ i ] 代表达到状态 S 后到达 i 最小花费。
动态方程： dp [ S + t [ j ] ] [ j ] = min (dp [ S + t [ j ] ] [ j ] , dp[ S ] + d [ i ] [ j ] ) ;
代码：
#include<iostream>
#include<fstream>
#include<iomanip>
#include<ctime>
#include<fstream>
#include<sstream>
#include<stack>
#include<cstring>
#include<cmath>
#include<map>
#include<queue>
#include<vector>
#include<cstdio>
#include<algorithm>
#define INT __int64
using namespace std ;
const double esp = 0.00000001 ;
const int INF = 0x3f3f3f3f ;
const int mod = 1e9 + 7 ;
const int MY = 10 + 10 ;
const int MX = 59049+ 10 ;
int n ,m ;
int t[MY] ,dp[MX][MY] ,d[MY][MY] ,f[MX][MY] ;
void init() // 预处理状态
{
t[0] = 1 ;
for(int i = 1 ;i <= 11 ; ++i)
t[i] = t[i-1] * 3 ;
for(int S = 0 ; S <= 59049 ; ++S)
{
int temp = S ,i = 0 ;
while(temp)
{
f[S][i++] = temp % 3 ;
temp /= 3 ;
}
}
}
void input()
{
int u ,v ,w ;
memset(d ,INF ,sizeof(d)) ;
for(int i = 0 ;i < m ; ++i)
{
scanf("%d%d%d" ,&u ,&v ,&w) ;
u-- ; v-- ;
d[u][v] = d[v][u] = min(d[u][v] ,w) ;
}
}
void DP()
{
int best = INF ;
memset(dp ,INF ,sizeof(dp)) ;
for(int i = 0 ;i < n ; ++i)
dp[t[i]][i] = 0 ;
for(int S = 0 ;S < t[n] ; ++S)
{
bool flag = true ; // 查看是否每个地点都拜访过了
for(int i = 0 ;i < n ; ++i)
{
if(dp[S][i] != INF)
{
for(int j = 0 ;j < n ; ++j)
if(i != j && f[S][j] <= 1 && d[i][j] != INF)
{
int& ans = dp[S+t[j]][j] ;
ans = min(ans ,dp[S][i] + d[i][j]) ;
}
}
if(!f[S][i]) flag = false ;
}
if(flag)
for(int i = 0 ;i < n ; ++i)
best = min(best ,dp[S][i]) ;
}
if(best != INF)
cout<<best<<endl ;
else cout<<"-1"<<endl ;
}
int main()
{
init() ;
while(~scanf("%d%d" ,&n ,&m))
{
input() ;
DP() ;
}
return 0 ;
}