各 \(i\) に対して、都市 \(1\) から社用車のみを使って都市 \(i\) まで行くときにかかる時間の最小値を \(X_i\)、都市 \(i\) から電車のみを使って都市 \(N\) まで行くときにかかる時間の最小値を \(Y_i\) とします。

都市 \(i\) で社用車から電車に乗り換えることにすると、このときかかる時間の最小値は \(X_i + Y_i\) であることより、本問題の答えは \(\min (X_i + Y_i)\) となります。ただし、社用車のみを使う場合は \(i = N\) に、電車のみを使う場合は \(i = 1\) に対応します。

\(X_i\) たちは dijkstra 法を用いることで時間計算量 \(O(N^2)\) で求めることができ、都市 \(i\) から電車のみを使って都市 \(N\) まで行くときにかかる時間の最小値は都市 \(N\) から電車のみを使って都市 \(i\) まで行くときにかかる時間の最小値と等しいことを利用すると、\(Y_i\) たちも同様に求めることができます。