Each edge in the graph has weight of 1,The graph may have cycles ,if a node has self loop it can be any distance from itself from 0 to infinity , depending on the no. of time we take the self loop.
We ll be asked multiple queries on a given graph of the form (distance , source) and the o/p is the list of nodes that are exactly at the given distance starting from the source vertex.
Constraints
1<=Nodes<=500 1<queries<=500 1<=distance<=10^9 I have a feeling ,there would be many repeated computations as the no. of nodes are small,but i am not able to figure out how do i reduce the problem in smaller problems.
What is the efficient way to do this?
I have solved the problem using bfs, but the constraint on distance is in order of 10^9 ,hence bfs is slow.
I have also tried using matrix exponentiation but its too slow ,for the given constraints. The problem has a time limit of 1 sec.
Length of longest simple path(without loop) won't exceed the number of nodes. So you need to update at most 501 times. In 501st round, if there exists a loop between u, v, distance between them will be longer, otherwise it will stay the same and there won't be a longer path between them.
https://www.codechef.com/AUG16/problems/SHAIKHGN