7K12 blog

猫でも分かるアルゴリズム解説

AOJ ALDS1_11_C 幅優先探索

f:id:tkr987:20200617125103p:plain

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4587473

f:id:tkr987:20200617125929p:plain

幅優先探索の基本。注意点として、他の頂点から遠回りして更新済み頂点に辿り着いたとき再び更新しないように if (res[to] != -1) continue; が必要。これは最短経路では定跡の書き方なので暗記。辿り着かない頂点は-1にしたいので、結果を格納する配列を-1で初期化しスタート地点だけ0にする。