Editorial for Another Contest 2 Problem 1 - Poutine
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)~.
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~ and ~T~, there must be some intermediate vertex ~X~ that we travel to in one day, and then we travel from ~X~ to ~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~ to ~T~ in ~d~ days, for ~d > 1~, we use an optimal path from ~S~ to ~X~ in ~d-1~ days and then use an optimal path from ~X~ to ~T~ in one day.
Precomputing all of these values takes ~\mathcal O(N^4)~ time, and we can then answer queries in ~\mathcal O(1)~.