ABC61[D]ScoreAttack（別解）

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

ABC61D_BF_ScoreAttack

解説

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

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