ABC 061 D-Score Attack

D - Score Attack
グラフの問題としては少し特殊で, ゴールまでのコストを最大化する問題です. これは, すべてのコストを負にした最短経路問題を解くことで解を出せます. しかし, コストに負を含んでいるとダイクストラ法が使えません. そのため, ベルマンフォード法を用いる必要があります. さらに, 負の閉路が存在していると, スコアをいくらでも増加させることができる可能性があるので, そのような場合を検出しなければいけません. しかし, 負の閉路が存在していてもスコアをいくらでも増加させることができるとは限りません. 例えば, 負の閉路からゴールに到達できないようなグラフは, スコアをいくら増加させてもゴールすることができないので, スコアの上限が存在します. そのため, ベルマンフォード法で閉路の検出を行うときはN回目のループで『最終ループでゴールへの最短経路が更新されたか？』を調べるだけでよいことになります. これに気づかずWAを連発し, ネットの海を彷徨いました.
Submission #2901055 - AtCoder Beginner Contest 061