Given the constraints of this problem (n <= 1E6), how can we solve this problem?
The naive brute force solution( O(n^2) ) checking all pairwise distances will fail. Any ideas will be appreciated.
I implemented a simple BFS for this problem, which should give the shortest path in this case, but got only 3 test cases correct.
My solution: http://pastebin.com/thVPJZbK
When I looked at the test data from this page: All INOI contest problems, the test outputs seemed to be having a non-optimal path (probably using DFS) from the source to the destination.
The problem description states that if multiple routes are possible, print any one of them. But it seems the server doesn't find my solution to be correct.