Resource Expansion Principle

Dijkstra lied to you. Not maliciously --- it just let you believe that a node is a node. That dist[5] = 7 means you're done with node 5. But what if you're at node 5 with 3 coins? And also at node 5 with 0 coins? Those are not the same situation, and collapsing them into one dist[5] throws away information you need.

The fix is the single most powerful idea in competitive shortest-path problems: expand your state.

---

When dist[node] Isn't Enough

Standard Dijkstra tracks one number per node: the shortest distance from the source. This works when knowing "I'm at node \(u\)" tells you everything about your situation.

But many problems hand you an extra resource --- coins, keys, fuel, budget, a one-time coupon. Suddenly "I'm at node \(u\)" is incomplete. You also need to know how much resource you have left.

Consider a maze with 3 keys scattered across the grid. Being at cell \((2, 3)\) with key A is fundamentally different from being at \((2, 3)\) with no keys. Key A might open a door that halves your remaining path. Without it, you're stuck taking a detour.

Key insight. If two arrivals at the same node lead to different future costs, they are different states. Your distance table must distinguish them.

---

The Expanded Graph

The idea is mechanical. Replace your 1D distance table with a 2D one:

\[\text{dist}[\text{node}][\text{resource}]\]

Each (node, resource) pair becomes a vertex in an expanded graph. Edges in this expanded graph connect valid transitions:

• From (u, r) to (v, r') with cost \(w\), where \(r'\) is determined by the problem's resource logic.

Think of it as building a multi-story building on top of your original graph. Each "floor" corresponds to a resource value. Edges within a floor are normal graph edges. Edges between floors represent resource consumption or gain.

Floor r=2:   A --- B --- C
             |           |
Floor r=1:   A --- B --- C
             |           |
Floor r=0:   A --- B --- C

Vertical edges (between floors) appear when traversing an edge changes your resource. Horizontal edges (within a floor) appear when the resource stays the same.

---

When to Expand vs When to Preprocess

Not every problem with a "resource" needs state expansion. The key question:

Does the resource change per edge? If yes, expand. If the resource is fixed before you start, preprocess.

Situation	Approach
"You have K coins. Each edge costs some coins."	Expand: dist[node][coins_left]
"You can remove at most K obstacles."	Expand: dist[node][removals_left]
"All edges with weight < 5 are free."	Preprocess: modify edge weights, run standard Dijkstra
"You start with fuel F, refuel at certain nodes."	Expand: dist[node][fuel]

Gotcha. If the resource doesn't change during traversal (e.g., "find shortest path in graph where you've already chosen which edges to keep"), you're not doing state expansion. You're doing a different problem.

---

The Complexity Tax

State expansion doesn't come free. If your original graph has \(|V|\) vertices and \(|E|\) edges, and your resource ranges over \(|R|\) values:

• Vertices in expanded graph: \(|V| \times |R|\)
• Edges in expanded graph: \(|E| \times |R|\) (roughly)
• Dijkstra complexity: \(O(|V| \cdot |R| \cdot \log(|V| \cdot |R|))\)

This is tractable when \(|R|\) is small. A boolean resource (\(|R| = 2\)) barely doubles the work. A fuel tank from 0 to 50 multiplies by 51. A resource from 0 to \(10^6\) makes state expansion infeasible.

Gotcha. The resource must be bounded for state expansion to work. If the resource can grow without limit (e.g., accumulating coins with no cap), you need to find a cap yourself --- or use a different technique entirely.

---

Finding the Bound

Often the problem doesn't hand you the bound explicitly. You need to derive it.

If edges cost at most \(C\) silver coins and the graph has at most \(N\) nodes, then you never need more than \(C \times N\) silver coins. Any path uses at most \(N - 1\) edges, each costing at most \(C\). So cap your resource at \(C \times N\) and ignore any surplus.

This observation is critical for problems like AtCoder abc164_e, where the silver coin count is technically unbounded but the useful range is small.

---

The Template

Every state-expanded Dijkstra follows the same skeleton:

// dist[node][resource] = minimum cost
vector<vector<long long>> dist(n, vector<long long>(maxR + 1, LLONG_MAX));

// pq: (cost, node, resource)
priority_queue<tuple<long long,int,int>,
               vector<tuple<long long,int,int>>,
               greater<>> pq;

dist[src][initR] = 0;
pq.push({0, src, initR});

while (!pq.empty()) {
    auto [d, u, r] = pq.top(); pq.pop();
    if (d > dist[u][r]) continue; // stale entry

    for (auto& [v, w] : adj[u]) {
        int nr = /* compute new resource */;
        if (nr < 0 || nr > maxR) continue;
        long long nd = d + w;
        if (nd < dist[v][nr]) {
            dist[v][nr] = nd;
            pq.push({nd, v, nr});
        }
    }
}

The only thing that changes between problems is the nr = ... line. Everything else is boilerplate.

---

Reading the Answer

The answer at the destination is usually the minimum over all resource values:

\[\text{answer} = \min_{r=0}^{R} \text{dist}[\text{dest}][r]\]

Sometimes the problem constrains the final resource value (e.g., "you must have at least 1 key remaining"), in which case you only take the min over valid \(r\) values.

---

Trace: Shortest Path with 1 Free Edge Removal

Graph: 3 nodes, edges 0-1 (cost 5), 1-2 (cost 3), 0-2 (cost 10). Resource: can remove at most 1 edge (make it free). Source: 0, destination: 2.

State: (node, removals_left). Resource range: 0 to 1.

Step	Pop	dist	Push
1	(0, 0, 1)	dist[0][1]=0	(5, 1, 1), (10, 2, 1), (0, 1, 0), (0, 2, 0)
2	(0, 1, 0)	dist[1][0]=0	(3, 2, 0)
3	(0, 2, 0)	dist[2][0]=0	done!
4	(3, 2, 0)	dist[2][0]=0 already	skip
5	(5, 1, 1)	dist[1][1]=5	(8, 2, 1), (5, 2, 0) skip
6	(8, 2, 1)	dist[2][1]=8	---
7	(10, 2, 1)	dist[2][1]=8 already	skip

Answer: \(\min(\text{dist}[2][0], \text{dist}[2][1]) = \min(0, 8) = 0\).

We removed edge 0-2 (cost 10) for free, arriving at cost 0.

Key insight. The expanded graph is just a regular graph with more nodes. Dijkstra doesn't care that those nodes encode (city, resource) pairs. It only sees vertices and edges. The "expansion" is conceptual --- the algorithm is identical.

---

Exercises

1. State design. You have a grid with walls. You can break at most 2 walls. What is your state? What is the resource range?

2. Bound derivation. A graph has 100 nodes. Each edge costs between 1 and 10 coins. What's the maximum useful coin budget? Why?

3. Answer extraction. A problem says "reach node \(N\) with at least 3 fuel remaining." How do you read the answer from dist[N][r]?

---

Problems

Problem	Link	Difficulty
CSES — Flight Discount	cses.fi/problemset/task/1195	Medium
LC 1293 — Shortest Path in a Grid with Obstacles Elimination	leetcode.com/problems/shortest-path-in-a-grid-with-obstacles-elimination	Hard
LC 787 — Cheapest Flights Within K Stops	leetcode.com/problems/cheapest-flights-within-k-stops	Medium