perogram

ベルマンフォード bellman ford クラス実装

Quiz

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_B

Submission

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

参考

https://ei1333.github.io/luzhiled/snippets/graph/bellman-ford.html

その他

  • 競プロでの問題では必要となる時が少ないのか、bellman fordの実装は初めてだったようだ
  • 負のコストがあるのでダイクストラではダメ
  • 頂点の数をVとして、V-1回まわすことで伝播するというのは他でも使えるかもしれない
  • 必ず止まるという安心感もある
  • 全く詰まらず実装できて成長を感じる