Dijkstra Algorithm using Priority queue in C++

Revision en3, by Jady, 2023-04-12 13:24:54

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

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English Jady 2023-04-12 13:24:54 104
en2 English Jady 2023-04-12 10:15:08 137 (published)
en1 English Jady 2023-04-12 10:12:19 630 Initial revision (saved to drafts)