Dijkstra (Shortest Paths (Weighted) Sub-pattern)

// Dijkstra: always settle the closest unsettled node; its distance can't improve later.
// Works when every edge weight is >= 0.
vector<long long> dijkstra(int n, const vector<vector<pair<int, int>>>& adj, int src) {   // adj[u] = {v, w}
    const long long INF = LLONG_MAX;
    vector<long long> dist(n, INF);
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> pq;   // {dist, node}, min first
    dist[src] = 0;
    pq.push({0, src});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;                // stale entry: u was settled with a smaller d
        for (auto [v, w] : adj[u])
            if (d + w < dist[v]) {                // relax: a shorter way to v through u
                dist[v] = d + w;
                pq.push({dist[v], v});
            }
    }
    return dist;                                  // INF = unreachable
}