九州大学プログラミングコンテスト2014 D. 切符分割

研究室のプロコンでQUPC2014を1時間で解こうとしたら、3問しか解けなかった。

問題

D: 切符分割 - 九州大学プログラミングコンテスト2014 | AtCoder
電車の路線図が重み付き無向グラフG=(V, E)としてが与えられる。駅vから駅uまでの距離がd_vuであるとする。このとき駅v-u間の切符の値段は、要素数Kの数列x, fについて、1=x[0] <= d_vu < x[1]ならf[0]円, x[1] <= d_vu < x[2]ならf[1]円, ..., x[K-2] <= d_vu < x[K-1]ならf[K-2]円, x[K-1] <= d_vuならf[K-1]円とする。
このとき、2枚まで切符を使って良いとすると、スタート地点Sからゴール地点Gまで最小何円でたどり着けるか？

制約

2 <= |V| <= 30000
1 <= |E| <= 60000
1 <= K <= 100
x[i] < x[i+1] ならばf[i] < f[i+1]

解法

切符を二枚まで使ってよい、はスタートとゴールの間に、ある中継点が存在する、と考えられる。よって、ある中継点を決めたときの値段は、スタートから中継点までの最短距離と、中継点からゴールまでの最短距離がわかれば、求めることができる。

スタートから中継点までの距離は、一度Dijkstra法を使えば求められる。ただ、中継点からゴールまでの最短距離については、各点からゴール地点までの最短距離をそれぞれDijkstra法で計算していては間に合わない。しかし、このグラフは無向グラフなので、「中継点からゴールまでの最短距離」を、「ゴールから中継点までの最短距離」と言い換えれば、ゴールをスタートとしてDijkstra法をすれば、各中継点からゴールまでの最短距離を効率よく求めることができる。

距離がわかったあとは、地道にその距離に対応する値段を計算すればよい。(今回はK<=100なので、二分探索さえする必要がない)

計算量

O(|V|+|E|log|E|+|V|K)

コード

感想

問題文の上の方の例には切符を3枚使う例が書かれていて、計算間に合わない、となっていた。問題はよく読もう...