Ahmed-Yasser's blog

Memory Limit Exceeded test 2 without a proper reason!
By Ahmed-Yasser, 4 years ago, In English

While I was trying to solve a problem with dijkistra, something strange happened. I got an MLE test 2, but I discovered that after I changed some lines, which are not supposed to cause an MLE, with the corresponding lines in an AC code , it got AC. I'm now stuck in trying to understand why that happened!

The problem

The MLE solution

The AC solution

The two codes are identical. I just commented the call of a function and called the other in main!

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

»
4 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

"The two codes are identical, I just replaced a function with a completely different function."

The functions DIST and dis are not equivalent. Namely DIST (which is where your code failed) can return negative values. I am not going to verify it but I suspect that if you use DIST your graph will have a negative cycle which causes your Dijkstra to go to an infinite loop.

Here are the three first test cases of test 2. Even there, your code fails so it should be enough to debug.

Test case
→ Reply