/
\
38 lines (32 loc) · 1005 Bytes
/
\
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
#include <iostream>
#include <cmath>
#define sq(a) ((a) * (a))
#define distance(i, j) ((long long) round(sqrt(sq(computer[i][0]-computer[j][0])+sq(computer[i][1]-computer[j][1])) * 1000))
#define get(n, i) ((n >> i) % 10)
#define set(n, i) (n | (1 << i))
#define clear(n, i) (n & ~(1 << i))
#define ll unsigned long long
using namespace std;
int computer[10][2], connect[10], n;
ll solve(int cur, int visited) {
if (__builtin_popcount(visited) == n - 1) return 0;
visited = set(visited, cur);
ll best = 999999999999;
cout << cur << ' ' << visited << endl;
for (int i = 0; i < n; i++) {
if (get(visited, i) == 0) {
best = min(best, distance(cur, i) + solve(i, visited));
}
}
visited = clear(visited, cur);
return best;
}
int main() {
while (cin >> n and n) {
for (int i = 0; i < n; i++) cin >> computer[i][0] >> computer[i][1];
ll best = 999999999999;
for (int i = 0; i < n; i++) best = min(best, solve(i, 0));
cout << best << endl;
}
return 0;
}