GRL_2の解答例(Python)

最小全域木に関する問題です．

1. GRL_2_A: Minimum Spanning Tree

# GRL_2_A
# グラフが連結であるのでプリム法を使った
import heapq
V,E = map(int,input().split())

adjacent_list = [[] for _ in range(V)]
for _ in range(E):
    s,t,w = map(int,input().split())
    # 有向グラフでないのでどちらの向きも追加する
    adjacent_list[s].append((w,s,t)) # 重みで優先度を付けたいのでwを1番目にする
    adjacent_list[t].append((w,t,s)) # 重みで優先度を付けたいのでwを1番目にする
    
# 優先度付きキューにする 0を始点にした 
heap = [info for info in adjacent_list[0]]
heapq.heapify(heap)

done_set = set([0]) # 到達した点の集合
cost = 0
while heap:
    # コストが小さい辺から取り出す
    w,s,t = heapq.heappop(heap)
    # コストが小さくならないなら何もしない
    if t not in done_set:
        cost += w
        for info in adjacent_list[t]:
            if info[-1] not in done_set:
                heapq.heappush(heap,info)

    done_set.add(t)
    
print(cost)

2. GRL_2_B: Minimum-Cost Arborescence

# GRL_2_B
# 編集中