20C - Dijkstra? in this problem , I used standard dijkstra using (visited) boolean array so as not to use a node as a source node twice , the problem is that code worked well until test 31(worst case) (WA:-1 although a path already existed) when I commented if condition saying not to re-visit a visited node the code was accepted ... I cannot understand why this happened .. any help is appreciated
Using a 'visited' array, you are prohibiting the node to be relaxed more than once. It's not optimal as you can later figure smaller paths converging to the node you previously "blocked".
In your submission with visited array, change:
to
Imagine in a extreme case you need n - 1 edges(with weight 106) from node 1 to node N, then with N = 105 and Weight = 106, the cost of the path will be almost 1011 and your INF value is small.
Sorry for my poor english.