ほぼこれ。abc 137 E - Coins Respawn (python) - aacord’s memo 頂点１からNまでに通りうる経路だけ抜き出して、その中で bellman-ford を使う。更新回数が m 回をこえたら inf を出力する。 from collections import deque def belman(s,n,w,es): d = [-fl…

経過時間*P 枚コインを失い、辺を通るのに１分かかり、辺上でC枚のコインを得るので、 辺を通ったときにかかるコスト（-コインの数）を －C＋P 枚とすれば、最短路問題に帰着できる。今回は負の辺があるのでベルマンフォード法を使う。 面倒なのは、頂点１か…