BOJ - 4386 - 별자리 만들기

import sys
import math
import heapq

def PRIM(graph, V, idx):
    hq = []
    visit = [False] * (V + 1)
    visit[idx] = True
    distance = 0
    cnt = 1

    for i in graph[idx]:
        heapq.heappush(hq, i)

    while hq:
        weight, vertex = heapq.heappop(hq)
        if not visit[vertex]:
            visit[vertex] = True
            cnt += 1
            distance += weight
            for i in graph[vertex]:
                heapq.heappush(hq, i)
        if cnt == V:
            return distance
    return -1

def getDistance(x1, x2):
    return (
        math.sqrt(math.pow(x1[0] - x2[0], 2) + math.pow(x1[1] - x2[1], 2))
    )

def solution():
    N = int(sys.stdin.readline())
    vertex = []
    graph = [[] for _ in range(N)]

    for idx in range(N):
        x, y = map(float, sys.stdin.readline().split())
        vertex.append([x, y])

    for i in range(N):
        for j in range(i + 1, N):
            distance = getDistance(vertex[i], vertex[j])
            graph[i].append([distance, j])
            graph[j].append([distance, i])

    print("%0.2f"%PRIM(graph, N, 0))

solution()

https://www.acmicpc.net/problem/4386