the problem is actually a 01 bfs based problem. Description In a graph if the weights are either 0 or 1 and we have to find shortest path from one node to another then 01 bfs algorithm can be used. Solution It is handled by a double ended queue(deque) where we insert the node at front if the edge directed to it has weight 0 and at back if the weight is 1. This is done because we propagate by always taking out the element from the front of the dequeue as naturally we want to process the node having less distance (just like Dijksta's algorithm) FIRST. here's the code for better understanding https://ideone.com/UOIv6U hope it helps. answered 21 Jan '16, 02:05
My code is very similar to yours, but there is some mistake its giving wrong answer.Can you please figure it out.
(22 Jan '16, 07:49)
this is the corrected code. You see that when we are using 01 bfs the best part is that we need not keep a visited array as the way of insertion in dequeue(front or back) is already doing that job i.e keeping the distance to a particular node to minimal. You can read more about it from http://codeforces.com/blog/entry/22276
(22 Jan '16, 19:15)
@thedark In question there is a constraint that we have to consider self pair also and there could be multiple paths between two nodes. But why we do not need to take any additional care about them.
(22 Jan '16, 23:36)
@arpit728 We are changing the distance of a node iff its distance is decreasing so it is just a fast version of dijkstra's algorithm and it will pick the path having least cost/distance between two nodes(IF MULTIPLE PATHS EXIST).
(23 Jan '16, 00:00)
@arpit728 self pair is not required. you can easily ignore them. as for multiple paths. it is possible that edges could be like 1>2 and 2>1 in which both are accepted
(23 Jan '16, 01:15)
showing 5 of 6
show all
