来源：AcWing

题目

给定一张 n 个点的带权无向图，点从 0 ~ n - 1 标号，求起点 0 到终点 n - 1 的最短 Hamilton 路径。 Hamilton 路径的定义是从 0 到 n - 1 不重不漏地经过每个点恰好一次。

输入格式

第一行输入整数n。

接下来n行每行n个整数，其中第i行第j个整数表示点i到j的距离（记为a[i,j]）。

对于任意的x,y,z，数据保证 a[x,x]=0，a[x,y]=a[y,x] 并且 a[x,y]+a[y,z]>=a[x,z]。

输出格式

输出一个整数，表示最短Hamilton路径的长度。

数据范围

1 ≤ n ≤ 20
0 ≤ a[i,j] ≤ 107

输入样例

1
2
3
4
5
6
5
0 2 4 5 1
2 0 6 5 3
4 6 0 8 3
5 5 8 0 5
1 3 3 5 0

输出样例

1
18

分析

用状态压缩的图论问题

先来看集合f[i][j]表示所有从 0 走到 j，走的路径为 i 的所有路径，存储的值为最小值。其中 i 表示方案集合：如果有三个点 0 1 2，i = 6表示1 1 0即表示 0 没走过，1 2走过。j 表示走法为 i 的终点

状态转移方程：只考虑最后一步，取最后一步的点为 k，将路径分为 0 ~ k，k ~ j，那么就可以将f[i][j]分解成 从 0 ~ k （不含 j ）的最短路径 + w[k][j]，就可以得到方程：f[i][j] = f[i ^ (1 << j)][k] + w[k][j]

代码

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

int f[1 << 20][21];
int w[21][21];

int main() {
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            scanf("%d", &w[i][j]);
    memset(f, 0x3f, sizeof f);
    
    f[1][0] = 0;	// 0~0状态为1，最短距离为0
    for(int i = 1; i < 1 << n; i++)	// 枚举所有方案集合
        for(int j = 0; j < n; j++)	// 枚举所有终点
            if(i >> j & 1)	// 如果j在方案集合里，即走过j这个点
                for(int k = 0; k < n; k++)	// 把j作为终点，枚举k
                    if(i ^ (1 << j) >> k & 1)	// 如果j不属于i且k属于i（可以省略判断）
                        f[i][j] = min(f[i][j], f[i ^ (1 << j)][k] + w[k][j]);
                        
    printf("%d", f[(1 << n) - 1][n - 1]);	// 结果为走过所有点的终点为n-1的值
    return 0;
}