Editorial for SAC '22 Code Challenge 4 Junior P5 - Obligatory Output Only Problem
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.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
There are many solutions to this problem.
The main prerequisite to solving this problem is knowing how Dijkstra's algorithm runs.
Below is an outline of a solution:
Connect to
with a weight of
.
Connect to
with a weight of
.
Finally, output ,
, and the edges on separate lines.
Time Complexity:
This graph will push into the queue many times since Dijkstra's algorithm will traverse
first and then discover
to
is better, but then
to
is better, and so forth.
will check each of its adjacent edges
, causing the
counter
variable to exceed .
Comments