For 1149D - Abandoning Roads I implemented this code using a priority queue. This is tutorials logic. And took 639ms.
But when I implemented same logic using a single normal queue it took 280ms. ( My code ).
Can any one tell me why without priority queue Dijkstra working much faster. Please help me to understand the complexity for 2nd code ( without priority queue ) . I understood the complexity of the 1st code ( with priority queue ).
Priority Queue is a implemented as a Max Heap, therefore the push() operation takes O(logn). On the other hand, queue can be implemented using linked-lists resulting in a O(1) push() operation. Remember that priority-queue sorts the elements while queue doesn't. That's why the queue implementation is faster as you get rid of the O(log(n)) factor.
But I implemented Dijkstra using queue. Many node may update multiple time. Normally Dijkstra using normal queue has O(n^2) complexity.