ABC164 E Two Currencies
Diff 1877.
実装問題. 銀貨がかなり多いがよくよく考えると2500枚までしか考えないでよいことがわかる.
$ dist_{i,j}
:=
$ i
番目の都市にいて銀貨を
$ j
枚持っているときの時間の最小値 として拡張ダイクストラをしていく.
両替操作の途中で銀貨が2500枚を超えないように注意する(超える場合は1回のみ2500枚として考える). 移動は銀貨が0枚下回らないか考えるだけ.
実装例:
https://atcoder.jp/contests/abc164/submissions/18933617