외판원 순회 3

백준 16991번: 외판원 순회 3

아이디어

외판원 순회 1이랑 똑같고 cost 대신 거리를 구하면 된다. 소수점 출력 주의.

코드

#include <bits/stdc++.h>

using namespace std;

const double INF = 987654321.0;
int N;
pair<int, int> arr[16];
double cache[16][1<<16];

double get_dist(pair<int, int> p1, pair<int, int> p2) {
    int y1 = p1.first;
    int x1 = p1.second;
    int y2 = p2.first;
    int x2 = p2.second;
    return sqrt(pow(y1-y2, 2) + pow(x1-x2, 2));
}

double solve(int now, int cur) {
    if (cur == (1<<N)-1) {
        return get_dist(arr[now], arr[0]);
    }
	
    double& ret = cache[now][cur];
    if (ret != 0) return ret;

    ret = INF;
    for (int i = 1; i < N; i++) {
        if (cur&(1<<i)) continue;
        ret = min(ret, solve(i, cur|(1<<i)) + get_dist(arr[now], arr[i]));
    }
    return ret;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int y, x;
    cin >> N;

    for (int i = 0; i < N; i++) {
        cin >> x >> y;
        arr[i] = {y, x};
    }

    cout << fixed;
    //cout.precision(6);

    memset(cache, 0, sizeof(cache));
    cout << solve(0, 1);
    return 0;
}

여담

기본 6자리 출력이라 그냥

cout << fixed;

만 쳐도 소수점 6자리까지 나온다.