7K12 blog

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

AOJ GRL_1_A Single Source Shortest Path

f:id:tkr987:20200626095932p:plain

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

f:id:tkr987:20200626100800p:plain

到達できない頂点はINFを出力するので、各頂点を十分大きな値infで初期化する。スタート地点を0として、ダイクストラ法で最短経路を求める。詳しい実装は螺旋本p312に載っている。