Bellman-Ford

I too

Edited by author 21.04.2004 00:39

I used two SSSP algo (BFS + DFS) to solve the problem. Can it be done with only one ?

how to determinate the shortest route??? Why in the test input  the criminal goes to 85 and not to 10 or 75????

First do BFS with the first node in the criminal's route. Save the result in the array d1. Do another BFS with the last node in the criminal's route, and save the result in the array d2. For any node i, if d1[i]-d2[i]=m-1, then i is an answer.

The graph is always connected.

I build BFS traversal tree by giving priorities to points on the route (i.e. advance them first). Children of the last route node gain privelege for the rest of traversal (if you process nodes in the order they were first visited, this condition is automatic because they will be added prior to any other nodes during last privileged propagation).

After BFS tree is ready, nodes reachable from last node on the route inside that tree form the answer.

Edited by author 01.08.2008 05:09