Editorial for Another Contest 2 Problem 1 - Poutine - Olympiads Online Judge

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)$ $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)$ $O (N^{4})$ time, and we can then answer queries in $\mathcal O(1)$ $O (1)$ .

Comments

There are no comments at the moment.