-
Notifications
You must be signed in to change notification settings - Fork 0
/
우주신과의교감.java
102 lines (84 loc) · 2.66 KB
/
우주신과의교감.java
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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
// BOJ - 우주신과의 교감(1774번)
// MST
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Main_1774 {
public static int[] parent;
public static Node[] node;
public static class Node {
int x;
int y;
public Node(int x, int y){
this.x = x;
this.y = y;
}
}
public static class Edge implements Comparable<Edge> {
int a;
int b;
double dist;
public Edge(int a, int b, double dist){
this.a = a;
this.b = b;
this.dist = dist;
}
@Override
public int compareTo(Edge o) {
return Double.compare(this.dist, o.dist);
}
}
public static int n, m;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
node = new Node[n+1];
parent = new int[n+1];
for(int i=0;i<n;i++){
st = new StringTokenizer(br.readLine(), " ");
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
node[i+1] = new Node(x, y);
parent[i+1] = i+1;
}
for(int i=0;i<m;i++){
st = new StringTokenizer(br.readLine()," ");
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
union_parent(a, b);
}
PriorityQueue<Edge> pq = new PriorityQueue<>();
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
double cost = Math.sqrt(Math.pow(node[i].x - node[j].x, 2) + Math.pow(node[i].y - node[j].y, 2));
pq.add(new Edge(i, j, cost));
}
}
double cost = 0;
while (!pq.isEmpty()){
Edge edge = pq.poll();
if(find_parent(edge.a) != find_parent(edge.b)){
union_parent(edge.a, edge.b);
cost += edge.dist;
}
}
System.out.printf("%.2f", cost);
}
public static int find_parent(int x) {
if(parent[x] == x) return x;
return parent[x] = find_parent(parent[x]);
}
public static void union_parent(int a, int b){
a = find_parent(a);
b = find_parent(b);
if(a < b){
parent[b] = a;
} else {
parent[a] = b;
}
}
}