AcWing-91-最短哈密顿路径

2021-01-26 · 106次阅读 · 原创 · 数据结构与算法

#题解 #动态规划 #位运算

问题

给定一张 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] ≤ 10^7$

输入样例：

输出样例：

思路

动态规划。状态转移方程如下

$dp[i][j]=\min_{0\le k\le n}\{dp[i][j],dp[i-(1<<j)][k]+weight[k][j]\}$

i为由二进制表示的状态集合，例{0,1,4}表示为 $i=10011_b=19$ ，j表示当前所在的点的位置。

i-(1<<j)表示当前状态集合去除掉j状态。

则此为状态压缩dp。

题解

#include<iostream>
#include<cstring>

using namespace std;

const int N = 20, M = 1 << 20;
int weight[N][N], dp[M][N];
int n;

int main() {
    //输入
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> weight[i][j];
        }
    }

    memset(dp, 0x3f, sizeof(dp));    //初始化dp
    dp[1][0] = 0;   //初态

    for (int i = 0; i < 1 << n; i++)
        for (int j = 0; j < n; j++)
            if (i >> j & 1) //状态i的第j位是否使用
                for (int k = 0; k < n; k++) //i - (1 << j)表示状态i中去除状态j后的状态
                    if (i - (1 << j) >> k & 1) dp[i][j] = min(dp[i][j], dp[i - (1 << j)][k] + weight[k][j]);

    cout << dp[(1 << n) - 1][n - 1] << endl;

    return 0;
}

标题：	AcWing-91-最短哈密顿路径
链接：	https://www.fightingok.cn/detail/30
更新：	2022-09-18 22:32:46
版权：	本文采用 CC BY-NC-SA 3.0 CN 协议进行许可