Editorial for Hide n Seek


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.

Upon examination, we find that the total shortest time is the sum of the time from Griffy to one of the hiders, and hiders to hiders until everyone is found. The easiest way to find the shortest path is just to try all possible permutations! Thus, this turns into a recursive problem (or just use itertools permutations/algorithm next_permutation) to find the optimal path. First, compute using BFS the distance from each hider to each other hider, and Griffy. Using your method of choice, generate all possible paths and take the best. This solution works due to the fact that T \leq 5.

Skills needed: BFS, recursion

Time complexity: \mathcal O(T!+T(N+M))


Comments

There are no comments at the moment.