BOJ 16991번 외판원 순회3

BOJ : https://www.acmicpc.net/problem/16991

github : https://github.com/junho0956/Algorithm/blob/master/16991/16991/%EC%86%8C%EC%8A%A4.cpp

 

BOJ 외판원 순회2 https://junho0956.tistory.com/172?category=825557

위 문제를 통해 풀이한 문제입니다.

 

달라진 것은 소수점 표현인데,

정점이 좌표로 주어지는 방식이고, 좌표끼리의 거리를 알기 위해서

완전탐색을 통해 각 좌표사이의 거리만 구해준 후 TSP의 흐름과 똑같이 풀어주시면 됩니다

 

#include <cstdio>
#include <algorithm>
#include <math.h>
using namespace std;
#pragma warning(disable:4996)
#define MAX 99999999.999999
 
pair<int,int> arr[16];
double cost[16][16];
double dp[16][1 << 16];
int N;
 
double TSP(int start, int visit) {
    if (visit == ((1 << N) - 1)) {
        if (cost[start][0] == 0) return MAX;
        else return cost[start][0];
    }
 
    double& result = dp[start][visit];
    if (result) return result;
 
    double len = MAX;
    for (int i = 1; i < N; i++) {
        if (cost[start][i] != 0 && (visit & (1 << i)) == 0) {
            len = min(len, cost[start][i] + TSP(i, visit | (1 << i)));
        }
    }
 
    return result = len;
}
 
int main() {
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++) scanf("%d%d", &arr[i].first, &arr[i].second);
 
    for (int i = 0; i < N; i++) {
        int fx = arr[i].first, fy = arr[i].second;
        for (int k = i + 1; k < N; k++) {
            int lx = arr[k].first, ly = arr[k].second;
            cost[i][k] = cost[k][i] = sqrt(pow(lx - fx, 2) + pow(ly - fy, 2));
        }
    }
 
    printf("%.9f", TSP(0, 1));
    return 0;
}