TLE using queue but AC with priority_queue?

in the codeforces question djikstra?, i am getting TLE for using queue but AC for using priority_queue, i don’t understand why this is happening, please help!

Read how dijikstra works. You’ll automatically realise why priority queue works better.

Your first code is O(nm) and the second is O(m+n\log{n}). You can construct a counter - testcase By having two edges on each node, one with a large weight, and one with a small weight. You’ll notice that it will go through all n nodes for each edge with a large weight, and then come back and notice it could have done everything faster by just going to the other node. This is not a problem with the priority queue based algorithm.

1 Like