Gym - 101908J Joining Capitals
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int MAXN = 105; 5 const double INF = 1e12; 6 pair<int, int> p[MAXN]; 7 double dp[MAXN][1 << 11], dis[MAXN][MAXN]; 8 int N2(int x) { 9 return x * x; 10 } 11 double get_dis(pair<int, int> a, pair<int, int> b) { 12 return sqrt(N2(a.first - b.first) + N2(a.second - b.second)); 13 } 14 int main() { 15 int n, k; 16 scanf("%d %d", &n, &k); 17 for (int i = 0; i < n; i++) { 18 scanf("%d %d", &p[i].first, &p[i].second); 19 } 20 for (int i = 0; i < n; i++) { 21 for (int j = 0; j < n; j++) { 22 if (i != j) { 23 dis[i][j] = get_dis(p[i], p[j]); 24 } 25 } 26 } 27 for (int i = k; i < n; i++) { 28 for (int j = 0; j < (1 << k); j++) { 29 dp[i][j] = 0; 30 for (int s = 0; s < k; s++) { 31 dp[i][j] += (j >> s & 1) * dis[i][s]; 32 } 33 } 34 } 35 for (int S = 0; S < (1 << k); S++) { 36 for (int x = k; x < n; x++) { 37 for (int i = k; i < n; i++) { 38 if (i != x) { 39 for (int sub = S; ; sub = (sub - 1)&S) { 40 dp[x][S] = min(dp[x][S], dis[i][x] + dp[x][sub] + dp[i][S ^ sub]); 41 if (!sub) { 42 break; 43 } 44 } 45 } 46 } 47 } 48 } 49 double ans = INF; 50 for (int i = k; i < n; i++) { 51 ans = min(ans, dp[i][(1 << k) - 1]); 52 } 53 printf("%.5f ", ans); 54 return 0; 55 }