Editorial for COCI '21 Contest 4 #2 Autobus
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 , and storing the shortest distance between every pair of nodes. The time complexity is
.
To fully solve the problem we use dynamic programming. Let denote the length of the shortest path between
and
which uses at most
edges, and let
be the length of the (shortest) edge between
and
, or
if no such edge exists.
In the beginning, we initialize all the paths of length zero: and
for
. When making a transition from
to
, for each pair of nodes
, we try to go from
to some node
using at most
edges, and from
to
using just one edge:
The complexity is , which solves the third subtask.
Notice that the shortest path between two nodes cannot use more than 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
, we can set
and the answer will be the same.
Comments