ABC137 E - Coins Respawn (500)
Pを各辺のコインから引くと必要な秒数について考えなくて良くなる
辺のコストとしてコインの数に-1をかけた値を用いるとベルマンフォード法で最短経路と負閉路検出ができる
グラフ内に負閉路があっても1->Nの経路上に持ってくることができない位置にある場合は無視する必要がある
事前に1から辺を辿っていける頂点の集合と、Nから辺を逆に辿ってを作っておく
負閉路となる辺に対して1から到達できる点とNから到達できる点の間にあった場合は無限に増やせる
そうでない場合はそこは通ることができない点なので無視する
コインが不足する場合はマイナスではなく0になる点に注意