Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

Given a directed weighted graph with self loops ,find the list of nodes that are exactly k dist from a given node x?

Revision en1, by atomicemc2, 2016-08-08 08:53:39

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.

Tags directed graph, dynamic programming, cycles, path

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English atomicemc2 2016-08-08 08:53:39 1030 Initial revision (published)