Editorial for Another Contest 2 Problem 1 - Poutine

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.

Let's start by solving the simplest possible case - when a trip must be done in 1 day.

In order to solve queries of this form, we're basically asking for the shortest path in the graph between those two vertices. With Floyd-Warshall, we can precompute answers for all of these queries in $\mathcal O(N^3)$ ~\mathcal O(N^3)~.

How does this help us when the number of days a trip can take is larger than 1? For a 2-day trip between $S$ ~S~ and $T$ ~T~, there must be some intermediate vertex $X$ ~X~ that we travel to in one day, and then we travel from $X$ ~X~ to $V$ ~V~. For each of these intermediate trips, we can use the precomputed values from the Floyd-Warshall application earlier. In general, to figure out the optimal path from $S$ ~S~ to $T$ ~T~ in $d$ ~d~ days, for $d > 1$ ~d > 1~, we use an optimal path from $S$ ~S~ to $X$ ~X~ in $d-1$ ~d-1~ days and then use an optimal path from $X$ ~X~ to $T$ ~T~ in one day.

Precomputing all of these values takes $\mathcal O(N^4)$ ~\mathcal O(N^4)~ time, and we can then answer queries in $\mathcal O(1)$ ~\mathcal O(1)~.

Comments

There are no comments at the moment.