洛谷P10447 最短 Hamilton 路径 题解 & 最小哈密顿路径模板

题目链接：P10447 最短 Hamilton 路径

题目描述：

给定一张 \(n\) 个点的带权无向图，点从 \(0 \sim n-1\) 标号，求起点 \(0\) 到终点 \(n-1\) 的最短 Hamilton 路径。

Hamilton 路径的定义是从 \(0\) 到 \(n-1\) 不重不漏地经过每个点恰好一次。

输入格式：

第一行输入整数 \(n\)。

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

对于任意的 \(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\) 。

注意本题并不是一道很合格的模板题，\(a\) 的额外限制对于常规的状压dp解法是没有任何意义的。

言归正传。本题要求的是节点 \(0\) 到节点 \(n-1\) 的最小哈密顿路径，起点和终点是固定的。

考虑状压dp。记 \(f(S,i)\) 为当前走到 \(i\) ，已经走过了 \(S\) 集合中的点时的最小哈密顿路径长。

初始值 \(f(\{0\},0)=0\) ，即从 \(0\) 出发走过了 \(0\) 的花费，当然为 \(0\) 。答案就是 \(f(U,n-1)\) ，其中 \(U\) 为全集。

考虑转移，记 \(w(i,j)\) 为无向边 \((i,j)\) 的边权，每轮枚举 \(i\,(i \in S)\) ，有 \[ f(S,i) \gets \min_{(j \ne i) \land (j \in S)}\left(f(S,i), \,f(S\setminus\{i\},j) + w(j,i)\right) \] 直接转移即可，时间复杂度 \(O(n^2\cdot2^n)\)

代码：（常数略大，不过很直观的写法，然后因为 \(w(i,j)=w(j,i)\) 就可以随便写）

#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define INF 0x3f3f3f3f3f3f3f3f
typedef long long ll;
template<typename T> void up(T &x, T y) { x < y ? x = y : 0; }
template<typename T> void down(T &x, T y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(1 << 20) + 5)

int n, a[N][22]; ll f[N][22];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    rep(i, 0, n - 1) rep(j, 0, n - 1) cin >> a[i][j];
    memset(f, 0x3f, sizeof(f));f[1 << 0][0] = 0;
    rep(S, 1, (1 << n) - 1)
    {
        rep(i, 0, n - 1) if((S >> i) & 1)
            rep(j, 0, n - 1) if(j != i && ((S >> j) & 1))
                down(f[S][i], f[S ^ (1 << i)][j] + a[i][j]);
    }
    cout << f[(1 << n) - 1][n - 1] << '\n';
    return 0;
}