プリム法

F - 最小全域木問題

O(N)

import sys
import math
import heapq
import itertools
from collections import deque
from functools import reduce

# main
def main():
    N, M = list(map(int, input().split()))
    G = []

    for _ in range(N):
        G.append([])

    for _ in range(M):
        u, v, c = list(map(int, input().split()))
        G[u].append((v, c))
        G[v].append((u, c))

    marked = []
    for _ in range(N):
        marked.append(False)

    marked_count = 0
    marked[0] = True
    marked_count += 1
    Q = []

    for j, c in G[0]:
        heapq.heappush(Q, (c, j))

    sum = 0
    while marked_count < N:
        c, i = heapq.heappop(Q)
        if marked[i]:
            continue
        marked[i] = True
        marked_count += 1
        sum += c
        for j, c in G[i]:
            if marked[j]:
                continue
            heapq.heappush(Q, (c, j))
    
    print(sum)

# エントリポイント
if __name__ == '__main__':
    main()