b_우주신과의교감_1774

문제

우주신과 황선자씨랑교신해야함(바로 교신할필요없음)
일부 우주신은 이미황선자씨와 교신할수있음
짧은 통로를 좋아함
우주신 개수 N,이미연결된 통로 M

답

import sys
input = sys.stdin.readline
n,m= map(int,input().strip().split())
parents = [i for i in range(n+1)]
nodes = [] # 번호, y, x
edges = [] # 비용, 번호1, 번호2

def find_parent(n):
    if parents[n] !=n:
        parents[n] = find_parent(parents[n])
    return parents[n]

for i in range(n):
    y,x = map(int,input().strip().split())
    nodes.append((i+1,y,x))

def union_p(n1,n2):
    np1 = find_parent(n1)
    np2 = find_parent(n2)
    if np1 != np2:
        if np1<np2:
            parents[np2] = np1
        else:
            parents[np1] = np2
        return True
    return False

for i in range(m):
    n1,n2 = map(int,input().strip().split())
    union_p(n1,n2)

for i in range(n):
    n1 = nodes[i]
    for j in range(i+1,n):
        n2 = nodes[j]
        cost=((n1[1]-n2[1])**2 + (n1[2]-n2[2])**2) ** 0.5
        edges.append((round(cost,2),n1[0],n2[0]))

edges.sort()
anw = 0
for e in edges:
    c,n1,n2 = e
    if union_p(n1,n2):
        anw +=c

print(format(anw, ".2f"))