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 .

How does this help us when the number of days a trip can take is larger than 1? For a 2-day trip between and , there must be some intermediate vertex that we travel to in one day, and then we travel from to . 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 to in days, for , we use an optimal path from to in days and then use an optimal path from to in one day.

Precomputing all of these values takes time, and we can then answer queries in .