AtCoder Beginners Contest 164 E - Two Currencies
問題
十分多い金貨と枚の銀貨を持って都市1にいる。
本の線路はそれぞれ、都市
間を走り、運賃は銀貨
枚、時間は
分かかる。
各都市の料金所で
分かけて金貨1枚と銀貨
枚を交換してくれる。
各都市に移動するのにかかる最小時間を求める。
考察
都市の数が50、運賃の上限が50なので、銀貨は2500枚あれば十分であることがわかる。コストを時間とし、今いる都市と所持している銀貨の枚数
の状態で拡張ダイクストラ法を用いて解く。
路線を利用すると、都市
で銀貨を
枚持っているとき、
分後に都市
で銀貨を
枚持っているので、この状態に辺を張る（
の逆も）。
料金所を利用すると、都市
で銀貨を
枚持っているとき、
分後に都市
で銀貨を
枚持っているので、この状態に辺を張る。
このグラフでからの最短距離を求め、各都市の任意の銀貨の枚数でもっともかかったコストが小さいものが答え。ただし、
は2500あれば十分なので、超えているなら2500で置き換える。
