Let S denote the number of different speed limits occuring. It is clear that
S <= 500. Construct a new graph with N * S vertices, each one (n, v) corresponding
to the state of being at crossing n and having speed v. There is a directed
edge from vertex (n1, v1) to vertex (n2, v2) if and only if there is a road
r from crossing n1 to crossing n2 and one of the following holds:
1. V(r) = v2
2. V(r) = 0 and v1 = v2
If the weight of the edge is L(r) / v1, then the original problem exactly
corresponds to finding the shortest path in the new graph from (0, 70) to
(D, v) with v arbitrary.
To find the shortest path, Dijkstra's algorithm can be used. The graph does
not have to be constructed explicitly. In a typical instance, many of the
vertices will not be reached since they have a much longer travel time than
the destination. To solve all test cases, a priority queue must be implemented,
for example by using a heap.