コンテスト中に解けなかったので記録.

問題概要

${n}$ 頂点 ${m}$ 本の辺からなる無向グラフが与えられる。

頂点 ${s}$ から頂点 ${t}$ に移動するとき、1回だけ両替所の存在する頂点で円→スヌークへ全額両替する。

この時かかる金額(円+スヌーク)の最小値を求めたい。

初期状態として各頂点に両替所が存在するが, ${i}$ 年後には頂点 ${i}$ の両替所は閉鎖され以降使用不可。

とりあえず、頂点 ${s}$ から頂点 ${t}$ への最小コストを求めたいので、円とスヌークをそれぞれ重みとしたダイクストラをやるのかと思った...がそこから考えが進まず、コンテスト終了。

これって ${n-1}$ 年後を考えると両替できるのが頂点 ${n}$ だけで、これは「円でダイクストラをした時の頂点 ${s}$ から頂点 ${n}$ へのコストと、スヌークでダイクストラをした時の頂点 ${n}$ から頂点 ${t}$ へのコストの和」でも求まるんですよね。

で ${n-2}$ 年後は ${n-1}$ 年後か同様に「円でダイクストラをした時の頂点 ${s}$ から頂点 ${n-1}$ へのコストと、スヌークでダイクストラをした時の頂点 ${n-1}$ から頂点 ${t}$ へのコストの和」の最小値を取ればいいんですよ。

ということは ${n-1}$ 年後から ${0}$ 年後に向かって累積minを求めれば ${i}$ 年後について全て求まるんですね。

提出コード:

問題の言い換えは大切( ${i}$ 年後に頂点 ${i}$ の両替所が廃止/設立)

比較する候補が少ない状態(使用可能な両替所の数)から多くなる方向に考えを巡らせることは典型らしいので身に付けたいね。

fuu32のブログ