Блог пользователя noobied

Dijikstra !!
Автор noobied, история, 6 лет назад, По-английски

How this Solution works even if in priority queue the values stored are not weights.I think for Dijikstra to work we should maintain a priority queue which give the node whose distance is shortest from the source but in this implementation the priority queue gives the smallest node number

LINK:http://codeforces.net/contest/20/submission/30960352

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

»
6 лет назад, # |
← Rev. 3   Проголосовать: нравится -15 Проголосовать: не нравится

PLZZ HELP ME UNDERSTAND THIS SOLUTION AND IF I CHANGE THE PRIORITY QUEUE TO QUEUE IT GIVE TLE AT TEST NUMBER 28 I DIDN'T ABLE TO UNDERSTAND HOW PRIORITY QUEUE IS BENIFICIAL HERE INSTEAD OF A NORMAL QUEUE

→ Ответить
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    To begin with ,Dijkstra algorithm is a Greedy Algorithm.

    Therefore while using Dijkstra algorithm we have to use a priority queue (or similar data structure ) so that we can process the edge which have greater weight's before the edges that have a smaller weight.

    Reason for doing so :

    "if(dis[u] + w < dis[v])" this particular statement check's if the previous path has more weight than the current path. If we process the heavier edges first then this process becomes very much easier.

    That is the reason for using priority queue in Dijkstra.

    → Ответить
    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      But the code store the node number instead of wieghts in the priority queue

      → Ответить
      • »
        »
        »
        »
        6 лет назад, # ^ |
        ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

        In the question you are trying to solve , The author's solution is just storing the neighboring nodes.

        If u check TC # 28 , if you do not use a priority queue , u will have to process 50000 nodes. but using priority queue , 50000 will be above all the other nodes.

        And also there is a direct path from node 1 to node 50000.

        → Ответить
        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          In the originally linked solution, how does the priority queue know which nodes are closest (and thus should be processed first) when the priority queue only stores the node (instead of say, a pair<node, weight>)?

          → Ответить
»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I think the problem might have weak test case, and the TL is too tight for priority queue to pass (because of doubled runtime).

Counter case:

5 5
1 2 1
2 3 1
1 4 10
4 5 1
1 5 5

The linked code (and my own "AC" solution) prints "1 5" instead of "1 2 3 4 5".

→ Ответить