Dijkstra with the default priority_queue

This Dijkstra passes on tiny graphs but on larger ones returns distances that are sometimes too large, and the profiler shows far more heap pops than expected — nearly one per edge relaxation rather than one per settled vertex. The graph has only non-negative weights. Find the bug.

1#include <iostream>
2#include <queue>
3#include <vector>
4#include <climits>
5using namespace std;
6 
7vector<int> dijkstra(int n, const vector<vector<pair<int,int>>>& adj, int src) {
8  vector<int> dist(n, INT_MAX);
9  vector<bool> done(n, false);
10  priority_queue<pair<int,int>> pq;      // (dist, vertex)
11  dist[src] = 0;
12  pq.push({0, src});
13 
14  while (!pq.empty()) {
15    auto [d, u] = pq.top(); pq.pop();
16    if (done[u]) continue;
17    done[u] = true;
18    for (auto [v, w] : adj[u]) {
19      if (dist[u] + w < dist[v]) {
20        dist[v] = dist[u] + w;
21        pq.push({dist[v], v});
22      }
23    }
24  }
25  return dist;
26}
27 
28int main() {
29  int n = 4;
30  vector<vector<pair<int,int>>> adj(n);
31  auto add = [&](int a, int b, int w) { adj[a].push_back({b, w}); adj[b].push_back({a, w}); };
32  add(0, 1, 1); add(1, 2, 1); add(0, 2, 5); add(2, 3, 1);
33  for (int d : dijkstra(n, adj, 0)) cout << d << ' ';   // expected: 0 1 2 3
34}

1. What ordering does std::priority_queue<pair<int,int>> use by default? Which element does top() return?
2. Trace the algorithm on the given graph. At which pop does the done optimisation settle a vertex with a non-final distance?
3. Give three ways to obtain a min-heap in C++ and state which you would use in an interview.
4. Write the corrected code.
5. State the complexity of the corrected algorithm.