E - Two Currencies(解説)
[解法]
結論から言えば、拡張ダイクストラというものをする。なにを拡張するのかというと、ノードの数である。 そもそもダイクストラをただ単に移動する最短距離や最小コストを得るものとして捉えるのではなく、 最初の状態から最後の状態 になるための最小コストを得るものだ と捉えてほしい。
ある点からある点への移動 はもっと抽象的にいうと ある状態からある状態への推移
と捉えることができる。 今の状態から次にどのような状態にすることができるかを考えれば、自然にダイクストラを拡張することができる。
今回は、 [街Uにいるときに銀貨をx枚もっている] というものを一つの状態にすることができる。 街Uからは街Vの辺が貼られてるすると遷移先としては、 [街Vにいるときに銀貨をx-A枚持ってる状態]にコストB, [街Uにいるときに銀貨をx+C枚持っている状態]にコストD で遷移することができる。
ここまでくれば、あとは普通のダイクストラをするだけだ。
自分は二次元でダイクストラをしたくないので、[街Uにいるときに銀貨をx枚もっている] という情報を1次元にしたく、 配列で node[U][x] にするのではなく node[U*5000 + x] と変換した。
Aの最大は50,街の最大数は50で必要な銀貨の最大数は50*50=2500枚程度なので かぶることはない。
また、最初に受け取った S を S=min(S,3000) としたのもポイントだ。
以下がACコードになる
