题面

大秦 为你打开 题目传送门

题目翻译：

有 $n$ 个地方（标号 $1$ 到 $n$ ）要从标号为 $0$ 的地方出去，经过所有的地方之后回来，求最短的时间，输入 $(n+1)$ 的矩阵 $a$，$a[i][j]$表示顶点 $i$ 到顶点 $j$ 所需要的时间。

第一行输入一个整数 $n(1≤n≤10)$ 。

接下来 $𝑛+1$ 行，每行 $n+1$ 个整数，表示矩阵中的元素，矩阵中的元素在区间 $[1,1000]$ 内。

思路

这道题我们要同时兼顾经过了哪些点（因为要经过所有点），所以最好的方式就是把经过的点存下来，但是想要在递推过程中记录这些东西，有点困难。发现数据范围只有 $10$ 不难想到状压DP。因为状压DP是基于集合的DP，每经过一个点，就在状态中标记。

另外要处理某两个点之间的最短路，因为只有 $10$ 的数据范围，所以这个可以用 floyd 水水过。

此外，在标记每一个点的是否经过，还有一个很重要的元素是最后一个点是哪里。就比如说：

1
2
1 4 3 2 
1 2 3 4

同样是经过了点 1 2 3 4 但是顺序不一样，路程就可能有变化，另外我们要从最后一个经过的点往后走，所以也是要记录最后一个经过的点的重要原因。

代码

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
#include<bits/stdc++.h>
using namespace std;

int n;
int a[20][20];

int dp[4010][20];

void Input() {
    scanf("%d", &n);
    n++;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            scanf("%d", &a[i][j]);
        }
    }
}

void Init() {
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            for(int k = 0; k < n; k++) {
                a[i][j] = min(a[i][j], a[i][k] + a[k][j]);
            }
        }
    }
}

void Work() {
    Init();
    memset(dp, -1, sizeof(dp));
    dp[1][0] = 0;
    for(int mask = 0; mask < (1 << n); mask++) {
        for(int ed = 0; ed < n; ed++) {
            if(dp[mask][ed] == -1) continue;
            for(int to = 0; to < n; to++) {
                if((1 << to) & mask) continue;
                int nmask = mask | (1 << to);
                if(dp[nmask][to] == -1 || dp[nmask][to] > dp[mask][ed] + a[ed][to]) {
                    dp[nmask][to] = dp[mask][ed] + a[ed][to];
                }
            }
        }
    }
    int ans = 1e9;
    for(int i = 1; i < n; i++) {
        ans = min(ans, dp[(1 << n) - 1][i] + a[i][0]);
    }
    printf("%d\n", ans);
}

int main() {
    Input();
    Work();
    return 0;
}