DDOSvoid's Blog

hdu 3001 Travelling

发表于 分类于
本文字数： 1.4k 阅读时长 ≈ 1 分钟

题目描述

http://acm.hdu.edu.cn/showproblem.php?pid=3001

三进制TSP问题

Solution

我们拿三进制记录一下目前去过了哪些城市，上一个城市是哪即可

时间复杂度 $O(3^n n^2)$ 

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
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#define maxn 11
#define maxm 60000
#define INF 1000000000
using namespace std;

int n, m, g[maxn][maxn];

int pow3[maxn], tri[maxm][maxn]; 
void init() { pow3[0] = 1; 
    for (int i = 1; i < maxn; ++i) pow3[i] = pow3[i - 1] * 3;
    for (int i = 0; i < maxm; ++i) {
        int st = i; 
        for (int j = 1; j < maxn; ++j) {
            tri[i][j - 1] = st % 3;
            st /= 3;
        }
    }
}           

int f[maxm][maxn]; 

void work() {
    int M = pow3[n] - 1;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j) g[i][j] = INF;
    for (int i = 0; i <= M; ++i)
        for (int j = 1; j <= n; ++j) f[i][j] = INF; 
    for (int i = 1; i <= m; ++i) {
        int x, y, z; cin >> x >> y >> z; 
        g[x][y] = g[y][x] = min(g[x][y], z); 
    }
    for (int i = 1; i <= n; ++i) f[pow3[i - 1]][i] = 0; 
    for (int S = 0; S <= M; ++S) 
        for (int i = 1; i <= n; ++i) {
            if (!tri[S][i - 1]) continue;
            for (int j = 1; j <= n; ++j) {
                if (tri[S][j - 1] == 2) continue;
                f[S + pow3[j - 1]][j] = min(f[S + pow3[j - 1]][j], f[S][i] + g[i][j]);
            }
        }
    int ans = INF;
    for (int S = 1; S <= M; ++S) {
        bool F = 1; 
        for (int i = 1; i <= n; ++i)
            if (!tri[S][i - 1]) F = 0;
        if (!F) continue;
        for (int i = 1; i <= n; ++i) ans = min(ans, f[S][i]);
    }
    if (ans == INF) cout << -1 << endl;
    else cout << ans << endl; 
}

int main() { init();
    while (cin >> n >> m) work(); 
    return 0;
}