ALDS1_12_C: Single Source Shortest Path II (続き3)

たいへん申し訳ありません

                heappush(h, (adj, nodes[adj].dist))

ここでついついノード番号を先に書いてしまいました
サンプルのコードはちゃんとコストから書いてあったんですけどね
なんでそういう順なのかな好みかなとかテキトーなこと考えて
なんかIDっぽいものから書きたくなりますよね？

ノード番号を先に書いてしまったので、コストが最小なものからではなくて
番号が小さいものから取り出されることに

n=10000で0.040s
少し速くなりました

さてこれでPart2[基礎編]が終わりました
え、基礎!?

ところで『最短経路の本 レナのふしぎな数学の旅』の関連部分も読んでみました
プリムのアルゴリズムで

どこから始めても同じなのか？
そうであってもよさそうだけど絶対そうかと言われるとちょっと自信がない

なところも、背理法の証明が載ってました
もちろんダイクストラのアルゴリズムも出てました
そっちのほうが先に出てましたね
順番が入れ替わってるのは、優先度付きキューによる実装を含めて順番を考慮したのかな