Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

Memory Limit Exceed on Dijkstra

Revision en1, by IkramulMurad, 2017-02-10 07:14:22

Hi, I was solving problem "20C — Dijkstra?". At first, I implemented through priority_queue. I got verdict "memory limit exceeded on test 31". I then realised that, if a single node relaxed more than once, priority_queue enqueue the node more than once. This may be the cause of memory limit exceed.

Then I have designed another algorithm with c++ std::set. I kept all the pair of cost and node number in that set. Then whenever a node to be relaxed, I firstly erase that node from the set, then update the node cost and insert to the set again. I believe this algorithm needs O(n) memory. Because there at most n pairs in the set. But I got verdict "memory limit exceeded on test 31" again. I don't know how it takes more memory or which test cases make it inefficient.

My implementation: http://ideone.com/2vNqOS

This is my first post. Thanks in advance. :)

Tags dijkstra, shortest path, memory limit

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English IkramulMurad 2017-02-10 07:14:22 905 Initial revision (published)