For each \(i\), let \(X_i\) be the minimum time required to travel from city \(1\) to city \(i\) only by company car, and \(Y_i\) be the minimum time required to travel from city \(i\) to city \(N\) only by train.

If you switch from company car to train at city \(i\), the minimum time required in this case is \(X_i + Y_i\); thus, the answer to the original problem is \(\min (X_i + Y_i)\). Here, using only company car corresponds to \(i = N\), and only train to \(i = 1\).

The values \(X_i\) can be computed in a total of \(O(N^2)\) time; also, the minimum time required to travel from city \(i\) to city \(N\) only by train equals that from city \(N\) to city \(i\), so the values \(Y_i\) can also be found in the same way.