When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

A.ElGamal's blog

By A.ElGamal, 9 years ago, In English

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

  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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".

»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

In your submission with visited array, change:

#define INF 999999999

to

#define INF 1e14

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.