우주신과의 교감(백준 1774)

MST를 사용하는 대표적인 문제이다. 이미 연결된 길은 건설할 필요가 없으니 0의 값으로 저장한다. 

이후 프림 알고리즘을 사용한다. 

import sys 
import heapq 
input = sys.stdin.readline 

def calc(x1,y1,x2,y2):
    return (((x1-x2)**2 + (y1-y2)**2)**0.5 )



def prim(start) :
    global ans 
    q =[[0,start]]
    heapq.heapify(q)
    while q :
        cost,now = heapq.heappop(q)
        if (visited[now] ==0):
            visited[now] = 1 
            ans += cost 
            for nextnode,nextcost in gra[now] :
                if(visited[nextnode]==0):
                    heapq.heappush(q,(nextcost,nextnode))
n,m = map(int, input().split())
gra =[[]for _ in range(n+1)]
points = [[0,0,0]]
for i in range(n):
    a,b= map(int, input().split())
    points.append((i,a,b))

for _ in range(m):
    a,b = map(int, input().split())
    gra[a].append((b,0))
    gra[b].append((a,0))

for i in range(1, n):
    for j in range(i+1, n+1):
        x1,y1 = points[i][1],points[i][2]
        x2,y2 = points[j][1],points[j][2]
        howfar =calc(x1,y1,x2,y2)
        gra[i].append((j,howfar))
        gra[j].append((i,howfar))
visited = [0 for i in range(n+1)]
ans = 0 
prim(1)

print("%.2f" %(ans))