IkramulMurad's blog

Memory Limit Exceed on Dijkstra
By IkramulMurad, history, 8 years ago, In English

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

  • Vote: I like it
  • -5
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think it is a compiler bug, I change the int to long long int for cost, and not type cast it, and it got AC.

See 24563357 for info

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

    Thanks to Zun, I have found my fault. I wrote "int cost=pq.begin()->first;", where cost overflowed and became a negative value. That makes my Dijkstra function wrong.

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

      right, it is not a compiler bug. but i am confused. How did your this 24561391 AC?

      → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it -22 Vote: I do not like it

Try to replace int by long long int. It worked for me. I too implemented dijkstra from set method but it too gave me MLE :_)(I was taking int in both of them) . Just use long long int..both implementation (priority queue and set) will get accepted.

Thanks :) (This was my first comment ever on CF)

→ Reply