Resource with Refueling

Graph with refueling stations that reset fuel to max capacity

Every resource problem so far had a resource that only drained. Coins spent, coupons used, budget consumed. Now the resource refills. You pull into a city, fill the tank, and suddenly you're back to full. This refueling twist breaks the monotone structure and demands a different approach: build a second graph on top of the first one.

The Problem: AtCoder abc143_e (Travel by Car)

State: (node, fuel remaining), refuel resets fuel at stations

\(N\) cities, \(M\) undirected roads with distances. Your car has a fuel tank of capacity \(L\). Every unit of distance costs one unit of fuel. At any city, you can refuel to full capacity for free.

\(Q\) queries: given source \(s\) and destination \(t\), what is the minimum number of refueling stops?

Constraints: \(N \le 300\), \(M \le N(N-1)/2\), \(Q \le N(N-1)/2\).

Why State Expansion Is Awkward Here

You could model this as dist[city][fuel_remaining] and run Dijkstra. Each edge (u, v, w) transitions from (u, f) to (v, f - w) if \(f \ge w\). At each city, you can also "refuel": (u, f) to (u, L) with cost +1 (one refueling stop).

This works for a single query. But with \(Q\) up to 45,000 queries and \(N \le 300\), running Dijkstra per query is too slow. The all-pairs nature screams Floyd-Warshall. And Floyd doesn't mix well with a fuel dimension.

Key insight. When you need all-pairs answers and the resource can refill, think in two layers. Layer 1 computes the raw distances. Layer 2 builds a new graph from those distances.

Layer 1: All-Pairs Shortest Distances

Run Floyd-Warshall on the original graph. After this, d[i][j] = shortest distance between cities \(i\) and \(j\).

const long long INF = 1e18;
vector<vector<long long>> d(n + 1, vector<long long>(n + 1, INF));
for (int i = 1; i <= n; i++) d[i][i] = 0;

// Read edges and initialize
for (auto& [u, v, w] : edges) {
    d[u][v] = min(d[u][v], (long long)w);
    d[v][u] = min(d[v][u], (long long)w);
}

// Floyd-Warshall
for (int k = 1; k <= n; k++)
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (d[i][k] != INF && d[k][j] != INF)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

Complexity: \(O(N^3)\).

Layer 2: The Refueling Graph

Now build a new graph. Cities are still the nodes. But there's a directed edge from \(i\) to \(j\) if and only if:

\[d[i][j] \le L\]

Meaning: you can drive from \(i\) to \(j\) on a single tank. If this edge exists, the cost is 1 refueling stop (you refuel at \(j\) to continue).

On this new graph, run Floyd-Warshall again. Now stops[i][j] = minimum number of intermediate refueling stops to get from \(i\) to \(j\).

vector<vector<int>> stops(n + 1, vector<int>(n + 1, 1e9));
for (int i = 1; i <= n; i++) stops[i][i] = 0;

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
        if (i != j && d[i][j] <= L)
            stops[i][j] = 1;

// Floyd on refueling graph
for (int k = 1; k <= n; k++)
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (stops[i][k] < 1e9 && stops[k][j] < 1e9)
                stops[i][j] = min(stops[i][j], stops[i][k] + stops[k][j]);

Gotcha. The edge cost in the refueling graph is 1, not the distance. We don't care about distance anymore --- that was handled in layer 1. Layer 2 only counts stops.

Full Trace

5 cities. Roads: 1-2 (3), 2-3 (4), 3-4 (2), 1-4 (10), 4-5 (3). Tank: \(L = 7\).

Layer 1: Floyd-Warshall distances.

	1	2	3	4	5
1	0	3	7	9	12
2	3	0	4	6	9
3	7	4	0	2	5
4	9	6	2	0	3
5	12	9	5	3	0

Reachable on one tank (\(\le 7\)):

From\To	1	2	3	4	5
1	-	Y	Y	N	N
2	Y	-	Y	Y	N
3	Y	Y	-	Y	Y
4	N	Y	Y	-	Y
5	N	N	Y	Y	-

Layer 2: Floyd on refueling graph.

	1	2	3	4	5
1	0	1	1	2	2
2	1	0	1	1	2
3	1	1	0	1	1
4	2	1	1	0	1
5	2	2	1	1	0

Query: \(1 \to 5\). Answer: 2 refueling stops.

Path: \(1 \to 3\) (distance 7, one tank) \(\to\) refuel \(\to\) \(5\) (distance 5, one tank) \(\to\) refuel. Two stops.

The Complete Code

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

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

    const long long INF = 1e18;
    vector<vector<long long>> d(n + 1, vector<long long>(n + 1, INF));
    for (int i = 1; i <= n; i++) d[i][i] = 0;

    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        d[u][v] = min(d[u][v], (long long)w);
        d[v][u] = min(d[v][u], (long long)w);
    }

    // Layer 1: all-pairs shortest distances
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (d[i][k] != INF && d[k][j] != INF)
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

    // Layer 2: refueling graph
    const int BIG = 1e9;
    vector<vector<int>> stops(n + 1, vector<int>(n + 1, BIG));
    for (int i = 1; i <= n; i++) stops[i][i] = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (i != j && d[i][j] <= L)
                stops[i][j] = 1;

    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (stops[i][k] < BIG && stops[k][j] < BIG)
                    stops[i][j] = min(stops[i][j], stops[i][k] + stops[k][j]);

    int q;
    cin >> q;
    while (q--) {
        int s, t;
        cin >> s >> t;
        cout << (stops[s][t] >= BIG ? -1 : stops[s][t]) << "\n";
    }

    return 0;
}

Graph on Graph

This "two-layer Floyd" technique is a specific instance of a broader pattern: graph on graph. You compute something on graph \(G_1\), then build a new graph \(G_2\) whose edges are derived from \(G_1\)'s results, and compute something else on \(G_2\).

The pattern appears whenever:

The raw graph encodes distances/costs.
The answer you need is in a different "currency" (stops, transfers, swaps).
The second graph's edges are determined by thresholds on the first graph's answers.

Why Not Dijkstra with Fuel State?

For a single query, dist[city][fuel] with Dijkstra works fine. Complexity: \(O(N \cdot L \cdot \log(N \cdot L))\).

But for all-pairs with \(Q\) queries, you'd run this \(N\) times. Total: \(O(N^2 \cdot L \cdot \log(N \cdot L))\).

The two-layer Floyd approach is \(O(N^3)\) for both layers combined. With \(N \le 300\), that's \(2.7 \times 10^7\) --- fast.

Approach	Complexity	For \(N = 300, L = 10^9\)
Dijkstra per query	\(O(Q \cdot N \cdot L \cdot \log)\)	Way too slow
Two-layer Floyd	\(O(N^3)\)	\(\sim 2.7 \times 10^7\)

Key insight. Floyd doesn't need the fuel dimension at all. By separating "compute distances" from "compute stops", each layer uses plain Floyd on plain graphs. The fuel tank is implicit in the edge-existence criterion of layer 2.

Exercises

Refueling cost. What if refueling costs \(C\) dollars per stop, and you want to minimize total dollars? How does layer 2 change?
Partial refueling. What if refueling only adds \(F\) units (not full tank)? Can the two-layer Floyd approach still work, or must you use state expansion?
One-way roads. If the roads are directed, does the algorithm change? What about the refueling graph's edge criterion?

Problems

Problem	Link	Difficulty
AtCoder abc143_e — Travel by Car	atcoder.jp/contests/abc143/tasks/abc143_e	Hard
LC 871 — Minimum Number of Refueling Stops	leetcode.com/problems/minimum-number-of-refueling-stops	Hard