プリム法
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()