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

Dijkstra Algorithm using Priority queue in C++
Автор Jady, история, 19 месяцев назад, По-английски

I was trying to solve CSES Shortest Routes I using priority_queue. However, I faced TLE even though I was storing negative of distance in it. After a bit of reading on CP-Algo's Page, they said that

The main difference to the implementation with set is that in many languages, including C++, we cannot remove elements from the priority_queue (although heaps can support that operation in theory).

I have a question regarding this: What happens when pq.pop() is called? Does it not remove the top element from pq?

PS: CF Rookie here, Please do not downvote. Update: Explained on USACO

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

»
19 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Yes. In priority_queue, only the top element can be deleted. But in the set, any element can be deleted.

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

It was meant that you cannot remove any element other than top element. When distance to vertex is updated you add it to the priority queue, but it may happen that after being added it will get updated again with even smaller distance. But the old one couldn't be removed, so you have to check whether you have handled this vertex before.

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

    I agree. But since the updated new distance is always smaller than the old one, I should get only the latest updated pair (i.e., the smallest distance) from priority_queue and not the older one. Doesn't this reduce the need to check?

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

      No it doesn't, you can see full explanation here

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

        Thanks. I get it now!

        The last test case contains 100000 destinations and 149997 flights. City 1 has flights to cities 2 through 50000. Cities 2 through 50000 have flights to city 50001. City 50001 has flights to cities 50002 through 100000. Without the continue , after the program pops cities 1 through 50000 off the queue, the priority queue will contain 49999 routes that end at city 50001. Every one of the 49999 times city 50001 is popped off the queue and processed, we must iterate over all of its outgoing flights (to cities 50002 through 100000). This results in a runtime of $$$\Theta(N^2\log N)$$$ , which will TLE.

        → Ответить