Why did this TLE? Cook-a-Code AJP

Code: https://www.codechef.com/CACD2020/problems/AJP
Explanation:
I used BFS in series
IDEONE: https://ideone.com/ruC0wH
I want to know if there’s a more efficient way to solve this and please move the questions to practise section. :slight_smile:

@shim98 Your code is just passing the TC’s .i.e 0.91 sec. Hence it is at threshold of time limit. Core idea is BFS , make sure you optimize it a little more.

Okay thank you :slight_smile:
Will you be posting the editorials soon?

I think you can use parallel bfs to do it faster.The main idea is that if it’s closer to something else, We don’t need to check from there. Therefore, we can use a vector of queues, that store distance and the node. from there we use bfs on each element in the vector, until We have used up all the nodes at the current distance. For example, If the queue only contains those with distance 2, we search from all of them, and when all of them are over, we go to the next queue in the vector. After we go through all the elements in the vector, we now check all the elements at distance 3 and so on.