Editorial for GFSSOC '14 Winter J5 - Pursuit of Knowledge

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.

If you tried to run a BFS for each query, it is likely your code would've failed (unless it was in C++ or PyPy with good optimization). This is because the time cost is $Q(N+M)$ ~Q(N+M)~, where $Q$ ~Q~ is a ridiculously huge number. Notice that there are many more queries than possible source nodes. Therefore, all we need to do is run BFS from each possible source node and store the values in an answer array. For each query, just grab the value from the answer array. In total, this solution takes $N(N+M)$ ~N(N+M)~ time, a significant upgrade from the first.

Skills needed: BFS

Time complexity: $\mathcal O(N(N+M)+Q)$ ~\mathcal O(N(N+M)+Q)~

Note: The difficulty curve from J4 and J5 is quite steep. This question requires an algorithm known as Breadth First Search, which you can search up online.

Comments

0

pblpbl commented on Oct. 6, 2019, 10:39 p.m.

You can still pass with BFSing each query if you stop searching as soon as you find the end node

-6

4n0u4r commented on June 18, 2018, 8:24 p.m.

Floyd Warshall algorithm would also work just fine.

This comment is hidden due to too much negative feedback. Show it anyway.

-41

hezeyu2007001 commented on July 26, 2017, 2:37 p.m.

but there is no code

This comment is hidden due to too much negative feedback. Show it anyway.

9

dxke02 commented on Nov. 17, 2020, 10:36 p.m.

I think that the editorial is only to give you the idea to solve the problem.