[HDU - 3001] Travelling

发表于 | 分类于 ， ，
本文字数： 16k

链接

\(\text{HDU - 3001 Travelling}\)

题意

  某一天你有个旅游的计划，这里有\(n\)个城市，你想要访问完\(n\)个城市，开始的时候你可以从任何城市出发，你已经知道了一个二维矩阵\(a[i][j]\)，表示城市\(i\)与城市\(j\)之间互相抵达需要的花费，现在需要计算出访问完\(n\)个城市所需要的最小花费，每个城市最多被允许访问两次。

  数据范围：\(1\leq n\leq 10\).

分析

  首先如果每个点只被允许访问一次，并且指定起点，那么显然是一个最短\(\text{Hamilton}\)路径问题；

  第一次读题，我以为是个不指定起点的最短哈密顿路径问题，然后我就\(O(n^{2})\)枚举起点终点，然后套个\(O(2^n*n^{2})\)的状压\(dp\)，就是\(O(n^4*2^n)\)，后来看题解发现读错题了；对于不指定起点终点的情况来说，可以不用这么做，在指定起点为0的最短哈密顿路径中，我们初始化\(dp[1][0]=0\)，其他为\(\infty\)，那么不指定起点它可能开始的时候在任意位置，我们就初始化，在任意城市为起点的状态为0，即\(dp[1<<pos][pos]_{pos\in [0,n)}=0\)，最后目标是\(\min_{end\in [0,n)}dp[(1<<n)-1][end]\)；

  那么对于这一题来说，其实将最短哈密顿路径的每个点只允许被经过一次，变成了每个点至少经过一次，最多经过2次，那么原来使用2进制，0表示没经过，1表示经过；那么现在使用3进制，0表示没经过，1表示经过一次，2表示经过2次；与2进制不同，3进制不能通过简单位运算取出某一位上的数、对某一位进行取反等一些操作，所以我们需要进行一些预处理，预处理状态\(s\)的第\(k\)位是什么，还需要用到仅走过城市k一次所表示的状态，还需要处理下这个；

  注意代码中的\(status[x]\)，在三进制下是怎么表示的，这里不是说它的意义。

代码

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include<iostream>
#include<string>
#include<queue>
#include<set>
#include<vector>
#include<stack>
#include<map>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;

#define mod 998244353
#define inf 0x3f3f3f3f
#define maxn 500005
#define N 300005
typedef long long ll;

inline int read()
{
    int x = 0;
    int f = 1;
    char c = getchar();
    while (c<'0' || c>'9')
    {    
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0'&&c <= '9')
    {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x*f;
}

int n, m, cost[11][11], dp[60005][11], status[11], t[60005][11];
//预处理，状态s的第i位是t[s][i]，status[i]为，三进制下，n个城市中，只有第i个城市访被问一次所代表的状态
inline void init() {
    status[0] = 1;
    for (int i = 1; i <= 10; i++) {
        status[i] = status[i - 1] * 3;
    }
    for (int s = 0; s <= status[10]; s++) {
        int num = s;
        for (int k = 0; k < 10; k++) {
            t[s][k] = num % 3;
            num /= 3;
        }
    }
}
// 判断x的每一位是不是都大于1,说明任意一个城市都至少访问过一次
inline int is_ok(int x) {
	int cnt = 0;
    while (x) {
        if (!(x % 3)) return 0;
        x /= 3;
        cnt++;
    }
    if (cnt < n) return 0;
    return 1;
}
int main() {
    //freopen("test.in", "r", stdin);
    //freopen("test.out", "w", stdout);
    init();
    while (cin >> n >> m) {
        memset(cost, inf, sizeof(cost));
        int a, b, c;
        for (int i = 0; i < m; i++) {
            cin >> a >> b >> c;
            a--, b--;
            cost[a][b] = cost[b][a] = min(c, cost[b][a]);
        }
        memset(dp, inf, sizeof(dp));
        for (int i = 0; i < n; i++) {
            dp[status[i]][i] = 0;
        }
        for (int s = 0; s < status[n]; s++)
            for (int i = 0; i < n; i++)
                if (t[s][i])
                    for (int j = 0; j < n; j++) {
                        if (i == j) continue;
                        if (t[s][j]) {
                            dp[s][i] = min(dp[s][i], dp[s - status[i]][j] + cost[j][i]);
                        }
                    }
        int ans = inf;
        for (int i = status[n - 1]; i < status[n]; i++) {
            if (is_ok(i)) {
                for (int j = 0; j < n; j++)
                    ans = min(ans, dp[i][j]);
            }
        }
        if (ans >= inf) cout << -1 << endl;
        else
            cout << ans << endl;
    }
}