-
Notifications
You must be signed in to change notification settings - Fork 96
/
[16]_3.py
60 lines (48 loc) · 1.21 KB
/
[16]_3.py
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
import math
import sys
input = sys.stdin.readline
def get_distance(p1, p2):
a = p1[0] - p2[0]
b = p1[1] - p2[1]
return math.sqrt((a * a) + (b * b))
def get_parent(parent, n):
if parent[n] == n:
return n
return get_parent(parent, parent[n])
def union_parent(parent, a, b):
a = get_parent(parent, a)
b = get_parent(parent, b)
if a < b:
parent[b] = a
else:
parent[a] = b
def find_parent(parent, a, b):
a = get_parent(parent, a)
b = get_parent(parent, b)
if a == b:
return True
else:
return False
edges = []
parent = {}
locations = []
n, m = map(int, input().split())
for _ in range(n):
x, y = map(int, input().split())
locations.append((x, y))
length = len(locations)
for i in range(length - 1):
for j in range(i + 1, length):
edges.append((i + 1, j + 1, get_distance(locations[i], locations[j])))
for i in range(1, n + 1):
parent[i] = i
for i in range(m):
a, b = map(int, input().split())
union_parent(parent, a, b)
edges.sort(key=lambda data: data[2])
result = 0
for a, b, cost in edges:
if not find_parent(parent, a, b):
union_parent(parent, a, b)
result += cost
print("%0.2f" % result)