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.

Author: maxcruickshanks

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:

N = 10^5

Connect 1 to i (1 < i < N) with a weight of i.

Connect i to N with a weight of 2 \times (N-i).

Finally, output N, M, and the edges on separate lines.

Time Complexity: \mathcal{O}(M)

This graph will push N into the queue many times since Dijkstra's algorithm will traverse i first and then discover i to N is better, but then i+1 to N is better, and so forth.

N will check each of its adjacent edges (N-1), causing the counter variable to exceed 10^7.


There are no comments at the moment.