ワープする回数は高々 \(1\) 回に抑えられます．

(証明) \(2\) 回以上ワープしたとする．最初のワープを都市 \(a\) から都市 \(b\) ，最後のワープを都市 \(c\) から都市 \(d\) とすると，この間の移動には \((X_a+X_b+Y)+(X_c+X_d+Y)\) 分以上の時間がかかる．しかしこれらの代わりに都市 \(a\) から都市 \(d\) へワープすれば \(X_a+X_d+Y\) 分かかるので，時間を短縮できる．

都市 \(i\) から都市 \(j\) へ道路のみで移動するときの最短時間を \(dis[i,j]\) とします．ワープを使わない場合，答は \(dis[1,k]\) です．これは dijkstra 法で求められます．ワープを使う場合，答は \(\min_{i,j}(dis[1,i]+X_i+X_j+Y+dis[j,k])\) です．これを求める方法を考えます．

まず， dijkstra 法で \(\min_i(dis[1,i]+X_i)\) を求めます．すると，各 \(j\) について \(\min_i(dis[1,i]+X_i)+X_j+Y\) がわかり，あとは多始点 dijkstra 法で答が求まります．