HDU 3001 Travelling （状态压缩/三进制）

Travelling（HDU 3001）

Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 8931 Accepted Submission(s): 2914

Problem Description
After coding so many days,Mr Acmer wants to have a good rest.So travelling is the best choice!He has decided to visit n cities(he insists on seeing all the cities!And he does not mind which city being his start station because superman can bring him to any city at first but only once.), and of course there are m roads here,following a fee as usual.But Mr Acmer gets bored so easily that he doesn’t want to visit a city more than twice!And he is so mean that he wants to minimize the total fee!He is lazy you see.So he turns to you for help.

Input
There are several test cases,the first line is two intergers n(1<=n<=10) and m,which means he needs to visit n cities and there are m roads he can choose,then m lines follow,each line will include three intergers a,b and c(1<=a,b<=n),means there is a road between a and b and the cost is of course c.Input to the End Of File.

Output
Output the minimum fee that he should pay,or -1 if he can’t find such a route.

Sample Input
2 1
1 2 100
3 2
1 2 40
2 3 50
3 3
1 2 3
1 3 4
2 3 10

Sample Output
100
90
7
题目大意：10个点的TSP问题，但是要求每个点最多走两边，不是只可以走一次，所以要用三进制的状态压缩解决这个问题。可以预处理每个状态的第k位是什么。

刚开始用memset初始化，结果一直过不了样例，最后用for手动初始化就过了。。。又一次掉进了memset的大坑里。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 99999999;
int n,m;
int tri[12] = {0,1,3,9,27,81,243,729,2187,6561,19683,59049};//三进制的位权
int dig[59050][11];//dig[state][k_dig]状态state的第k位是多少
int edge[11][11],dp[59050][11];//dp[state][k]为状态state下最后一个点是k的最小距离
int main(){
    for(int i = 0; i < 59050; i++){
        int t = i;
        for(int j = 1;j<=10; j++){
            dig[i][j] = t%3;
            t /= 3;
            if(t == 0)break;
        }
    }
    while(scanf("%d%d",&n,&m)!=EOF){
        for(int i  = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                edge[i][j] = MAXN;
            }
        }
        for(int i = 1; i <= n; i++)edge[i][i] = 0;
        int a,b,c;
        for(int i = 1; i <= m; i++){
            scanf("%d %d %d",&a,&b,&c);
            if(c < edge[a][b]){
                edge[a][b] = edge[b][a] = c;
            }
        }
        for(int state = 0; state < tri[n+1]; state++){
            for(int j = 1; j <= n; j++){
                dp[state][j] = MAXN;
            }
        }
        for(int i = 1; i <= n; i++){
            dp[tri[i]][i] = 0;
        }
        int ans = MAXN;
        for(int state = 0; state < tri[n+1]; state++){
            int visit_all = 1;
            for(int i = 1; i <= n; i++){
                if(dig[state][i] == 0)visit_all = 0;
                if(dp[state][i] == MAXN)continue;
                for(int j = 1; j <= n; j++){
                    if(i == j)continue;
                    if(edge[i][j] == MAXN || dig[state][j] >= 2)continue;
                    int newState = state + tri[j];
                    dp[newState][j] = min(dp[newState][j],dp[state][i]+edge[i][j]);
                }
            }
            if(visit_all){
                for(int j = 1; j <= n; j++){
                    ans = min(ans,dp[state][j]);
                }
            }
        }
        if(ans == MAXN){
            puts("-1");
            continue;
        }
        printf("%d\n",ans);
    }
}










  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
  
67
  
68
  
69
  
70
  
71
  
72
  
73
  
74
  
75
  
76
  
77
 

文章来源: blog.csdn.net，作者：爱玲姐姐，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/jal517486222/article/details/79363319