解答:Submission #12471668 - AtCoder Beginner Contest 164
解法:dp[v][s]を「頂点vに銀貨s枚で到達するときの最短時間」とし、ダイクストラする。(拡張ダイクストラ)
辺自体は最初に与えられた(v, a, b) = (行き先の頂点、辺の銀貨コスト、辺の時間コスト)だけでよく、ダイクストラのキューで保持する(v, ns, time) = (現在の頂点、現在の銀貨、現在の時間)が増えてゆくイメージ。
ダイクストラの遷移は、1つの(v, ns, time) に対し、①同じ頂点で銀貨交換、②各辺を使っていける頂点に移動を行う。
必要とする銀貨は最大で2500枚であるため、初期値の銀貨は2500枚で頭打ちし、銀貨交換も2500枚でやめる。