stdfloat's blog

Does prority_queue take too much memory?
By stdfloat, 9 months ago, In English

UPD: I suppose no. Thanks lrvideckis for explaining my mistake in this comment.

I think PQ takes too much memory because of what happened in CF Round 923.

In this contest, because of I couldn't solve E, I read F, after some time I found solution. In the end of my solution, I have to find any path from $$$mn.ss.ss$$$ to $$$mn.ss.ff$$$ which doesn't contain a node more than one time, in this code I used dijikstra for it(I don't know why I didn't use bfs). And it used more than 256 megabytes.

Today, I used bfs instead of dijikstra in this code, and I suprised, it took only 43 megabytes. In time 2, in memory 6 times smaller than previous code. I'm sad about I didn't use bfs in contest, but I'm happy about I learned a lesson.

Did you have any experience like these?

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

»
9 months ago, # |
  Vote: I like it +13 Vote: I do not like it

245612146

I fixed 2 bugs in your dijkstra: overflow, and you need to continue when distance in the dist array doesn't equal distance on the PQ

https://cp-algorithms.com/graph/dijkstra_sparse.html

Among these pairs we are only interested in the pairs where the first element is equal to the corresponding value in  $d[]$ , all the other pairs are old. Therefore we need to make a small modification: at the beginning of each iteration, after extracting the next pair, we check if it is an important pair or if it is already an old and handled pair. This check is important, otherwise the complexity can increase up to  $O(n m)$ .

→ Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    actually, the not-continueing-bug I made once 35532768 and then switched to set implementation of dijkstras for a couple years then realized my mistake

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

    Thanks, I didn't know it.

    → Reply