[closed] Is set-based Dijkstra is faster then priority_queue-based one?
Difference between en2 and en3, changed 9 character(s)
When I was a little child I learned a lot (indirectly via the [website](https://e-maxx.ru/algo/) which also have a [community-driven](http://github.com/e-maxx-eng) [english transation](https://cp-algorithms.com)) from [user:e-maxx,2021-01-22].(Orz). ↵

In particular, there is a post about [Dijkstra on sparse graphs](https://e-maxx.ru/algo/dijkstra_sparse) ([English version](https://cp-algorithms.com/graph/dijkstra_sparse.html). It is mentioned there that [priority_queue](http://www.cplusplus.com/reference/queue/priority_queue/?kw=priority_queue) is based on [heaps](https://en.wikipedia.org/wiki/Binary_heap), thus has smaller hidden constant then [set](http://www.cplusplus.com/reference/set/set/?kw=set) which is based on [RB-trees](https://en.wikipedia.org/wiki/Red–black_tree). Explanation makes perfect sense. ↵


I got back from quite a long break from CP and checked the recent [contest:1473] for a warm up. There was a nice problem [problem:1473E] authored by [user:Neon,2021-01-22] which required Dijkstra's algorithm. So I used the priority_queue based one from my template [submission:105061903] and got TLE 61. I thought of several bad words and started to optimize. Eventually, I tried the set-based solution and got AC [submission:105066945]. For your convenience, there is a diff between the submissions:↵

![ ](/predownloaded/c4/72/c4723ba6706419b4c6a4236d148185dd9fe92719.png)↵

Is it some other hidden bug in my code, or is set-based Dijkstra works faster then priority_queue one? When and why?↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English Infoshoc 2021-01-22 17:26:37 9
ru3 Russian Infoshoc 2021-01-22 17:26:18 10
en2 English Infoshoc 2021-01-22 17:14:53 6 Tiny change: 'sion:105066945] and got ' -> 'sion:105061903] and got '
ru2 Russian Infoshoc 2021-01-22 17:14:38 6 Мелкая правка: 'sion:105066945] и получи' -> 'sion:105061903] и получи'
ru1 Russian Infoshoc 2021-01-22 16:53:43 1316 Первая редакция перевода на Русский
en1 English Infoshoc 2021-01-22 16:47:25 1587 Initial revision (published)