题目没有起点限制，且每个节点至少访问1次，最多访问2次，所以用三进制数表示节点的状态（选取情况）。
因为三进制数的每一位是0或1或2，所以预处理z状态S的第j位的数是有必要的。
边界条件：dp[tri[i]][i]=0,表示只访问了i节点时，从i出发最小费用是0。
最后的答案就在所有满足条件的状态中统计dp[S][u]的最小值，枚举u（因为无起点限制）。
1 #include<cstdio>
2 #include<cstring>
3 #include<algorithm>
4 const int INF=0x3f3f3f3f;
5 using namespace std;
6 int n,m,ans;
7 int tri[12]={0,1,3,9,27,81,243,729,2187,6561,19683,59049};//三进制每位为1时对应十进制，如第3位是1，(100)3=9
8 int dig[60000][11];//dig[S][j]状态S的第j位是多少
9 int edge[11][11],dp[60000][11];//3^10=59050
10
11 void init(){
12 for(int i=0;i<59050;i++){
13 int t=i;
14 for(int j=1;j<=10;j++){
15 dig[i][j]=t%3;
16 t/=3;
17 if(t==0) break;
18 }
19 }
20 }
21
22 void solve(){
23 memset(dp,0x3f,sizeof(dp));
24 for(int i=1;i<=n;i++) dp[tri[i]][i]=0;//初始化状态为tri[i]时，从i出发最小费用为0
25 ans=INF;
26 for(int S=0;S<tri[n+1];S++){//状态顺序枚举
27 bool visit_all=1;//标记所有的城市都遍历1次以上
28 for(int u=1;u<=n;u++){
29 if(dig[S][u]==0){
30 visit_all=0;
31 continue;
32 }
33 for(int v=1;v<=n;v++){
34 if(dig[S][v]==0) continue;
35 dp[S][u]=min(dp[S][u],dp[S-tri[u]][v]+edge[u][v]);
36 //有u的集合可以由不含u的集合通过v-u这条边转移而来
37 }
38 }
39 if(visit_all){
40 for(int u=1;u<=n;u++)
41 ans=min(ans,dp[S][u]);//无起点限制，对于满足条件的状态枚举从每个节点出发取最小值
42 }
43 }
44 }
45
46 int main(){
47 init();
48 while(~scanf("%d%d",&n,&m)){
49 memset(edge,0x3f,sizeof(edge));
50 int a,b,c;
51 while(m--){
52 scanf("%d%d%d",&a,&b,&c);
53 edge[a][b]=edge[b][a]=min(edge[a][b],c);
54 }
55 solve();
56 if(ans==INF) ans=-1;
57 printf("%d\n",ans);
58 }
59 return 0;
60 }
