BOJ - 1647 - 도시 분할 계획

import sys
import heapq

def PRIM(graph, V, idx):
    hq = []
    visit = [False] * (V + 1)
    visit[idx] = True
    distance = [0] * (V + 1)
    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[vertex] += weight
            for i in graph[vertex]:
                heapq.heappush(hq, i)
        if cnt == V:
            ret = sum(distance) - max(distance)
            return ret
    return 0

def solution():
    V, E = map(int, sys.stdin.readline().split())
    graph = [[] for _ in range(V + 1)]
    for _ in range(E):
        A, B, C = map(int, sys.stdin.readline().split())
        graph[A].append((C, B))
        graph[B].append((C, A))
    print(PRIM(graph, V, 1))
solution()

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