Editorial for DMOPC '18 Contest 2 P3 - Thanksgiving Feast


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: r3mark

For the first two subtasks, compute the distances from each of the K buildings to any of the other N buildings. This can be done by BFSing from each of the K buildings as the source. Then the answer is \min (dis[s_i][A]+dis[s_i][B]).

Time Complexity: \mathcal{O}(K(N+M))

For the last subtask, instead BFS from A and B. The answer is \min (dis[A][s_i]+dis[B][s_i]).

Time Complexity: \mathcal{O}(N+M+K)


Comments

There are no comments at the moment.