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 to T. This runs in \mathcal O(K(N+M)) time.

We can reduce this to \mathcal O(M^2) time by noticing that there are only \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.