Editorial for DMOPC '18 Contest 2 P3 - Thanksgiving Feast - Olympiads Online Judge

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 (d i s [s_{i}] [A] + d i s [s_{i}] [B])$ .

Time Complexity: $\mathcal{O}(K(N+M))$ $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 (d i s [A] [s_{i}] + d i s [B] [s_{i}])$ .

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

Comments

There are no comments at the moment.