Hi! I tried to implement the dijkstras algorithm using a priority queue for a better time complexity. However I am running into some problems as it’s not passing all test cases at an online judge. Can you please detect the error
Given is my code:-
Thanks
@Arpan_Goswami,
In your code, if you find a child with lesser distance, you push a new pair into to the pq, but the old pair of that child and it’s old distance is still in pq, which at some point would come out as top of pq, and waste an iteration, increasing runtime.
Thus rather use set instead of pq, and when you get a lesser distance for a child, first erase the old pair then push the new pair.
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.
It was giving WA not TLE