<—点个赞吧QwQ

宣传一下算法基础课整理{:target=”_blank”}

给定一张 $n$ 个点的带权无向图，点从 $0 \\sim 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\] \\ge a\[x,z\]$。

输出格式

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

数据范围

$1 \\le n \\le 20$
$0 \\le a\[i,j\] \\le 10^7$

输入样例：

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

输出样例：

18

思路

闫氏$\text{DP}$分析法：
状态表示：$f_{i,j}$

• 集合：当前在点$i$，已经过点的集合为$j$的所有方案
• 属性：$\min$

状态计算：

• 设当前点为$i$，已经经过的点集合为$s$
• 如果从$1$过来（$s>>1\&1$成立时），那么距离就是$f_{1,s - (1 << (1 - 1))} + w_{1,i}$
• 如果从$2$过来（$s>>2\&1$成立时），那么距离就是$f_{1,s - (1 << (2 - 1))} + w_{2,i}$
• 如果从$j$过来（$s>>j\&1$成立时），那么距离就是$f_{1,s - (1 << (j - 1))} + w_{j,i}$
• 所以状态转移方程就是$f_{i,s}=\underset{1 \le j \le n~\text{and}~s >> (j - 1) \& 1}\min\lbrace f_{j,s - (1 << (j - 1))} + w_{j,i}\rbrace$

代码

#include <iostream>
#include <cstring>
using namespace std;
const int N = 21,M = 1 << N;
int n;
int g[N][N];
int f[N][M];
int main () {
    cin >> n;
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= n;j++) cin >> g[i][j];
    }
    memset (f,0x3f,sizeof (f));
    f[1][1] = 0;
    for (int k = 0;k < 1 << n;k++) {
        for (int i = 1;i <= n;i++) {
            if (k >> i - 1 & 1) {
                for (int j = 1;j <= n;j++) {
                    if (k >> j - 1 & 1) f[i][k] = min (f[i][k],f[j][k - (1 << i - 1)] + g[j][i]);
                }
            }
        }
    }
    cout << f[n][(1 << n) - 1] << endl;
    return 0;
}