AtCoder Beginner Contest 061 D - Score Attack
負経路を許す有向グラフで、頂点1から頂点Nまでの最長経路を求めよ。いくらでも長くできる場合はinfを出力せよ。
辺のコストを-1倍してベルマンフォード。負閉路が検出されたその時点でinfにする。ただし、1からNへの経路に関係ない負閉路が存在する場合があるのでそこは考えない。簡単な方法としてdfsでNに行くことが可能な頂点がtrueであるようなbooleanの配列を作っておき、負閉路チェックの際にfalseであればスルーするなどがある。
いわれてみればそうなんだけど、負閉路検出の条件に気づかずにハマった。しかももっと単純に書けるかもしれない。
