P10447 最短 Hamilton 路径 题解

题目传送门

题意：给定一张有向带权图（\(n \le 20\)）求点 \(0\) 到点 \(n-1\) 的最短哈密顿路径。

这是一道状压 DP 模板题。在状态压缩 DP 中，我们将一个集合压成一个二进制数。

设 \(f_{u,i}\) 为已经走了集合 \(u\) 中的节点，且现在在点 \(i\) 的最短路。枚举路径上 \(i\) 的前一个点 \(j\) 进行转移。

时间复杂度 \(O(n^2 2^n)\)。

#include <bits/stdc++.h>
using namespace std;
typedef unsigned int uint;

template<typename T>
void cmin(T &x, T y) {
    x = min(x, y);
}

const int N = 20;

int n;
int dis[N][N];

int f[1 << N][N];

int main() { ios::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> dis[i][j];

    uint tot = (1 << n) - 1;
    memset(f, 0x3f, sizeof f);
    f[1][0] = 0;
    for (uint u = 0; u <= tot; u++)
        for (int i = 0; i < n; i++)
            if (u & (1 << i))
                for (int j = 0; j < n; j++)
                    if ((u ^ (1 << i)) & (1 << j))
                        cmin(f[u][i], f[u ^ (1 << i)][j] + dis[j][i]);
    cout << f[tot][n-1] << endl;
    return 0;
}