Graph on Graph
Sometimes one round of shortest paths isn't the answer. It's the raw material. You compute distances on graph 1, use those distances to build graph 2, then solve graph 2. Two phases. Two graphs. One answer that neither graph could produce alone.
The Pattern
The graph-on-graph pattern has three phases:
- Phase 1: Compute shortest paths on the original graph.
- Phase 2: Build a derived graph using those distances as construction rules.
- Phase 3: Solve the actual problem on the derived graph.
This shows up whenever the problem has two scales: a local metric (distance, fuel, time) and a global metric (refueling stops, currency exchanges, relay hops).
Problem 1: ABC143-E Travel by Car
\(N\) cities, \(M\) roads with distances. A car has a fuel tank of capacity \(L\). Every city has a gas station that fills the tank completely. Find, for \(Q\) queries \((s, t)\), the minimum number of refueling stops to get from \(s\) to \(t\).
Phase 1: Compute all-pairs shortest distances using Floyd-Warshall. Let \(d[i][j]\) be the shortest road distance from city \(i\) to city \(j\).
Phase 2: Build a new graph. Add edge \((i, j)\) with weight 1 if \(d[i][j] \leq L\) (reachable on one tank). If \(d[i][j] > L\), no direct edge.
Phase 3: Run Floyd-Warshall again on the derived graph. Now \(d_2[s][t]\) gives the minimum number of refueling stops.
// Phase 1: Floyd on original graph
vector<vector<long long>> d(n, vector<long long>(n, 1e18));
for (int i = 0; i < n; i++) d[i][i] = 0;
for (auto& [u, v, w] : edges) {
d[u][v] = min(d[u][v], w);
d[v][u] = min(d[v][u], w);
}
for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
// Phase 2: Build derived graph
vector<vector<long long>> d2(n, vector<long long>(n, 1e18));
for (int i = 0; i < n; i++) d2[i][i] = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (i != j && d[i][j] <= L)
d2[i][j] = 1;
// Phase 3: Floyd on derived graph
for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
d2[i][j] = min(d2[i][j], d2[i][k] + d2[k][j]);
Key insight. The original graph measures distance. The derived graph measures refueling stops. Floyd-Warshall runs twice, but on completely different metrics. The first Floyd produces distances; the second Floyd produces hop counts.
Trace: Travel by Car
Cities: 4. Fuel capacity \(L = 5\).
Original distances (after Floyd):
| 0 | 1 | 2 | 3 | |
|---|---|---|---|---|
| 0 | 0 | 2 | 5 | 7 |
| 1 | 2 | 0 | 3 | 5 |
| 2 | 5 | 3 | 0 | 2 |
| 3 | 7 | 5 | 2 | 0 |
Derived graph (edge exists if \(d[i][j] \leq 5\)):
| 0 | 1 | 2 | 3 | |
|---|---|---|---|---|
| 0 | 0 | 1 | 1 | \(\infty\) |
| 1 | 1 | 0 | 1 | 1 |
| 2 | 1 | 1 | 0 | 1 |
| 3 | \(\infty\) | 1 | 1 | 0 |
After Floyd on derived graph:
| 0 | 1 | 2 | 3 | |
|---|---|---|---|---|
| 0 | 0 | 1 | 1 | 2 |
| 1 | 1 | 0 | 1 | 1 |
| 2 | 1 | 1 | 0 | 1 |
| 3 | 2 | 1 | 1 | 0 |
Query \((0, 3)\): answer = 2 stops. Path: \(0 \to 1 \to 3\) (refuel at city 1).
City 0 to city 3 has distance 7 > 5, so you can't go direct. But 0 to 1 is 2 \(\leq\) 5, and 1 to 3 is 5 \(\leq\) 5. Two tanks, one refuel stop.
Problem 2: SoundHound 2018-D Saving Snuuk
\(N\) cities, \(M\) roads. Each road has two costs: yen cost and snuuk cost. You travel from city 1 to city \(N\). At exactly one city \(k\) along the way, you exchange all remaining yen for snuuk (favorable rate). Find the route that minimizes total spending.
Phase 1a: Dijkstra from city 1 using yen costs. Gives \(\text{yen}[k]\) = min yen to reach city \(k\).
Phase 1b: Dijkstra from city \(N\) using snuuk costs on reversed edges. Gives \(\text{snuuk}[k]\) = min snuuk from city \(k\) to \(N\).
Phase 2: For each possible exchange city \(k\), compute \(\text{yen}[k] + \text{snuuk}[k]\).
Phase 3: Sweep from \(k = N\) down to \(k = 1\), tracking the running minimum of \(\text{snuuk}[k]\). For each city, the answer is the best exchange point from that city onward.
auto yen_dist = dijkstra(0, adj_yen); // forward, yen edges
auto snuuk_dist = dijkstra(n-1, adj_snuuk_rev); // backward, snuuk edges
// Best exchange point for travel from city 1 to city N
long long ans = LLONG_MAX;
for (int k = 0; k < n; k++)
if (yen_dist[k] < LLONG_MAX && snuuk_dist[k] < LLONG_MAX)
ans = min(ans, yen_dist[k] + snuuk_dist[k]);
Key insight. This is the same forward + reverse Dijkstra trick from Lesson 1, but now each Dijkstra runs on a different graph. The yen graph and the snuuk graph have different edge weights. You're combining results across two separate cost functions.
Problem 3: ABC035-D Treasure Hunt
\(N\) towns, \(M\) one-directional roads. Each town has a gold rate \(A[i]\) (gold per unit time spent there). You start at town 1 with \(T\) total time. You must return to town 1 by time \(T\). Maximize gold collected.
Strategy: travel to some town \(k\), stay there collecting gold, then return.
Phase 1a: Dijkstra from town 1 on the forward graph. Gives \(\text{go}[k]\) = time to reach town \(k\).
Phase 1b: Dijkstra from town 1 on the reverse graph (reverse all edges). Gives \(\text{back}[k]\) = time to return from town \(k\) to town 1.
Phase 2: For each town \(k\), compute \(\text{stay}[k] = T - \text{go}[k] - \text{back}[k]\). If \(\text{stay}[k] \geq 0\), the gold collected is \(\text{stay}[k] \times A[k]\).
auto go = dijkstra(0, adj_forward);
auto back = dijkstra(0, adj_reverse);
long long best = 0;
for (int k = 0; k < n; k++) {
if (go[k] >= LLONG_MAX || back[k] >= LLONG_MAX) continue;
long long stay = T - go[k] - back[k];
if (stay >= 0)
best = max(best, stay * A[k]);
}
Gotcha. The graph is directed. Reversing edges for the return trip is essential. If you run forward Dijkstra from \(k\) for each \(k\), you get \(O(N \times (N + M) \log N)\) which is far too slow. One reverse Dijkstra from town 1 on the reversed graph gives all return times in a single pass.
Trace: Treasure Hunt
Towns: 3. Time \(T = 10\). Gold rates: \(A = [0, 5, 3]\).
Forward distances from town 0: go = [0, 2, 4].
Reverse distances from town 0: back = [0, 3, 6].
| Town \(k\) | go[\(k\)] | back[\(k\)] | stay | gold |
|---|---|---|---|---|
| 0 | 0 | 0 | 10 | \(10 \times 0 = 0\) |
| 1 | 2 | 3 | 5 | \(5 \times 5 = 25\) |
| 2 | 4 | 6 | 0 | \(0 \times 3 = 0\) |
Best: town 1, gold = 25.
When to Use Graph-on-Graph
Look for these signals:
| Signal | Example |
|---|---|
| Two different metrics in one problem | Distance + fuel stops |
| "Compute X, then use X to decide Y" | Shortest path determines reachability, then count hops |
| Forward + reverse with different cost functions | Yen forward, snuuk backward |
| Optimal stay/exchange/switching point | Stay at best town, exchange at best city |
The common thread: the problem can't be solved in one pass because the two metrics interact. You need Phase 1 to extract information, then Phase 2 to act on it.
Complexity
For Floyd-based problems (\(N\) small, typically \(\leq 300\)):
- Phase 1: \(O(N^3)\).
- Phase 2: \(O(N^2)\) to build the derived graph.
- Phase 3: \(O(N^3)\).
- Total: \(O(N^3)\).
For Dijkstra-based problems (\(N\) large):
- Phase 1: \(O((N + M) \log N)\) per Dijkstra call.
- Phase 2: \(O(N)\) sweep.
- Total: \(O((N + M) \log N)\).
Key insight. The graph-on-graph pattern doesn't increase asymptotic complexity. The derived graph is usually sparser or uses a simpler algorithm than the original. The insight cost is high; the computational cost is low.
Exercises
-
Relay network. Cities have relay towers. A message can travel at most distance \(R\) per hop. Given all-pairs distances, how do you find the minimum number of relay hops between any two cities?
-
Bidirectional exchange. In Saving Snuuk, what if you could exchange back from snuuk to yen at a different rate? Does the two-Dijkstra approach still work?
-
Multiple stays. In Treasure Hunt, what if you could visit and collect gold at multiple towns (but travel time still counts)? Why does the single-stay greedy approach break?
Problems
| Problem | Link | Difficulty |
|---|---|---|
| ABC143-E — Travel by Car | atcoder.jp/contests/abc143/tasks/abc143_e | Medium |
| SoundHound 2018-D — Saving Snuuk | atcoder.jp/contests/soundhound2018-summer-qual/tasks/soundhound2018_summer_qual_d | Medium |
| ABC035-D — Treasure Hunt | atcoder.jp/contests/abc035/tasks/abc035_d | Medium |