Editorial for Mock CCC '18 Contest 1 S4 - A Graph 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: xiaowuc1

The most straightforward solution is to construct each graph and then do a BFS from $S$ ~S~ to $T$ ~T~. This runs in $\mathcal O(K(N+M))$ ~\mathcal O(K(N+M))~ time.

We can reduce this to $\mathcal O(M^2)$ ~\mathcal O(M^2)~ time by noticing that there are only $\mathcal O(M)$ ~\mathcal O(M)~ relevant graphs to construct - namely when an edge becomes eligible or when an edge becomes unavailable.

Comments

There are no comments at the moment.