Editorial for WC '17 Contest 1 S3 - Crosscountry Canada

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.

This problem can be reinterpreted as asking for the shortest path on an implicit directed, weighted graph.

Each node in the graph should represent a particular state which you may be in during your trip. This can be described by a pair of integers $\{i, t\}$ ~\{i, t\}~, where $i$ ~i~ is the city you're currently in, and $t$ ~t~ is the number of minutes which have gone by since your last Tim Horton's visit (or since the start of your trip). In total, there are $\mathcal O(NL)$ ~\mathcal O(NL)~ nodes.

The edges in this graph should then correspond to valid transitions between such states, of which there are two types. The first type of transition involves stopping at a Tim Horton's. For each node $\{i, t\}$ ~\{i, t\}~ such that $R_i = 1$ ~R_i = 1~, there exists an edge to node $\{i, 0\}$ ~\{i, 0\}~ with weight $T$ ~T~. The second type of transition involves driving along a road. For each road $i$ ~i~ and value $t$ ~t~, there exists an edge from node $\{A_i, t\}$ ~\{A_i, t\}~ to node $\{B_i, t+C_i\}$ ~\{B_i, t+C_i\}~ with weight $C_i$ ~C_i~, as long as $t+C_i \le L$ ~t+C_i \le L~. There's also a similar edge for taking the road in the opposite direction. In total, there are $\mathcal O((N+M) \times L)$ ~\mathcal O((N+M) \times L)~ edges.

With this interpretation, the answer is the length of the shortest path from node $\{1, 0\}$ ~\{1, 0\}~ to any node $\{N, t\}$ ~\{N, t\}~. This can be computed using the well-known "Dijkstra's algorithm" in $\mathcal O(E \log V)$ ~\mathcal O(E \log V)~ time, where $E = (N+M) \times L$ ~E = (N+M) \times L~ and $V = NL$ ~V = NL~.

Comments

There are no comments at the moment.