最小全域木（MST）については以下： 最小全域木（MST - Minimum Spanning Tree） - 競プロはじめましたUnionFindについては以下： UnionFind木 - 競プロはじめました 考え方 回答例 考え方クラスカル法を使う．以下のようにすれば良い．一度のクラスカル法で…

用語 アルゴリズム 例題 用語用語を整理しておきます（蟻本p. 99-）： 全域木：無向グラフの部分グラフで，任意の2頂点が連結である木． 最小全域木：辺のコストの和が最小の全域木． アルゴリズム プリム法：木$T$に，木$T$の頂点と木$T$に含まれない頂点を…

考え方 回答例 考え方 「重みなし」グラフの最短経路を求める問題になる→BFS 桁が減る操作はないので，10 ** 6を超えたら打ち切ることができる 回答例 from collections import deque a, N = map(int, input().split()) q = deque() q.append(1) dist = [-1]…