Блог пользователя stdfloat

Does prority_queue take too much memory?
Автор stdfloat, 9 месяцев назад, По-английски

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?

  • Проголосовать: нравится
  • +14
  • Проголосовать: не нравится

»
9 месяцев назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

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)$ .

→ Ответить