Infoshoc's blog

[closed] Is set-based Dijkstra is faster then priority_queue-based one?
By Infoshoc, history, 4 years ago, In English

When I was a little child I learned a lot (indirectly via the website which also have a community-driven english transation) from e-maxx.(Orz).

In particular, there is a post about Dijkstra on sparse graphs (English version. It is mentioned there that priority_queue is based on heaps, thus has smaller hidden constant then set which is based on RB-trees. Explanation makes perfect sense.

I got back from quite a long break from CP and checked the recent Educational Codeforces Round 102 (Rated for Div. 2) for a warm up. There was a nice problem 1473E - Minimum Path authored by Neon which required Dijkstra's algorithm. So I used the priority_queue based one from my template 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 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?

  • Vote: I like it
  • +11
  • Vote: I do not like it

»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Uh, the two submission links are the same link. I thought that one of them was supposed to be TLE and the other is AC. Maybe link this one instead https://mirror.codeforces.com/contest/1473/submission/105061903

→ Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Reverse happened with demoralizer.His solution using set TLEed and priority queue worked. Here are submissions
With set(TLE): https://mirror.codeforces.com/contest/1473/submission/104326547
with pq (AC) : https://mirror.codeforces.com/contest/1473/submission/104327939

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This only the internal set VS PQ constant changes. Usually, when one codes Dijkstra with sets the old distance is removed from the queue on the update, and some memory is saved.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +28 Vote: I do not like it

      Yes that's right. Priority Queue method can be made faster though — make a custom comparator which compares only the first element of the pair. (It improves the constant factor by a lot in the worst case)

      → Reply
»
4 years ago, # |
← Rev. 5   Vote: I like it 0 Vote: I do not like it

You should check after popping if the current minimum distance to this node equals to the one popped, since a node can be popped multiple times if you use priority_queue and if you process each one it'll result in wasting a lot of time. For example, look at my code without checking 105069884 and with checking 104306045

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Oh actually nvm you do that, then I don't know what causes your TLE.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it +23 Vote: I do not like it

      He don't do it in a proper way: 105071086, without your comment I've never noticed this bug :)

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Wow, and I lived with this bug in the template! Thanks a lot!

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yeah, I know this fill bro, some bugs are really hard to notice, they live in template even after N >> 1 AC submits. I've recently found bug it my Modular class: comment

          → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +13 Vote: I do not like it

          This shows how bad it is to use pairs instead of classes with proper field names and comparator.

          → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Infoshoc (previous revision, new revision, compare).

→ Reply