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 two codes are identical. I just commented the call of a function and called the other in main!
"The two codes are identical, I just replaced a function with a completely different function."
The functions
DISTanddisare not equivalent. NamelyDIST(which is where your code failed) can return negative values. I am not going to verify it but I suspect that if you useDISTyour 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.
Thank you very much