uniolympiads Ελληνικά

Dijkstra

Single-source shortest paths with non-negative weights, in O((n+m)log⁡n)O((n + m) \log n).

When

A graph with weights ≥0\ge 0 and the question "minimum cost from ss". If all weights are equal, BFS is enough. If some are negative, you need Bellman–Ford.

The idea

BFS with a heap instead of a queue. Each time we take out the vertex with the smallest tentative distance. Because the weights are non-negative, no path through vertices that have not been taken out yet can be shorter. So the distance of this vertex is final.

The STL priority_queue has no decrease-key. Instead, we push the vertex again with the new distance and, when an old entry comes out, skip it: if (d > dist[u]) continue;. The heap can reach O(m)O(m) entries, but log⁡m≤2log⁡n\log m \le 2 \log n, so the complexity does not change.

The move that unlocks problems

State graph. In Flight Discount you can use a half-price coupon once. The state is the pair (city, have I used the coupon?), that is 2n2n vertices. From (u,0)(u, 0) you go to (v,0)(v, 0) at cost ww and to (v,1)(v, 1) at cost ⌊w/2⌋\lfloor w/2 \rfloor. Dijkstra runs unchanged.

In Investigation you want, besides the minimum cost, how many minimum routes there are. These are updated inside the relaxation: on a tie you add, on an improvement you replace.

Pitfalls

  • Distances in long long, "infinity" as LLONG_MAX. Do not add a weight to infinity. The code here never does, because it relaxes only from vertices that have left the heap.
  • Without the continue for stale entries the algorithm stays correct, but on a dense graph it becomes O(m2)O(m^2) in the worst case.

Code

No main: it goes below the #include lines, using namespace std and using ll = long long.

cpp/dijkstra.cpp
// Dijkstra with a binary heap: shortest paths from src, non-negative weights. O((n + m) log n).
// Stale heap entries (d > dist[u]) are skipped instead of decreased.
// Unreachable vertices keep LLONG_MAX.

vector<ll> dijkstra(const vector<vector<pair<int, ll>>>& adj, int src) {
    int n = adj.size();
    vector<ll> dist(n, LLONG_MAX);
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
    dist[src] = 0;
    pq.push({0, src});
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (d > dist[u]) {
            continue;
        }
        for (auto [v, w] : adj[u]) {
            if (d + w < dist[v]) {
                dist[v] = d + w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

Tested on 1,000 random cases against a slow, obviously correct solution, with AddressSanitizer and UndefinedBehaviorSanitizer (g++ (Ubuntu 13.3.0-6ubuntu2~24.04.1) 13.3.0, 2026-11-18 23:27 UTC).

Practice on CSES

In order: the first is the plain application, the rest need a twist.

More in the USACO Guide

In English, with more problems per level.