ダイクストラ法の理解

[kenchanbomber]

https://atcoder.jp/contests/abc191/tasks/abc191_e

各地点iからの最短経路をある程度高速に求める必要がある。

[kenchanbomber]

利用可能なedgeの内、コストが最小のものを利用すると確定させる方針をとったがWA

例えば、同じコストのedgeが多数ある場合、最小コストになるとは限らない。

[kenchanbomber]

1. 確定していないnodeのうち最小コストで辿り着けるnodeを確定する。
2. そのnodeから行けるnodeの最小コストを更新する。
3. 確定していないnodeがなければ終了。確定していないnodeがあれば1に戻る。