← All solutions

This problem may at first look like some sort of max flow problem, but even if the large size of the graph does not scare you away from this approach, I am not aware of any way of modeling the problem this way.

Consider instead the following approach. Let U (u, v) be true if every path from intersection u to intersection v has a unique cost. If U (1, N ) is true it is clear that no tolls need to be added, so assume from now on that U (1, N ) is not true. Now, suppose there is some vertex v such that both U (1, v) and U (v, N ) is false. In this case, no solution can possibly exist, since such a solution would have to incur a toll both on some road “before” v and on some road “after” v in order to ensure that all paths have unique costs.

Let us then suppose that no such vertex v exists, i.e., that either U (1, v) or U (v, N ) is true for every v. In this case, a solution can be constructed as follows: Let us say that an edge (u, v, c) from u to v of cost c is pivotal if it has the property that U (1, u) is true but U (1, v) is false. Pivotal edges have the following nice properties:

• The fact that U (1, 1) is true but U (1, N ) is false, together with the fact that if U (1, u) is false and there is an edge from u to v, then U (1, v) is also false implies that every route from 1 to N contains exactly one pivotal edge.
• The fact that U (1, v) is false implies that U (v, N ) is true.

Let C (1, N ) denote the maximum length of a path from 1 to N Now consider adding a toll of C (1, N ) − C (1, u) − C (v, N ) − c to every pivotal edge (u, v, c), if this number is positive (note that it can not be negative). By the two properties above, it is now easily shown that every route from 1 to N has at most one toll and a total cost of exactly C (1, N ).

To make an efficient solution out of this, note that the only quantities we actually need are those of the form U (1, v), U (v, N ), C (1, v) and C (v, N ), and all such values can be computed in linear time using dynamic programming.