SyntaxPilot
Courses/Competitive Programming/Lesson 46
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Competitive Programming · Lesson 46 of 90

Shortest paths in contests: Dijkstra variants, multi-source, state graphs

queued

These are the notes for Competitive Programming episode 46, the second episode of the graphs section. Last episode every step cost 0 or 1; now the roads have real lengths. Three original problems build three contest patterns. Bus Routes: last episode's BFS prints 10 where the answer is 3 (Wrong Answer), because fewest roads is not shortest length. A water tanker that always confirms the nearest waiting town gives Dijkstra's algorithm: a min priority queue, the stale-entry check, and long long distances (with int, two roads of 10^9 print -294967296). Nearest Hospital: one Dijkstra per hospital is Time Limit Exceeded with 10^5 hospitals; putting every hospital in the queue at distance 0 (multi-source Dijkstra, a virtual super source) is one run. One Coupon: halving the biggest road of the shortest path prints 15 where 14 is right; making the coupon part of the node, (town, coupon used?), turns it into plain Dijkstra on a state graph, checked against trying every road in a stress test. Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs below are real.

The real-life hook

In May, a water tanker lorry leaves the depot and every town on the route wants to know how far away the water is. A smart dispatcher does this: among the towns still waiting, confirm the nearest one: nothing can reach it faster, because every other route to it would pass through a town that is even farther away, and roads never have negative length. Then he phones that town's neighbours: "I can reach you in this many kilometres". Each town keeps its best offer. Repeat. That is Dijkstra's algorithm, with the waiting towns kept in a priority queue, smallest offer first.

If there are many depots, they all send a tanker at the same moment: that is multi-source Dijkstra. And if the driver holds one discount coupon for a toll road, the question "where am I?" is not enough; he also has to remember "have I used my coupon yet?": that is a state graph.

Problem D1 · Bus Routes

(Written for this course, in the style of an AtCoder Beginner Contest problem.)

n towns, m two-way roads; road i joins a_i and b_i and has length w_i. Print the shortest total length from town 1 to town n, or −1 if town n cannot be reached.

  • Input: n and m (2 ≤ n ≤ 2 · 10^5, 0 ≤ m ≤ 2 · 10^5), then m lines a_i b_i w_i (1 ≤ w_i ≤ 10^9).
  • Output: the shortest length, or −1.
Input Output
4 4 / 1 2 1 / 2 3 1 / 3 4 1 / 1 4 10 3 (1 → 2 → 3 → 4)
4 2 / 1 2 5 / 3 4 5 -1
3 2 / 1 2 1000000000 / 2 3 1000000000 2000000000

The obvious attempt: BFS (Wrong Answer)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, int>>> adj(n + 1);   // (neighbour, length)
    for (int i = 0; i < m; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        adj[a].push_back({b, w});
        adj[b].push_back({a, w});
    }
    vector<ll> dist(n + 1, -1);
    queue<int> q;
    dist[1] = 0;
    q.push(1);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (auto [v, w] : adj[u])
            if (dist[v] == -1) {
                dist[v] = dist[u] + w;            // first visit wins
                q.push(v);
            }
    }
    cout << dist[n] << "\n";
}
10

BFS reaches town 4 first using one road (length 10), and first visit wins. With lengths, the path with the fewest roads is not the shortest.

Dijkstra's algorithm

  1. dist[1] = 0, every other dist = ∞ (LLONG_MAX). Put (0, 1) in a min priority queue.
  2. Take out the pair (d, u) with the smallest d. If d > dist[u], this is an old offer that was beaten later: a stale entry, skip it.
  3. Otherwise u is final. For every road (u, v, w): if d + w < dist[v], improve dist[v] (relaxation) and push (dist[v], v).

Why is the smallest waiting town final? Any other path to u leaves the set of final towns at some town x with dist[x] ≥ d (u was the smallest), and then adds roads of length ≥ 0. So it is at least d. This is exactly where non-negative lengths are needed: with a negative road, a later path could become shorter, and Dijkstra is wrong (use Bellman–Ford instead).

priority_queue in C++ is a max-heap by default; greater<> turns it into a min-heap. Instead of deleting old entries (which priority_queue cannot do), we push a new pair every time a distance improves and skip stale ones when they come out (lazy deletion). The queue holds at most m + 1 pairs, so the total time is O((n + m) log m).

Taken out Final Offers made Queue after
(0, 1) 1 = 0 2: 1, 4: 10 (1, 2) (10, 4)
(1, 2) 2 = 1 3: 2 (2, 3) (10, 4)
(2, 3) 3 = 2 4: 3 (3, 4) (10, 4)
(3, 4) 4 = 3 — (10, 4)
(10, 4) stale: 10 > 3, skipped empty
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, int>>> adj(n + 1);   // (neighbour, length)
    for (int i = 0; i < m; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        adj[a].push_back({b, w});
        adj[b].push_back({a, w});
    }
    const ll INF = LLONG_MAX;
    vector<ll> dist(n + 1, INF);
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;   // smallest first
    dist[1] = 0;
    pq.push({0, 1});
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (d > dist[u]) continue;                // stale entry: skip
        for (auto [v, w] : adj[u])
            if (d + w < dist[v]) {
                dist[v] = d + w;
                pq.push({dist[v], v});
            }
    }
    cout << (dist[n] == INF ? -1 : dist[n]) << "\n";
}
3
-1
2000000000

The int overflow

The same code with int distances and INT_MAX as infinity:

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, int>>> adj(n + 1);   // (neighbour, length)
    for (int i = 0; i < m; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        adj[a].push_back({b, w});
        adj[b].push_back({a, w});
    }
    const int INF = INT_MAX;
    vector<int> dist(n + 1, INF);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;   // smallest first
    dist[1] = 0;
    pq.push({0, 1});
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (d > dist[u]) continue;                // stale entry: skip
        for (auto [v, w] : adj[u])
            if (d + w < dist[v]) {
                dist[v] = d + w;
                pq.push({dist[v], v});
            }
    }
    cout << (dist[n] == INF ? -1 : dist[n]) << "\n";
}
-294967296

2 · 10^9 does not fit in a 32-bit int (the largest is 2,147,483,647). Signed overflow is undefined behaviour; in practice it wraps around to 2 · 10^9 − 2^32 = −294,967,296. A path can have 2 · 10^5 roads of 10^9 each, so distances must be long long (up to 9.2 · 10^18).

Problem D2 · Nearest Hospital

(Written for this course.)

Same kind of road map; k of the towns have a hospital. For every town print the distance to its nearest hospital, or −1 if no hospital can be reached.

  • Input: n, m, k (1 ≤ k ≤ n ≤ 2 · 10^5, m ≤ 2 · 10^5), then the k hospital towns, then m roads a b w (1 ≤ w ≤ 10^9).
  • Output: n numbers.
Input Output
5 4 2 / 1 5 / 1 2 3 / 2 3 4 / 3 4 1 / 4 5 2 0 3 3 2 0
4 1 1 / 2 / 1 2 7 7 0 -1 -1

The obvious attempt: one Dijkstra per hospital (TLE)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

vector<ll> dijkstra(vector<vector<pair<int, int>>> &adj, int s) {
    vector<ll> dist(adj.size(), LLONG_MAX);
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;
    dist[s] = 0;
    pq.push({0, s});
    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;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, k;
    cin >> n >> m >> k;
    vector<int> hosp(k);
    for (int &h : hosp) cin >> h;
    vector<vector<pair<int, int>>> adj(n + 1);
    for (int i = 0; i < m; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        adj[a].push_back({b, w});
        adj[b].push_back({a, w});
    }
    vector<ll> best(n + 1, LLONG_MAX);
    for (int h : hosp) {                         // one Dijkstra per hospital
        vector<ll> d = dijkstra(adj, h);
        for (int v = 1; v <= n; v++) best[v] = min(best[v], d[v]);
    }
    for (int v = 1; v <= n; v++)
        cout << (best[v] == LLONG_MAX ? -1 : best[v]) << " \n"[v == n];
}
0 3 3 2 0

With n = 2 · 10^5 and k = 10^5 (the graph built inside the program):

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

vector<ll> dijkstra(vector<vector<pair<int, int>>> &adj, int s) {
    vector<ll> dist(adj.size(), LLONG_MAX);
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;
    dist[s] = 0;
    pq.push({0, s});
    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;
}

int main() {
    int n = 200000, k = 100000;              // worst case, built here
    mt19937 rng(46);
    vector<vector<pair<int, int>>> adj(n + 1);
    auto road = [&](int a, int b) {
        int w = rng() % 1000 + 1;
        adj[a].push_back({b, w});
        adj[b].push_back({a, w});
    };
    for (int v = 2; v <= n; v++) road(v, rng() % (v - 1) + 1);
    for (int i = 0; i < n; i++) road(rng() % n + 1, rng() % n + 1);
    vector<int> hosp(k);
    for (int &h : hosp) h = rng() % n + 1;
    vector<ll> best(n + 1, LLONG_MAX);
    for (int h : hosp) {                         // one Dijkstra per hospital
        vector<ll> d = dijkstra(adj, h);
        for (int v = 1; v <= n; v++) best[v] = min(best[v], d[v]);
    }
    ll total = 0;
    for (int v = 1; v <= n; v++) total += best[v];
    cout << "sum of distances: " << total << "\n";
}
Time Limit Exceeded (stopped after 8 seconds)

k full runs: about 10^5 × 4 · 10^5 × 18 ≈ 10^11 steps.

Multi-source Dijkstra

The distance to the nearest hospital is the shortest path that may start at any hospital. Imagine one extra town, a super source, joined to every hospital by a road of length 0: one Dijkstra from it answers every town. We don't build it; we just start with every hospital in the queue at distance 0. One run, O((n + m) log m), whatever k is. (The same trick works for BFS: multi-source BFS, e.g. "distance from every cell to the nearest fire".)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, k;
    cin >> n >> m >> k;
    vector<int> hosp(k);
    for (int &h : hosp) cin >> h;
    vector<vector<pair<int, int>>> adj(n + 1);
    for (int i = 0; i < m; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        adj[a].push_back({b, w});
        adj[b].push_back({a, w});
    }
    vector<ll> best(n + 1, LLONG_MAX);
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;
    for (int h : hosp) {                         // every hospital starts at 0
        best[h] = 0;
        pq.push({0, h});
    }
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (d > best[u]) continue;
        for (auto [v, w] : adj[u])
            if (d + w < best[v]) { best[v] = d + w; pq.push({best[v], v}); }
    }
    for (int v = 1; v <= n; v++)
        cout << (best[v] == LLONG_MAX ? -1 : best[v]) << " \n"[v == n];
}
0 3 3 2 0
7 0 -1 -1
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    int n = 200000, k = 100000;              // worst case, built here
    mt19937 rng(46);
    vector<vector<pair<int, int>>> adj(n + 1);
    auto road = [&](int a, int b) {
        int w = rng() % 1000 + 1;
        adj[a].push_back({b, w});
        adj[b].push_back({a, w});
    };
    for (int v = 2; v <= n; v++) road(v, rng() % (v - 1) + 1);
    for (int i = 0; i < n; i++) road(rng() % n + 1, rng() % n + 1);
    vector<int> hosp(k);
    for (int &h : hosp) h = rng() % n + 1;
    vector<ll> best(n + 1, LLONG_MAX);
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;
    for (int h : hosp) {                         // every hospital starts at 0
        best[h] = 0;
        pq.push({0, h});
    }
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (d > best[u]) continue;
        for (auto [v, w] : adj[u])
            if (d + w < best[v]) { best[v] = d + w; pq.push({best[v], v}); }
    }
    ll total = 0;
    for (int v = 1; v <= n; v++) total += best[v];
    cout << "sum of distances: " << total << "\n";
}
sum of distances: 44875592

Problem D3 · One Coupon

(Written for this course, in the style of a Codeforces Div. 2 C/D problem.)

Bus Routes again (from town 1 to town n), but you hold one coupon: on any single road you may pay ⌊w / 2⌋ instead of w. Print the minimum total length, or −1.

Input Output
4 4 / 1 2 10 / 2 4 10 / 1 3 2 / 3 4 24 14 (2 + ⌊24/2⌋)
2 1 / 1 2 9 4
4 2 / 1 2 5 / 3 4 5 -1

The obvious attempt: halve the biggest road of the shortest path (WA)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, int>>> adj(n + 1);   // (neighbour, length)
    for (int i = 0; i < m; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        adj[a].push_back({b, w});
        adj[b].push_back({a, w});
    }
    vector<ll> dist(n + 1, LLONG_MAX);
    vector<int> par(n + 1, 0), parW(n + 1, 0);
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;
    dist[1] = 0;
    pq.push({0, 1});
    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; par[v] = u; parW[v] = w; pq.push({dist[v], v}); }
    }
    int big = 0;                                  // biggest road on the shortest path
    for (int v = n; v != 1; v = par[v]) big = max(big, parW[v]);
    cout << dist[n] - big + big / 2 << "\n";     // halve it
}
15

The shortest path without a coupon is the top one (10 + 10 = 20); halving a 10 gives 15. But the bottom path, 26 at full price, has one huge road: 2 + 12 = 14. The coupon changes which path is best, so we cannot choose the path first and the coupon afterwards.

The state graph: (town, coupon used?)

Make the coupon part of the node. A node is a pair (u, c): town u, and c = 0 if the coupon is still in your pocket, 1 if it is used. From (u, 0), a road u–v of length w gives two edges: to (v, 0) with length w (pay full fare) and to (v, 1) with length ⌊w/2⌋ (use the coupon). From (u, 1) only full fares, to (v, 1). The answer is min(dist[n][0], dist[n][1]). This new graph has 2n nodes and at most 6m directed edges, all non-negative, so it is plain Dijkstra: O((n + m) log m).

The general recipe: if the best move depends on something besides the position (coupons left, fuel in the tank, the direction you face, the time modulo k, which keys you hold), put that "something" into the node. The node becomes (position, state), and the graph is the state graph (also called a layered graph or product graph).

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, int>>> adj(n + 1);   // (neighbour, length)
    for (int i = 0; i < m; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        adj[a].push_back({b, w});
        adj[b].push_back({a, w});
    }
    const ll INF = LLONG_MAX;
    vector<array<ll, 2>> dist(n + 1, {INF, INF});   // dist[town][coupon used?]
    priority_queue<tuple<ll, int, int>, vector<tuple<ll, int, int>>, greater<>> pq;
    dist[1][0] = 0;
    pq.push({0, 1, 0});
    while (!pq.empty()) {
        auto [d, u, c] = pq.top();
        pq.pop();
        if (d > dist[u][c]) continue;
        for (auto [v, w] : adj[u]) {
            if (d + w < dist[v][c]) {                 // pay the full fare
                dist[v][c] = d + w;
                pq.push({dist[v][c], v, c});
            }
            if (c == 0 && d + w / 2 < dist[v][1]) {   // use the coupon here
                dist[v][1] = d + w / 2;
                pq.push({dist[v][1], v, 1});
            }
        }
    }
    ll ans = min(dist[n][0], dist[n][1]);
    cout << (ans == INF ? -1 : ans) << "\n";
}
14
4
-1

Stress test against "try every road"

The brute force tries the coupon on each road in turn (and no coupon at all), runs a plain Dijkstra each time, and keeps the best: O(m · (n + m) log m), fine for tiny graphs. 500 random graphs with up to 7 towns and 10 roads (loops and repeated roads included):

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

using Graph = vector<vector<pair<int, int>>>;
ll plain(Graph &adj, int n) {                 // no coupon
    vector<ll> d(n + 1, LLONG_MAX);
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;
    d[1] = 0;
    pq.push({0, 1});
    while (!pq.empty()) {
        auto [x, u] = pq.top();
        pq.pop();
        if (x > d[u]) continue;
        for (auto [v, w] : adj[u])
            if (x + w < d[v]) { d[v] = x + w; pq.push({d[v], v}); }
    }
    return d[n];
}
ll states(Graph &adj, int n) {
    vector<array<ll, 2>> d(n + 1, {LLONG_MAX, LLONG_MAX});
    priority_queue<tuple<ll, int, int>, vector<tuple<ll, int, int>>, greater<>> pq;
    d[1][0] = 0;
    pq.push({0, 1, 0});
    while (!pq.empty()) {
        auto [x, u, c] = pq.top();
        pq.pop();
        if (x > d[u][c]) continue;
        for (auto [v, w] : adj[u]) {
            if (x + w < d[v][c]) { d[v][c] = x + w; pq.push({d[v][c], v, c}); }
            if (c == 0 && x + w / 2 < d[v][1]) { d[v][1] = x + w / 2; pq.push({d[v][1], v, 1}); }
        }
    }
    return min(d[n][0], d[n][1]);
}
int main() {
    mt19937 rng(46);
    for (int t = 1; t <= 500; t++) {
        int n = rng() % 6 + 2, m = rng() % 10 + 1;
        vector<array<int, 3>> e(m);
        for (auto &[a, b, w] : e) a = rng() % n + 1, b = rng() % n + 1, w = rng() % 20 + 1;
        auto build = [&](int half) {               // half = which road gets the coupon
            Graph adj(n + 1);
            for (int i = 0; i < m; i++) {
                auto [a, b, w] = e[i];
                if (i == half) w /= 2;
                adj[a].push_back({b, w});
                adj[b].push_back({a, w});
            }
            return adj;
        };
        Graph g = build(-1);
        ll brute = plain(g, n);
        for (int i = 0; i < m; i++) { Graph h = build(i); brute = min(brute, plain(h, n)); }
        if (brute != states(g, n)) { cout << "mismatch on test " << t; return 0; }
    }
    cout << "all 500 tests passed";
}
all 500 tests passed

Complexity vs the constraints

n, m ≤ 2 · 10^5.

Method Time n = m = 2 · 10^5
BFS on lengths O(n + m) wrong answer
Dijkstra (binary heap, lazy deletion) O((n + m) log m) ≈ 7 · 10^6 accepted
Dijkstra per source, k sources O(k (n + m) log m) ≈ 10^11 TLE
multi-source Dijkstra O((n + m) log m) accepted, 0.15 s for k = 10^5
greedy coupon after the path O((n + m) log m) wrong answer
state graph, 1 coupon (2 layers) O((n + m) log m), about 2× accepted
state graph, k coupons (k + 1 layers) O(k (n + m) log(k m)) fine for small k

Memory: O(n + m) for the graph, O(n · layers) for dist.

Common mistakes (and the real outputs)

Mistake What you see Why Fix
BFS when roads have lengths 10 (expected 3) fewest roads ≠ shortest Dijkstra
int distances -294967296 (expected 2000000000) 2 · 10^9 overflows int long long, LLONG_MAX
no stale check if (d > dist[u]) continue; still correct, but can be far slower old entries relax all their edges again skip stale entries
default priority_queue (max-heap) can be exponentially slow largest distance comes out first greater<>
one Dijkstra per source Time Limit Exceeded k × whole graph all sources at 0 in one queue
deciding the path, then the coupon 15 (expected 14) the coupon changes the best path state (town, coupon used?)
Dijkstra with negative roads Wrong Answer a final town could still improve Bellman–Ford / SPFA
INF + w when dist is LLONG_MAX overflow adding to infinity only relax from towns that were reached (taken out of the queue)

Mini project

Write a generic state-graph Dijkstra: a function dijkstra(numStates, start, edges) where edges(s) returns a list of (next state, length) for state s, with states encoded as integers (e.g. town * (k + 1) + couponsUsed). Use it to solve D1 (1 layer), D3 (2 layers), homework 1 (k + 1 layers) and homework 4 (fuel levels), without changing the Dijkstra code. Add a brute-force checker for each and a stress test.

Practice

These are the four homework problems from the episode. Every answer below came from a compiled C++ program (g++ -O2 -std=c++17).

1. k coupons. One Coupon, but you may use up to k coupons (each on a different road, each halves that road).

Solution

k + 1 layers: dist[town][coupons used], 0 ≤ used ≤ k. From layer c a road goes to layer c at full price, or to layer c + 1 at half price if c < k. O(k (n + m) log(k m)).

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    int n, m, k;
    cin >> n >> m >> k;                         // k = number of coupons
    vector<vector<pair<int, int>>> adj(n + 1);
    for (int i = 0; i < m; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        adj[a].push_back({b, w});
        adj[b].push_back({a, w});
    }
    const ll INF = LLONG_MAX;
    vector<vector<ll>> dist(n + 1, vector<ll>(k + 1, INF));   // dist[town][coupons used]
    priority_queue<tuple<ll, int, int>, vector<tuple<ll, int, int>>, greater<>> pq;
    dist[1][0] = 0;
    pq.push({0, 1, 0});
    while (!pq.empty()) {
        auto [d, u, c] = pq.top();
        pq.pop();
        if (d > dist[u][c]) continue;
        for (auto [v, w] : adj[u]) {
            if (d + w < dist[v][c]) { dist[v][c] = d + w; pq.push({dist[v][c], v, c}); }
            if (c < k && d + w / 2 < dist[v][c + 1]) { dist[v][c + 1] = d + w / 2; pq.push({dist[v][c + 1], v, c + 1}); }
        }
    }
    ll ans = *min_element(dist[n].begin(), dist[n].end());
    cout << (ans == INF ? -1 : ans) << "\n";
}

Input format n m k then the roads. The episode's sample with k = 2 (halve both top roads: 5 + 5 = 10), and one road with k = 0:

10
9

2. Count the shortest paths. Print the shortest distance from 1 to n and the number of different shortest paths modulo 10^9 + 7.

Solution

Keep ways[v] next to dist[v]. When a strictly shorter path to v is found, ways[v] = ways[u]; when an equally short one is found, ways[v] += ways[u]. This is correct because a town is taken out of the queue (final) only after every town that is strictly closer, so ways[u] is complete when u relaxes its roads (all lengths are ≥ 1).

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    const ll MOD = 1000000007;
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, int>>> adj(n + 1);
    for (int i = 0; i < m; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        adj[a].push_back({b, w});
        adj[b].push_back({a, w});
    }
    vector<ll> dist(n + 1, LLONG_MAX), ways(n + 1, 0);
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;
    dist[1] = 0;
    ways[1] = 1;
    pq.push({0, 1});
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (d > dist[u]) continue;              // u is final: ways[u] is complete
        for (auto [v, w] : adj[u]) {
            if (d + w < dist[v]) {              // a strictly better path: start counting again
                dist[v] = d + w;
                ways[v] = ways[u];
                pq.push({dist[v], v});
            } else if (d + w == dist[v]) {      // another shortest path
                ways[v] = (ways[v] + ways[u]) % MOD;
            }
        }
    }
    if (dist[n] == LLONG_MAX) cout << "-1 0\n";
    else cout << dist[n] << " " << ways[n] << "\n";
}

A square 1–2–4, 1–3–4 with all lengths 1 (two shortest paths), and the episode's Bus Routes sample:

2 2
3 1

3. The farthest town. Nearest Hospital, but print the reachable town whose nearest hospital is farthest away (smallest number on ties), and that distance.

Solution

Multi-source Dijkstra, then one pass for the maximum over reachable towns.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<int> hosp(k);
    for (int &h : hosp) cin >> h;
    vector<vector<pair<int, int>>> adj(n + 1);
    for (int i = 0; i < m; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        adj[a].push_back({b, w});
        adj[b].push_back({a, w});
    }
    vector<ll> best(n + 1, LLONG_MAX);
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;
    for (int h : hosp) { best[h] = 0; pq.push({0, h}); }
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (d > best[u]) continue;
        for (auto [v, w] : adj[u])
            if (d + w < best[v]) { best[v] = d + w; pq.push({best[v], v}); }
    }
    int far = -1;                               // reachable town with the largest distance
    for (int v = 1; v <= n; v++)
        if (best[v] != LLONG_MAX && (far == -1 || best[v] > best[far])) far = v;
    cout << far << " " << best[far] << "\n";
}

The two Nearest Hospital samples:

2 3
1 7

4. Fuel. Your tank holds cap litres (cap ≤ 100) and a road of length w uses w litres. Some towns have a free pump that fills the tank. Start full at town 1; print the shortest distance to town n, or −1.

Solution

State (town, fuel left): n · (cap + 1) states. A road u–v of length w ≤ fuel goes to (v, fuel − w) with length w; at a pump, (u, f) → (u, cap) with length 0. Dijkstra on this state graph.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    int n, m, cap;
    cin >> n >> m >> cap;                       // tank holds cap litres; 1 litre per km
    vector<int> pump(n + 1);
    for (int i = 1; i <= n; i++) cin >> pump[i];   // 1 = free refill to a full tank here
    vector<vector<pair<int, int>>> adj(n + 1);
    for (int i = 0; i < m; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        adj[a].push_back({b, w});
        adj[b].push_back({a, w});
    }
    const ll INF = LLONG_MAX;
    vector<vector<ll>> dist(n + 1, vector<ll>(cap + 1, INF));   // dist[town][fuel left]
    priority_queue<tuple<ll, int, int>, vector<tuple<ll, int, int>>, greater<>> pq;
    dist[1][cap] = 0;                           // start with a full tank
    pq.push({0, 1, cap});
    while (!pq.empty()) {
        auto [d, u, f] = pq.top();
        pq.pop();
        if (d > dist[u][f]) continue;
        if (pump[u] && f < cap && d < dist[u][cap]) {   // refill: same distance, full tank
            dist[u][cap] = d;
            pq.push({d, u, cap});
        }
        for (auto [v, w] : adj[u])
            if (w <= f && d + w < dist[v][f - w]) {
                dist[v][f - w] = d + w;
                pq.push({dist[v][f - w], v, f - w});
            }
    }
    ll ans = *min_element(dist[n].begin(), dist[n].end());
    cout << (ans == INF ? -1 : ans) << "\n";
}

Input n m cap, then n pump flags, then the roads. In the first test the short-looking route 1–2–4 needs 8 litres without a pump, so the answer goes through the pump at town 3 (3 + 2 = 5); in the second no route works:

5
-1

Quick quiz

You may now use up to 3 coupons. How many states does each town need?

dist[town][coupons used]

A) 1 · B) 3 · C) 4 · D) 8

Answer

C. "Coupons used" can be 0, 1, 2 or 3: four layers, so 4n states. In general k coupons need k + 1 layers.

Interview questions

  1. Why does Dijkstra need non-negative weights? It declares the smallest waiting node final. With a negative edge, a path through a node that is farther now could still become shorter later, so "final" would be wrong.
  2. What is lazy deletion in Dijkstra? Instead of decreasing a key in the heap, push a new (distance, node) pair and, when popping, skip pairs whose distance is larger than the best known (stale entries).
  3. What is the complexity of Dijkstra with a binary heap? O((V + E) log V) (or log E with lazy deletion, which is the same up to a constant since E ≤ V²).
  4. How do you find the distance to the nearest of many sources? Multi-source Dijkstra/BFS: push all sources at distance 0 before the loop; equivalent to adding a super source with 0-length edges.
  5. What is a state graph? A graph whose nodes are (position, extra information), so that a shortest-path algorithm can handle rules that depend on more than the position: coupons, fuel, keys, direction, time.
  6. Dijkstra vs BFS vs 0-1 BFS? All weights equal: BFS, O(V + E). Weights 0/1: 0-1 BFS with a deque, O(V + E). Non-negative weights: Dijkstra, O((V + E) log V). Negative weights: Bellman–Ford, O(VE).

Glossary

Term Meaning Example
Weighted graph A graph whose edges have lengths (weights, costs) roads of length 1, 1, 1 and 10
Shortest path A path with the least total length 1 → 2 → 3 → 4 = 3
Dijkstra's algorithm Shortest paths with non-negative weights: repeatedly finalise the closest waiting node Bus Routes
Priority queue A container that always gives the smallest (here) item first priority_queue<pair<ll, int>, vector<...>, greater<>>
Min-heap / max-heap Priority queue giving the smallest / largest first; C++'s default is max greater<> makes it a min-heap
Relaxation Improving dist[v] through u if dist[u] + w < dist[v] if (d + w < dist[v])
Stale entry An old, larger offer still in the queue (10, 4) after dist[4] became 3
Lazy deletion Leaving stale entries in the heap and skipping them when popped if (d > dist[u]) continue;
Final (settled) node A node whose distance can no longer improve a town taken out of the queue
Non-negative weights All lengths ≥ 0: the condition Dijkstra needs road lengths ≥ 1
Bellman–Ford Shortest paths that allow negative weights, O(VE) not needed today
long long 64-bit integer, up to about 9.2 · 10^18 sums of lengths up to 2 · 10^14
Integer overflow A result too big for the type; for signed types undefined, in practice wraps -294967296
INT_MAX, LLONG_MAX The largest int (2,147,483,647) and long long used as "infinity"
Multi-source shortest path Distances from the nearest of several sources Nearest Hospital
Super source (virtual node) An imaginary node joined to all sources with 0-length edges all hospitals start at 0
State The extra information a node must carry coupon used? fuel left?
State graph (layered graph) A graph whose nodes are (position, state) 2n nodes for one coupon
Layer All states with the same extra value layer 1 = coupon already used
⌊x⌋ (floor) Round down to an integer ⌊9 / 2⌋ = 4
Greedy Making the locally best choice now "halve the biggest road" (wrong here)
Stress test Comparing a fast solution with a slow, surely-correct one on random inputs all 500 tests passed
Brute force A simple, slow method that tries every possibility try the coupon on every road
Time Limit Exceeded (TLE) The program ran too long one Dijkstra per hospital
Wrong Answer (WA) The output differs from the correct one 15 instead of 14
tuple, array Fixed-size groups of values used as heap entries or table rows tuple<ll, int, int> = (dist, town, coupon)
mt19937 C++'s Mersenne Twister random generator mt19937 rng(46);

Summary

  • With lengths, BFS is wrong (10 instead of 3): use Dijkstra: min priority queue (greater<>), relax, skip stale entries; 3, -1, 2000000000.
  • Distances in long long: with int, two roads of 10^9 print -294967296.
  • Lengths must be non-negative.
  • Many sources: one Dijkstra each is TLE; all sources at 0 in one queue (a super source) is one run: 0 3 3 2 0, 7 0 -1 -1.
  • Extra choices (coupons, fuel, direction): a greedy afterthought gives 15 instead of 14; put the choice into the node, (town, state), and run plain Dijkstra on the state graph: 14, 4, -1; all 500 tests passed.

Solutions in C++, Java and Python

Problem D1 · Bus Routes

C++

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, int>>> adj(n + 1);   // (neighbour, length)
    for (int i = 0; i < m; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        adj[a].push_back({b, w});
        adj[b].push_back({a, w});
    }
    const ll INF = LLONG_MAX;
    vector<ll> dist(n + 1, INF);
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;   // smallest first
    dist[1] = 0;
    pq.push({0, 1});
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (d > dist[u]) continue;                // stale entry: skip
        for (auto [v, w] : adj[u])
            if (d + w < dist[v]) {
                dist[v] = d + w;
                pq.push({dist[v], v});
            }
    }
    cout << (dist[n] == INF ? -1 : dist[n]) << "\n";
}

Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        st.nextToken(); int n = (int) st.nval;
        st.nextToken(); int m = (int) st.nval;
        List<List<int[]>> adj = new ArrayList<>();
        for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());
        for (int i = 0; i < m; i++) {
            st.nextToken(); int a = (int) st.nval;
            st.nextToken(); int b = (int) st.nval;
            st.nextToken(); int w = (int) st.nval;
            adj.get(a).add(new int[]{b, w});
            adj.get(b).add(new int[]{a, w});
        }
        long[] dist = new long[n + 1];
        Arrays.fill(dist, Long.MAX_VALUE);
        PriorityQueue<long[]> pq = new PriorityQueue<>((x, y) -> Long.compare(x[0], y[0]));
        dist[1] = 0;
        pq.add(new long[]{0, 1});
        while (!pq.isEmpty()) {
            long[] top = pq.poll();
            long d = top[0];
            int u = (int) top[1];
            if (d > dist[u]) continue;
            for (int[] e : adj.get(u))
                if (d + e[1] < dist[e[0]]) {
                    dist[e[0]] = d + e[1];
                    pq.add(new long[]{dist[e[0]], e[0]});
                }
        }
        System.out.println(dist[n] == Long.MAX_VALUE ? -1 : dist[n]);
    }
}
3
-1
2000000000

Python

import sys, heapq

def main():
    data = sys.stdin.buffer.read().split()
    n, m = int(data[0]), int(data[1])
    adj = [[] for _ in range(n + 1)]
    for i in range(m):
        a, b, w = int(data[2 + 3 * i]), int(data[3 + 3 * i]), int(data[4 + 3 * i])
        adj[a].append((b, w))
        adj[b].append((a, w))
    INF = float('inf')
    dist = [INF] * (n + 1)
    dist[1] = 0
    pq = [(0, 1)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue                        # stale entry
        for v, w in adj[u]:
            if d + w < dist[v]:
                dist[v] = d + w
                heapq.heappush(pq, (dist[v], v))
    print(-1 if dist[n] == INF else dist[n])

main()
3
-1
2000000000

Problem D2 · Nearest Hospital

C++

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, k;
    cin >> n >> m >> k;
    vector<int> hosp(k);
    for (int &h : hosp) cin >> h;
    vector<vector<pair<int, int>>> adj(n + 1);
    for (int i = 0; i < m; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        adj[a].push_back({b, w});
        adj[b].push_back({a, w});
    }
    vector<ll> best(n + 1, LLONG_MAX);
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;
    for (int h : hosp) {                         // every hospital starts at 0
        best[h] = 0;
        pq.push({0, h});
    }
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (d > best[u]) continue;
        for (auto [v, w] : adj[u])
            if (d + w < best[v]) { best[v] = d + w; pq.push({best[v], v}); }
    }
    for (int v = 1; v <= n; v++)
        cout << (best[v] == LLONG_MAX ? -1 : best[v]) << " \n"[v == n];
}

Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        st.nextToken(); int n = (int) st.nval;
        st.nextToken(); int m = (int) st.nval;
        st.nextToken(); int k = (int) st.nval;
        int[] hosp = new int[k];
        for (int i = 0; i < k; i++) { st.nextToken(); hosp[i] = (int) st.nval; }
        List<List<int[]>> adj = new ArrayList<>();
        for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());
        for (int i = 0; i < m; i++) {
            st.nextToken(); int a = (int) st.nval;
            st.nextToken(); int b = (int) st.nval;
            st.nextToken(); int w = (int) st.nval;
            adj.get(a).add(new int[]{b, w});
            adj.get(b).add(new int[]{a, w});
        }
        long[] best = new long[n + 1];
        Arrays.fill(best, Long.MAX_VALUE);
        PriorityQueue<long[]> pq = new PriorityQueue<>((x, y) -> Long.compare(x[0], y[0]));
        for (int h : hosp) { best[h] = 0; pq.add(new long[]{0, h}); }   // every hospital starts at 0
        while (!pq.isEmpty()) {
            long[] top = pq.poll();
            long d = top[0];
            int u = (int) top[1];
            if (d > best[u]) continue;
            for (int[] e : adj.get(u))
                if (d + e[1] < best[e[0]]) {
                    best[e[0]] = d + e[1];
                    pq.add(new long[]{best[e[0]], e[0]});
                }
        }
        StringBuilder sb = new StringBuilder();
        for (int v = 1; v <= n; v++) sb.append(best[v] == Long.MAX_VALUE ? -1 : best[v]).append(v == n ? "\n" : " ");
        System.out.print(sb);
    }
}
0 3 3 2 0
7 0 -1 -1

Python

import sys, heapq

def main():
    data = sys.stdin.buffer.read().split()
    n, m, k = int(data[0]), int(data[1]), int(data[2])
    hosp = [int(x) for x in data[3:3 + k]]
    pos = 3 + k
    adj = [[] for _ in range(n + 1)]
    for i in range(m):
        a, b, w = int(data[pos]), int(data[pos + 1]), int(data[pos + 2])
        pos += 3
        adj[a].append((b, w))
        adj[b].append((a, w))
    INF = float('inf')
    best = [INF] * (n + 1)
    pq = []
    for h in hosp:                          # every hospital starts at 0
        best[h] = 0
        pq.append((0, h))
    heapq.heapify(pq)
    while pq:
        d, u = heapq.heappop(pq)
        if d > best[u]:
            continue
        for v, w in adj[u]:
            if d + w < best[v]:
                best[v] = d + w
                heapq.heappush(pq, (best[v], v))
    print(' '.join(str(-1 if best[v] == INF else best[v]) for v in range(1, n + 1)))

main()
0 3 3 2 0
7 0 -1 -1

Problem D3 · One Coupon

C++

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, int>>> adj(n + 1);   // (neighbour, length)
    for (int i = 0; i < m; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        adj[a].push_back({b, w});
        adj[b].push_back({a, w});
    }
    const ll INF = LLONG_MAX;
    vector<array<ll, 2>> dist(n + 1, {INF, INF});   // dist[town][coupon used?]
    priority_queue<tuple<ll, int, int>, vector<tuple<ll, int, int>>, greater<>> pq;
    dist[1][0] = 0;
    pq.push({0, 1, 0});
    while (!pq.empty()) {
        auto [d, u, c] = pq.top();
        pq.pop();
        if (d > dist[u][c]) continue;
        for (auto [v, w] : adj[u]) {
            if (d + w < dist[v][c]) {                 // pay the full fare
                dist[v][c] = d + w;
                pq.push({dist[v][c], v, c});
            }
            if (c == 0 && d + w / 2 < dist[v][1]) {   // use the coupon here
                dist[v][1] = d + w / 2;
                pq.push({dist[v][1], v, 1});
            }
        }
    }
    ll ans = min(dist[n][0], dist[n][1]);
    cout << (ans == INF ? -1 : ans) << "\n";
}

Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        st.nextToken(); int n = (int) st.nval;
        st.nextToken(); int m = (int) st.nval;
        List<List<int[]>> adj = new ArrayList<>();
        for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());
        for (int i = 0; i < m; i++) {
            st.nextToken(); int a = (int) st.nval;
            st.nextToken(); int b = (int) st.nval;
            st.nextToken(); int w = (int) st.nval;
            adj.get(a).add(new int[]{b, w});
            adj.get(b).add(new int[]{a, w});
        }
        long INF = Long.MAX_VALUE;
        long[][] dist = new long[n + 1][2];         // dist[town][coupon used?]
        for (long[] row : dist) Arrays.fill(row, INF);
        PriorityQueue<long[]> pq = new PriorityQueue<>((x, y) -> Long.compare(x[0], y[0]));
        dist[1][0] = 0;
        pq.add(new long[]{0, 1, 0});
        while (!pq.isEmpty()) {
            long[] top = pq.poll();
            long d = top[0];
            int u = (int) top[1], c = (int) top[2];
            if (d > dist[u][c]) continue;
            for (int[] e : adj.get(u)) {
                int v = e[0], w = e[1];
                if (d + w < dist[v][c]) { dist[v][c] = d + w; pq.add(new long[]{dist[v][c], v, c}); }
                if (c == 0 && d + w / 2 < dist[v][1]) { dist[v][1] = d + w / 2; pq.add(new long[]{dist[v][1], v, 1}); }
            }
        }
        long ans = Math.min(dist[n][0], dist[n][1]);
        System.out.println(ans == INF ? -1 : ans);
    }
}
14
4
-1

Python

import sys, heapq

def main():
    data = sys.stdin.buffer.read().split()
    n, m = int(data[0]), int(data[1])
    adj = [[] for _ in range(n + 1)]
    for i in range(m):
        a, b, w = int(data[2 + 3 * i]), int(data[3 + 3 * i]), int(data[4 + 3 * i])
        adj[a].append((b, w))
        adj[b].append((a, w))
    INF = float('inf')
    dist = [[INF, INF] for _ in range(n + 1)]     # dist[town][coupon used?]
    dist[1][0] = 0
    pq = [(0, 1, 0)]
    while pq:
        d, u, c = heapq.heappop(pq)
        if d > dist[u][c]:
            continue
        for v, w in adj[u]:
            if d + w < dist[v][c]:
                dist[v][c] = d + w
                heapq.heappush(pq, (dist[v][c], v, c))
            if c == 0 and d + w // 2 < dist[v][1]:
                dist[v][1] = d + w // 2
                heapq.heappush(pq, (dist[v][1], v, 1))
    ans = min(dist[n])
    print(-1 if ans == INF else ans)

main()
14
4
-1