ABC061 Dを解きました

ABC061 D - Score Attackを解きました

解法

1. グラフを構築する。このとき辺のコストは正負を反転する。(今回の問題が最大コストを求める問題のため)
2. ベルマンフォード法を使いスタートから各頂点までの最短経路を求める。(ただし最短距離の更新回数Vを頂点数とするとはV回までとする)
3. もう一回ベルマンフォード法を用いる。このとき更新された頂点は無限に更新される。
4. 頂点Nが3.で更新されてなければ最短経路を出力し、更新されていればinfを出力する。

自分の提出結果(http://abc061.contest.atcoder.jp/submissions/1673591)

感想とか

少しわかりづらい説明ですみません>< 今回気をつけるべきポイントは「負の閉路があるなら答えはinf」ではないということです。 例えば下図の場合出力すべき答えは132です。このとき4->5->6は負の閉路ですが7に至るまでの経路に関係ありません。 これに引っかかるって残り3つのWAが取れずに苦労しました><

図1