洛谷P1433 吃奶酪 题解

题目链接：P1433 吃奶酪

题意：

房间里放着 \(n\) 块奶酪。一只小老鼠要把它们都吃掉，问至少要跑多少距离？老鼠一开始在 \((0,0)\) 点处。

提示：对于两个点 \((x_1,y_1)\)，\((x_2, y_2)\)，两点之间的距离公式为 \(\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}\)。

输入格式：

第一行有一个整数，表示奶酪的数量 \(n\)。

第 \(2\) 到第 \((n + 1)\) 行，每行两个实数，第 \((i + 1)\) 行的实数分别表示第 \(i\) 块奶酪的横纵坐标 \(x_i, y_i\)。

输出格式：

输出一行一个实数，表示要跑的最少距离，保留 \(2\) 位小数。

数据范围：

对于全部的测试点，保证 \(1\leq n\leq 15\)，\(|x_i|, |y_i| \leq 200\)，小数点后最多有 \(3\) 位数字。

注意到 \(n \le 15\) ，考虑状压dp。

显然我们不会重复走到同一个奶酪的位置。同时因为两点之间线段最短，绕路一定不优。

于是这就是一个最小哈密顿路径的板子了，参考 最小哈密顿路径模板 。

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

代码：

#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 << 16) + 15)

int lowbit(int x) { return x & (-x); }
#define ctz(x) __builtin_ctz(x)
#define sq(x) ((x) * (x))

int n;
double x[20], y[20], f[N][20], e[20][20];
double calc(int a, int b)
{
    if(a == b) return 0;
    return sqrt(sq(x[a] - x[b]) + sq(y[a] - y[b]));
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cout << fixed << setprecision(2);
    cin >> n; ++n; x[0] = y[0] = 0.0; const int U = (1 << n) - 1;
    rep(i, 1, n - 1) cin >> x[i] >> y[i];
    rep(i, 0, n - 1) rep(j, 0, n - 1) { e[i][j] = calc(i, j); }
    rep(S, 0, U) rep(i, 0, n - 1) f[S][i] = 1e23;
    f[1][0] = 0;
    rep(S, 2, U)
    {
        for(int u = S; u > 0; u -= lowbit(u))
            for(int v = S; v > 0; v -= lowbit(v))
            {
                const int i = ctz(u), j = ctz(v);
                if(i != j) down(f[S][i], f[S ^ (1 << i)][j] + e[j][i]);
            }
    }
    double res = 1e23;
    rep(i, 0, n - 1) down(res, f[U][i]);
    cout << res << '\n';
    return 0;
}