Graph/Prim.py

View this file on GitHub
Last update: 1970-01-01 00:00:00+00:00

Code

# 最小全域木（プリム法）
from heapq import heappop, heappush, heapify

n, m = map(int,input().split())

g = [[] for _ in range(n)]
for _ in range(m):
    u, v, cost = map(int,input().split())
    g[u].append((cost, v))
    g[v].append((cost, u))

visited = [False] * n
connection = 0
q = []
q.append((0, 0))
heapify(q)

ans = 0
while q:
    cost, v = heappop(q)
    if visited[v]: continue

    visited[v] = True
    connection += 1
    ans += cost

    for nxt in g[v]:
        heappush(q, nxt)
    
    if connection == n:
        break

print(ans)

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.3/x64/lib/python3.12/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.12.3/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError