Editorial for Baltic OI '02 P4 - Bicriterial Routing


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Let K be the upper limit on the road toll. The cost of any route is then limited by nK.

The exemplary solution is a dynamic one. For each k from 0 to nK and for all vertices, one computes the minimal traveling time from s to the given vertex with the fee equal to exactly k.

Initialization for k = 0 is just an application of Dijkstra's algorithm for the graph limited to these edges with toll c = 0. For bigger k we first calculate the minimal time based on the previously computed results and assuming that the last edge on the route has a positive toll (this is done for all edges). Next we take into account edges with toll c = 0, again using Dijkstra's algorithm.

Results calculated for vertex e give us the final result. This algorithm has time complexity \mathcal O((n + m \log n) \cdot nK) — Dijkstra's algorithm is implemented using a heap. Memory complexity is \mathcal O(nK + m), since we can focus just on the last K+1 rows of the array of minimal traveling times (except for e).


Comments

There are no comments at the moment.