: std::set vs std::priority_queue for Dijkstra's algorithm

Hello,

I was trying to solve this problem on codeforces.
I realised that I had to implement Dijkstra’s in order to solve it. However, my submission that used priority_queue in the implementation received TLE.

However, the same algorithm but with set gives AC. I reckon that Insertion and Deletion in both set and priority_queue takes log(n) time. So, how is a set faster in this case?

Thank you

1 Like

Hi,

Priority queue in CPP is by default max heap. So your code is always fetching the farthest node instead of closest which is not optimal since in Dijkstra’s we pick node with minimum distance.

So to convert your priority queue from max heap to min heap you can insert negative distance like I did here. Or you can use greater as mentioned here.

Here is the diff from your TLE code.

PS - priority queue is 30 times faster than set. Source.

7 Likes