読者です 読者をやめる 読者になる 読者になる

samayotta.show()

好きな映画は『たまこラブストーリー』です。

ABC61[D]ScoreAttack(別解)

推奨のベルマンフォード実装。

 

ABC61D_BF_ScoreAttack

解説

ベルマンフォードは負の辺でも動作する最短経路アルゴリズムで、ワーシャル・フロイドよりは全然早い方法。ダイクストラは辺のコストが非負でのみ動作するがより高速。

グラフ理論を解くときに気をつけたいのは初期化のところ。手を抜いてinit()を書かずにうまくやろうとすると詰まったので、多少の手間を惜しまないのがバグを生まない実装かなと思う。