Skip to content

Bounded Integer Resource

Binary was easy. Two layers, done. But what happens when your resource isn't a coin flip --- it's a wallet? A fuel tank with 50 liters? A health bar draining hit by hit? Now your state space multiplies by the size of that resource, and the critical question shifts from "how do I model it?" to "how do I bound it?"

The Problem: AtCoder abc164_e (Two Currencies)

Pruning impossible states where resource drops below zero

K-layer graph: each layer represents one unit of resource consumed

\(N\) cities, \(M\) railways. Each railway from \(u\) to \(v\) costs \(c_{uv}\) silver coins and \(t_{uv}\) minutes of travel time. At each city \(i\), you can exchange \(e_i\) gold coins for \(f_i\) silver coins, taking \(g_i\) minutes.

You start at city 1 with \(S\) silver coins and unlimited gold. Find the minimum time to reach every other city.

The State

\[\text{dist}[\text{city}][\text{silver}] = \text{minimum time to reach city with exactly silver coins}\]

Silver coins are the resource dimension. But silver is technically unbounded --- you can keep exchanging gold for silver forever. So how big is the table?

Deriving the Bound

Each railway costs at most \(\max(c_{uv})\) silver. A shortest path visits at most \(N - 1\) edges. So you never need more than:

\[\text{MAXR} = \max(c_{uv}) \times (N - 1)\]

In the problem constraints, \(c_{uv} \le 50\) and \(N \le 50\). So \(\text{MAXR} = 50 \times 49 = 2450\). We cap at 2500 for safety.

Any silver beyond this cap is wasted --- you'll never spend it all. So when an exchange would push you past MAXR, just cap at MAXR.

Key insight. The bound comes from the maximum possible spending along any path. If the maximum edge cost is \(C\) and the path uses at most \(N-1\) edges, then \(C \times (N-1)\) silver suffices. Everything above that is dead weight.

The Transitions

Two types of moves from state (u, s):

1. Traverse railway to city \(v\): - Requires \(s \ge c_{uv}\) (enough silver to pay). - New state: (v, s - c_uv). - Added time: \(t_{uv}\).

2. Exchange at city \(u\): - Spend \(e_u\) gold (unlimited, so no constraint), gain \(f_u\) silver. - New state: (u, min(s + f_u, MAXR)). - Added time: \(g_u\). - Note: you stay at the same city. This is a self-loop in the expanded graph.

Gotcha. The exchange is a self-loop, not an edge to another node. It costs time but doesn't move you. This is perfectly valid in Dijkstra --- any edge with non-negative weight works.

Full Trace

Small example: 3 cities. Railways: 1->2 (cost 3 silver, 2 min), 2->3 (cost 5 silver, 4 min), 1->3 (cost 10 silver, 20 min). Exchange at city 2: pay 1 gold, get 6 silver, takes 3 min. Start with 3 silver.

State: (city, silver). Showing key entries only.

Step Pop (time, city, silver) Key updates
1 (0, 1, 3) dist[2][0]=2 (spend 3 silver on 1->2)
2 (2, 2, 0) dist[2][6]=5 (exchange: gain 6 silver, 3 min)
3 (5, 2, 6) dist[3][1]=9 (spend 5 silver on 2->3, 4 min)
4 (9, 3, 1) destination 3 reached in 9 min

Without exchange: we'd need 10 silver for the direct route (20 min) or can't afford 2->3. With exchange at city 2, we get silver mid-route and reach city 3 in 9 min.

The Code

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

int main() {
    int n, m;
    cin >> n >> m;

    struct Edge { int to, silver, time; };
    vector<vector<Edge>> adj(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v, c, t;
        cin >> u >> v >> c >> t;
        adj[u].push_back({v, c, t});
        adj[v].push_back({u, c, t});
    }

    // Exchange info: gold_cost (ignored, unlimited), silver_gained, time_cost
    vector<int> sg(n + 1), et(n + 1);
    for (int i = 1; i <= n; i++) {
        int e, f, g;
        cin >> e >> f >> g;
        // e = gold cost (don't care), f = silver gained, g = time
        sg[i] = f;
        et[i] = g;
    }

    int S;
    cin >> S;
    const int MAXR = 2500;
    S = min(S, MAXR);

    vector<vector<long long>> dist(n + 1, vector<long long>(MAXR + 1, LLONG_MAX));
    priority_queue<tuple<long long,int,int>,
                   vector<tuple<long long,int,int>>,
                   greater<>> pq;
    dist[1][S] = 0;
    pq.push({0, 1, S});

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

        // Traverse edges
        for (auto& [v, sc, tc] : adj[u]) {
            if (s >= sc) {
                long long nd = d + tc;
                int ns = s - sc;
                if (nd < dist[v][ns]) {
                    dist[v][ns] = nd;
                    pq.push({nd, v, ns});
                }
            }
        }

        // Exchange at city u
        int ns = min(s + sg[u], MAXR);
        long long nd = d + et[u];
        if (nd < dist[u][ns]) {
            dist[u][ns] = nd;
            pq.push({nd, u, ns});
        }
    }

    for (int v = 2; v <= n; v++) {
        long long ans = LLONG_MAX;
        for (int s = 0; s <= MAXR; s++) {
            ans = min(ans, dist[v][s]);
        }
        cout << ans << "\n";
    }

    return 0;
}

Same Pattern: LC 1293 (Obstacles Elimination)

Grid with 0s (empty) and 1s (obstacles). You can eliminate at most \(K\) obstacles. Find shortest path from top-left to bottom-right.

State: (row, col, obstacles_remaining).

This is BFS, not Dijkstra (all edge weights are 1). But the resource expansion is identical.

int shortestPath(vector<vector<int>>& grid, int k) {
    int R = grid.size(), C = grid[0].size();
    vector<vector<vector<int>>> dist(R, vector<vector<int>>(C, vector<int>(k + 1, -1)));
    queue<tuple<int,int,int>> q;
    dist[0][0][k] = 0;
    q.push({0, 0, k});

    int dx[] = {0,0,1,-1}, dy[] = {1,-1,0,0};
    while (!q.empty()) {
        auto [r, c, rem] = q.front(); q.pop();
        if (r == R-1 && c == C-1) return dist[r][c][rem];
        for (int d = 0; d < 4; d++) {
            int nr = r + dx[d], nc = c + dy[d];
            if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
            int nrem = rem - grid[nr][nc];
            if (nrem >= 0 && dist[nr][nc][nrem] == -1) {
                dist[nr][nc][nrem] = dist[r][c][rem] + 1;
                q.push({nr, nc, nrem});
            }
        }
    }
    return -1;
}

Key insight. BFS vs Dijkstra doesn't matter for the state expansion concept. If all edges have weight 1, use BFS. If edges have varying weights, use Dijkstra. The resource dimension works the same either way.

Complexity Comparison

Problem Nodes Resource Range Expanded States Algorithm
Flight Discount \(10^5\) 2 \(2 \times 10^5\) Dijkstra
Two Currencies 50 2500 125,000 Dijkstra
LC 1293 \(40 \times 40\) \(K \le 1600\) \(\sim 2.5 \times 10^6\) BFS

The pattern scales as long as the resource range stays manageable. Once the resource range exceeds \(\sim 10^4\), look for ways to tighten the bound or use a different approach.

Exercises

  1. Bound tightening. In Two Currencies, if all edge silver costs are exactly 1, what's the tighter MAXR? Does it meaningfully reduce runtime?

  2. Multiple resources. What if you had both silver coins AND bronze coins, each spent on different edges? What does the state look like? What happens to complexity?

  3. LC 1293 optimization. When \(K \ge R + C - 3\) (enough to bulldoze a straight-line path), what's the answer immediately without any search?

Problems

Problem Link Difficulty
AtCoder abc164_e — Two Currencies atcoder.jp/contests/abc164/tasks/abc164_e Hard
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