-
Notifications
You must be signed in to change notification settings - Fork 0
/
10021.js
67 lines (56 loc) · 1.37 KB
/
10021.js
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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
/*
각 밭별로 다른 모든 밭들까지의 수로 건설 비용을 계산
이때 비용이 C 미만이면 제외
위에서 만든 배열을 이용해서 크루스칼 알고리즘 사용
*/
// input
const inputFile = process.platform === 'linux'? '/dev/stdin' : './input';
const input = require('fs').readFileSync(inputFile).toString().trim().split('\n');
const [N, C] = input[0].trim().split(' ').map(Number);
const fields = input.slice(1).map(x => x.trim().split(' ').map(Number));
// process
// 수로 비용 계산
const pipe_costs = [];
for (let i=0; i<N-1; i++)
{
let [xi, yi] = fields[i];
for (let j=i+1; j<N; j++)
{
let [xj, yj] = fields[j];
let cost = (xi - xj) ** 2 + (yi - yj) ** 2;
if (cost >= C)
pipe_costs.push([i, j, cost]);
}
}
// 크루스칼
pipe_costs.sort((a, b) => a[2] - b[2]);
const parent = new Array(N).fill(-1);
let pipe_cnt = 0;
let total_cost = 0;
for (let [i, j, cost] of pipe_costs)
{
if (pipe_cnt == N - 1)
break
if (find(i) != find(j))
{
union(i, j);
pipe_cnt++;
total_cost += cost;
}
}
// output
console.log(pipe_cnt === N - 1? total_cost : -1);
// functinos
function union(a, b)
{
a = find(a);
b = find(b);
parent[b] = a;
}
function find(a)
{
if (parent[a] == -1)
return a;
parent[a] = find(parent[a]);
return parent[a];
}