Travelling

题意：
n 个城市已及 m 条路 以及对应路费 c，要求遍历所有城市最少的路费，每个城市不能超过2次。

思路：
三进制位表示一个城市被走过的次数，三进制没有位运算，可以预处理三进制位每一位的权值以及每个十进制数的三进制表示。
状态方程：表示访问中所有的点后最后到达城市（感觉紫书上对旅行商的解析不太好）
转移方程：

Code:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include <vector>
#include<map>
#include<set>
#include<utility>
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
inline ll read() {
    ll s = 0, w = 1;
    char ch = getchar();
    while (ch < 48 || ch > 57) {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch >= 48 && ch <= 57)
        s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
int n,m;
int bit[12]={0,1,3,9,27,81,243,729,2187,6561,19683,59049};
//三进制每一位的权值 
int tri[60000][11];//记录每个数的三进制数 
int dp[11][60000];
int graph[11][11];
void make_trb() {
    for(int i=0;i<59050;++i) {
        int t=i;
        for(int j=1;j<=10;++j) {
            tri[i][j]=t%3;
            t/=3;
        }
    }//共3^10=59049种状态 
} 
int comp_dp() {
    int ans=inf;
    memset(dp,inf,sizeof dp);
    for(int i=0;i<=n;++i)//初始化超人把他送到任意位置开始时的值 
        dp[i][bit[i]]=0;
    for(int i=0;i<bit[n+1];++i) {
        int flag=1;//表示每个城市都遍历了至少一次 
        for(int j=1;j<=n;++j) {
            if(tri[i][j]==0) {
                flag=0;
                continue;
            }
            if(i==j) continue;
            for(int k=1;k<=n;++k) {
                int l=i-bit[j];
                if(tri[i][k]==0) continue;
                dp[j][i]=min(dp[j][i],dp[k][l]+graph[k][j]);
            }//枚举下到达k的点 
        }//历遍所有终点 
        if(flag)
            for(int j=1;j<=n;++j)
                ans=min(ans,dp[j][i]);
    }
    return ans;
} 
int main() {
    make_trb();
    while(cin>>n>>m) {
        memset(graph,inf,sizeof graph);
        while(m--) {
            int a,b,c;
            cin>>a>>b>>c;
            if(c<graph[a][b]) graph[a][b]=graph[b][a]=c;//去重边 
        }
        int ans=comp_dp();
        if(ans==inf) cout<<"-1"<<endl;
        else cout<<ans<<endl;
    }
    return 0;
}