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$ ~K~ buildings to any of the other $N$ ~N~ buildings. This can be done by BFSing from each of the $K$ ~K~ buildings as the source. Then the answer is $\min (dis[s_i][A]+dis[s_i][B])$ ~\min (dis[s_i][A]+dis[s_i][B])~.

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

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

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

Comments

There are no comments at the moment.