Блог пользователя A.ElGamal

a problem with Dijkstra (visited boolean array)
Автор A.ElGamal, 11 лет назад, По-английски

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

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
11 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
11 лет назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

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.

→ Ответить