Dhruv_gheewala's blog

By Dhruv_gheewala, history, 2 months ago, In English,

Problem Link
Solution Link

Can anyone please help me, I am getting MLE(Memory Limit Exceeded) in this question.
I have tried my best to figure out, Why i am getting MLE, But i can't figured it out.
So, If you know anything to pass MLE, Please comment it !!

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Your code is full of definitions. I cannot understand that code. Sorry. Anyways, tell me when you found an answer, how did you track the paths? I saw that you used a stack. Can you explain what you've done to obtain that path after you found the shortest one?(Method you used to back track it)

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

    i'm getting answer in sssp, where sssp[node_num].cost is cost to reach node_num from root. and sssp[node_num].p will give parent of node_num.

    and for path, in that quetion, we have to give path from 1 to n. so i m pushing values in stack

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

      Okay I just found the cause for the memory limit:

      priority_queue<pii, vector<pii>, greater<pii>> pq;
      

      Why would you use a whole vector inside Dijkstra priority queue?

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

        what do you mean? can you please elaborate it?

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

          You are using a vector inside a priority queue. What is the usage of that vector?

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

            see here .

            we have to use vector, bcoz we need some nodes in queue. so we have to store them. so vector is needed. if i m wrong then what can i use ?

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

              So you are storing the nodes inside a vector that is inside a priority queue so you can print those nodes if you found an answer. Am I right?

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

                no !!

              • »
                »
                »
                »
                »
                »
                »
                »
                2 months ago, # ^ |
                Rev. 2   Vote: I like it 0 Vote: I do not like it

                suppose, we have relaxed node 4, 7, 9. then we have to store them in to queue, such that that node can relax other nodes.

                i think, vector written inside template, is to tell that priority queue will use vector to store values. isn't it?

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

                  Oh I see. Sorry I thought you used a vector inside the priority queue. Nevermind. Anyways, I just got you accepted with your code: Your code What you were missing was that if the node was visited before, then do not push. You were pushing nodes even if it was visited. This causes a very long queue which is useless as when the turn comes on the node that was already visited, you just pop it and do nothing. So instead, you would use a condition which is: &&!vis[v.ff]

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

    thank you very much for giving your time !!