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~).