問題

https://atcoder.jp/contests/soundhound2018-summer-qual/tasks/soundhound2018_summer_qual_d

考え方

解は $0 \le i \le n-1$ なる $i$ 年それぞれについて解を出力する必要がある。各年度それぞれについてダイクストラをするのではTLEになる。

まず $s,t$ からそれぞれの都市への最短距離を求めよう。経路は両替所を $u_k$ とすると $s \rightarrow u_k \rightarrow t$ となるためである。

最短経路が求められたら、制約の厳しいところから考えていこう。その場合は $n-1$ 年から考えていくことになる。このとき使用できる両替所は ${n}$ の両替所のみである。よって経路は一意に決まって $s \rightarrow n \rightarrow t$ となる。 $n-2$ 年の場合は $n-1$ 年の最短経路と $n-2$ の最短距離を比較して小さい値を選択すれば良い。よって $n-1$ 年から考えていくことで各年のコストが $O(1)$ で求めることができたので解を求めることができた。