HDU - 3001 Travelling （狀態壓縮）

HDU - 3001 Travelling （狀態壓縮）

題目大意：有一個人要去旅游，他想要逛遍所有的城市，但是同一個城市又不想逛超過2次。現在給出城市之間的來往路費，他可以選擇任意一個點為起點。問逛遍所有城市的最低路費是多少

解題思路：這題和POJ - 3311 Hie with the Pie相似
這裡的狀態標記要用三進制數來表示，就可以表示每個城市去過的次數了
設dp[i][state]為現在在i城市，逛過的城市狀態為state的最低路費
狀態轉移方程：
dp[i][S ＋ i城市標記] = min(dp[i][S + i城市標記], dp[j][S] + cost[j][i])
注意給邊判重
又用了隊列。。。

#include
#include
#include
#include
using namespace std;
#define maxn 15
#define INF 0x3f3f3f3f
#define maxs 60000

struct DP {
    int num, state;
}start[maxn];

int n, m;
int cost[maxn][maxn];
int dp[maxn][maxs];
int mod[maxn];

void init() {
    int x, y, z;
    memset(cost, 0x3f, sizeof(cost));
    for(int i = 0; i < m; i++) {
        scanf(%d%d%d, &x, &y, &z);
        cost[x-1][y-1] = cost[y-1][x-1] = min(cost[x-1][y-1], z);
    }
    memset(dp, 0x3f, sizeof(dp));
    for(int i = 0; i < n; i++) {
        dp[i][mod[i]] = 0;
        start[i].num = i;
        start[i].state = mod[i];
    }
}

void solve() {

    queue q;
    for(int i = 0; i < n; i++) 
        q.push(start[i]);
    int ans = INF;
    while(!q.empty()) {
        DP t = q.front();
        q.pop();
        for(int i = 0; i < n; i++) {
            if(i == t.num || cost[i][t.num] == INF)
                continue;
            if(!i && t.state % 3 == 2)
                continue;
            if(i && ( (t.state % mod[i+1]) - (t.state % mod[i]) ) / mod[i] == 2)
                continue;

            if(dp[i][t.state + mod[i]] > dp[t.num][t.state] + cost[t.num][i]) {
                dp[i][t.state + mod[i]] = dp[t.num][t.state] + cost[t.num][i];
                DP tt;
                tt.num = i;
                tt.state = t.state + mod[i];
                q.push(tt);

                bool flag = false;
                int tmp = t.state + mod[i];
                if(dp[i][tmp] < ans) {
                    for(int j = 0; j < n; j++)
                        if(tmp % 3 == 0) {
                            flag = true;
                            break;
                        }
                        else {
                            tmp /= 3;
                        }
                    if(!flag) 
                        ans = dp[i][t.state + mod[i]];
                }
            }
        }
    }
    if(ans == INF)
        ans = -1;
    printf(%d
, ans);
}

void begin() {
    mod[0] = 1;
    for(int i = 1; i < 12; i++)
        mod[i] = mod[i - 1] * 3;
}

int main() {
    begin();
    while(scanf(%d%d, &n, &m) != EOF) {
        init();
        solve();
    }
    return 0;
}