[16991번] 외판원 순회 3

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. Dynamic Programming

2. 점화식 세우는 방법

https://www.crocus.co.kr/1433?category=159837

위 링크에서 답이 double로 표현되는 것 외에는 차이가 없다.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53

#include <iostream> #include <memory.h> #include <cmath>   #define MIN(a, b)(a < b ? a : b) #define INF 987654321   typedef long long ll;   double cost[20][20]; double dp[20][1 << 16]; int n; std::pair<int, int> pt[20];   double TSP(int here, int visit) {     double &ret = dp[here][visit];     if (ret != -1.0)         return ret;       if (visit == (1 << n) - 1) {         if (cost[here][0] == 0.0)             return ret = INF;         return ret = cost[here][0];     }       ret = INF;     for (int i = 0; i < n; i++) {         if (visit & (1 << i) || cost[here][i] == 0.0)             continue;           ret = MIN(ret, TSP(i, visit | (1 << i)) + cost[here][i]);     }       return ret; } int main() {     scanf("%d", &n);       for (int i = 0; i < n; i++)         scanf("%d %d", &pt[i].first, &pt[i].second);       for (int i = 0; i < n; i++)         for (int j = 0; j < n; j++)             cost[i][j] = sqrt(pow(pt[i].first - pt[j].first, 2) + pow(pt[i].second - pt[j].second, 2));          for (int i = 0; i < 20; i++)         for (int j = 0; j < (1 << 16); j++)             dp[i][j] = -1.0;       printf("%lf", TSP(0, 1 << 0));          return 0; } Colored by Color Scripter

cs