No Caffeine, No Life

プログラミング(主にPython)

ABC 061 D:Score Attack ベルマンフォード法

問題:

D: Score Attack - AtCoder Beginner Contest 061 | AtCoder

解説:

  • ベルマンフォード法を使うために、辺のコストをすべて負とする。(答えは、得られた最小値 x -1 )
  • 閉路が検出されれば、それがinfの場合。普通のベルマンフォードの法と異なり、終点が頂点Nになることが保証されているので、それを加味する。

解答: