Editorial for COCI '21 Contest 4 #2 Autobus


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.

We model the problem as a directed graph.

The first two subtasks can be solved by iterating over all paths of length k, and storing the shortest distance between every pair of nodes. The time complexity is \mathcal O(n^k+q).

To fully solve the problem we use dynamic programming. Let dp[d][x][y] denote the length of the shortest path between x and y which uses at most d edges, and let w[x][y] be the length of the (shortest) edge between x and y, or \infty if no such edge exists.

In the beginning, we initialize all the paths of length zero: dp[0][x][x] = 0 and dp[0][x][y] = \infty for x \ne y. When making a transition from d to d+1, for each pair of nodes (x, y), we try to go from x to some node z using at most d edges, and from z to y using just one edge:

\displaystyle dp[d+1][x][y] = \min_z dp[d][x][z]+w[z][y]

The complexity is \mathcal O(kn^3+q), which solves the third subtask.

Notice that the shortest path between two nodes cannot use more than n-1 edges (otherwise we would visit some node twice, i.e. we would have a cycle which could be removed to obtain a shorter path). Therefore, if k > n-1, we can set k = n-1 and the answer will be the same.


Comments

There are no comments at the moment.