https://atcoder.jp/contests/abc137/submissions/11045565
- 最小値でなく最大値を求める場合、辺コストの符号を逆にしてグラフアルゴリズムに投げる
- 上記に加え、探索して得られた出力（最小値）の符号を逆にして答えとする
- 最大値は「符号の反転を2回する」と覚えるとコスパが良さそう
- 辺を通過する毎にP枚コインが減るので、予め辺のコストをP減らしておく
まず、辺を通過する毎にP枚コインが減るのでとして予め辺のコストを減らしておく。ただし、最小値でなく最大値を求めるので、辺のコストの符号を逆にする必要がある。結局のところ辺のコストは
となる。
次に、最大値を探索する具体的な処理を考える。辺のコストに負があるのでグラフアルゴリズムはベルマンフォード法を使う。ただし、いくらコインが増加するとしてもゴールに辿り着けなければ意味がないため、ゴールに辿り着けない頂点を集めた「無視する頂点集合」を求めておく。頂点sからtに辿り着けるかどうかはDFSを使ってで求められる（たぶん）ので、全頂点について調べると
になる。隣接リストと無視する頂点集合をベルマンフォード法に渡し、探索して得られた最小値の符号を逆にした値が答え（最大値）になる。
感想: 頂点の到達可能性は今後も役に立ちそうなのでライブラリ化した。
