P1433 吃奶酪-526互联

P1433 吃奶酪

思路

状态压缩dp + dfs。f[i][j]表示当前走到第i个点，且之前走过点的情况为j的情况下走过的最短路程

ac代码

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;
const i64 inf = 8e18;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
const int N = 3e5 + 10;

int n;
double f[20][65540], ans = DBL_MAX;
bool st[20];
vector<pdd> loc;

double dist(pdd a, pdd b) {
    return sqrt((a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second));
}

void dfs(int p, int step, int mark, double d) {
    if (step == n) {
        ans = min(ans, d);
        return;
    }

    for (int i = 1; i <= n; i++) {
        if (st[i]) continue;

        if (f[i][mark + (1 << i)] == 0 || f[i][mark + (1 << i)] > f[p][mark] + dist(loc[p], loc[i])) {
            f[i][mark + (1 << i)] = f[p][mark] + dist(loc[p], loc[i]);
            st[i] = 1;
            dfs(i, step + 1, mark + (1 << i), d + dist(loc[p], loc[i]));
            st[i] = 0;
        }
    }
}

void solve() {
    cin >> n;
    loc.push_back({0, 0});
    for (int i = 0; i < n; i++) {
        double x, y;
        cin >> x >> y;
        loc.push_back({x, y});
    }

    dfs(0, 0, 0, 0);
    st[0] = 1;

    printf("%.2lf", ans);
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    int t = 1;
    //cin >> t;
    while (t --) solve();

    return 0;
}