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:↵
↵
↵
↵
Is it some other hidden bug in my code, or is set-based Dijkstra works faster then priority_queue one? When and why?↵
↵
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:↵
↵
↵
↵
Is it some other hidden bug in my code, or is set-based Dijkstra works faster then priority_queue one? When and why?↵
