백준[16991] 외판원 순회 3

문제설명

문제링크

http://icpc.me/16991

풀이

비트마스크를 이용한 dp문제이며 외판원 순회와 다를 게 없다.

코드

#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;
using pii = pair<int, int>;

pii arr[17];
double dp[17][1 << 16];
int n;

double dist(pii a, pii b) {
    int x = (a.first - b.first) * (a.first - b.first);
    int y = (a.second - b.second) * (a.second - b.second);
    return sqrt(x * 1.0 + y * 1.0);
}

double dpf(int cur, int state) {
    double &ret = dp[cur][state];
    if (ret) return ret;
    if (state + 1 == 1 << n) return dist(arr[cur], arr[0]);
    double ans = 1e9;
    for (int i = 0; i < n; i++) {
        if (!(state & (1 << i))) ans = min(ans, dpf(i, state | (1 << i)) + dist(arr[cur], arr[i]));
    }
    return ret = ans;
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d %d", &arr[i].first, &arr[i].second);
    printf("%.6lf", dpf(0, 1));
}