AOJ 2371 TransferTrain - okaduki's diary

概要

電車で目的地まで行くための最短経路を求めるというよくある感じの問題。

$N$ 本の路線がありそれぞれの路線は $a_i$ 個の駅からなる。一つの路線について駅 $s_1,\ldots,s_{a_i}$ とそれらの間の所要時間 $t_1,\ldots,t_{a_i - 1}$ が与えられる。電車は両方向にあるのでどちら向きに移動しても良い。

また、同じ駅が複数回現れる (異なる路線はもちろん、同じ路線でもありうる)とき、その駅は乗り換え駅で、時間 $T$ で乗り換えることができる。

このとき今いる駅から目的駅までの最短時間と乗り換え回数を求めよ。最短経路が複数あるときは乗り換え回数が最小のものを求めよ。

制約: $1 \leq N \leq 5\times 10^4,\ \sum_{i=1}^{N}a_i \leq 10^5$

解法

Dijkstra.

普通に路線ごとに $s_1 \overset{(t_1,0)}\longleftrightarrow s_2 \overset{(t_2,0)}\longleftrightarrow \cdots$ と辺を張る。辺のコストは(かかる時間、乗り換え回数)を表している。

乗り換えのために同じ駅同士でコスト $T$ の辺を張ると辺の数が大きくなりすぎるので次のように工夫する。駅名 $s$ に対して一つ頂点 $S$ を作っておき、駅 $s$ が現れるごとに $s \overset{(T,1)}\longrightarrow S$ と $S \overset{(0,0)}\longrightarrow s$ のように辺を張る。