Editorial for Baltic OI '02 P4 - Bicriterial Routing
Submitting an official solution before solving the problem yourself is a bannable offence.
Let be the upper limit on the road toll. The cost of any route is then limited by .
The exemplary solution is a dynamic one. For each from to and for all vertices, one computes the minimal traveling time from to the given vertex with the fee equal to exactly .
Initialization for is just an application of Dijkstra's algorithm for the graph limited to these edges with toll . For bigger 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 , again using Dijkstra's algorithm.
Results calculated for vertex give us the final result. This algorithm has time complexity — Dijkstra's algorithm is implemented using a heap. Memory complexity is , since we can focus just on the last rows of the array of minimal traveling times (except for ).
Comments