Two-Mode Graphs
You drive a car across the country. At any city, you can ditch the car and hop on a train. But once you board the train, you never drive again. This one-way mode switch turns what looks like a single graph into a two-layer machine --- and unlocking that structure is the key to the entire chapter.
The Problem: ABC325-E Our Clients, Please Wait
There are \(N\) cities and a distance matrix \(D[i][j]\). Two transport modes:
- Car (mode 0): travel from city \(i\) to \(j\) costs \(D[i][j] \times A\).
- Train (mode 1): travel from city \(i\) to \(j\) costs \(D[i][j] \times B + C\).
You start at city 1 in a car. At any city, you can switch to train. Once you switch, you cannot go back to driving. Find the minimum cost to reach city \(N\).
Key insight. The irreversible switch from car to train creates a natural layering. You're not on one graph --- you're on two copies of the graph, stitched together by one-way bridges.
The Two-Layer Model
Build an expanded graph with \(2N\) nodes. Each city \(u\) has two copies: \((u, 0)\) for car mode and \((u, 1)\) for train mode.
Layer 0 (car): 1 --- 2 --- 3 --- ... --- N
| | | |
v v v v
Layer 1 (train): 1 --- 2 --- 3 --- ... --- N
Edges:
- Within layer 0: \((u, 0) \to (v, 0)\) with cost \(D[u][v] \times A\).
- Within layer 1: \((u, 1) \to (v, 1)\) with cost \(D[u][v] \times B + C\).
- Cross-layer: \((u, 0) \to (u, 1)\) with cost \(0\). One-way only.
Source: \((1, 0)\). Destination: \(\min(\text{dist}[N][0], \text{dist}[N][1])\).
Run Dijkstra on this expanded graph. That's it.
Why It Works
The cross-layer edges are one-directional: car to train, never train to car. This means the layer structure forms a DAG: once you drop to layer 1, you stay there. Dijkstra handles this naturally because it processes states in cost order.
Every valid journey is captured:
- Drive the whole way: stay on layer 0.
- Train the whole way: switch at city 1.
- Drive to city \(k\), switch, train the rest: cross at city \(k\).
No journey is counted twice. No illegal journey (train to car) is reachable.
Gotcha. The distance matrix \(D\) is \(N \times N\) with \(N\) up to 1000. That means \(O(N^2)\) edges per layer and \(O(N^2)\) total Dijkstra work. This is fine. Don't try to reduce edges --- the dense matrix forces \(O(N^2)\) regardless.
Trace: Layered Dijkstra
Cities: \(N = 3\), \(A = 2\), \(B = 1\), \(C = 5\).
Distance matrix:
| 1 | 2 | 3 | |
|---|---|---|---|
| 1 | 0 | 3 | 8 |
| 2 | 3 | 0 | 4 |
| 3 | 8 | 4 | 0 |
Car costs: \(D \times 2\). Train costs: \(D \times 1 + 5\).
| Step | Pop (cost, city, mode) | Update | Push |
|---|---|---|---|
| 1 | (0, 1, 0) | dist[1][0]=0 | (6, 2, 0), (16, 3, 0), (0, 1, 1) |
| 2 | (0, 1, 1) | dist[1][1]=0 | (8, 2, 1), (13, 3, 1) |
| 3 | (6, 2, 0) | dist[2][0]=6 | (14, 3, 0), (6, 2, 1) |
| 4 | (6, 2, 1) | dist[2][1]=6 | (10, 3, 1) |
| 5 | (8, 2, 1) | dist[2][1]=6, skip | --- |
| 6 | (10, 3, 1) | dist[3][1]=10 | done for node 3 |
| 7 | (13, 3, 1) | dist[3][1]=10, skip | --- |
| 8 | (14, 3, 0) | dist[3][0]=14 | --- |
| 9 | (16, 3, 0) | dist[3][0]=14, skip | --- |
Answer: \(\min(\text{dist}[3][0], \text{dist}[3][1]) = \min(14, 10) = 10\).
Best route: drive to city 2 (cost 6), switch to train, ride to city 3 (cost \(4 \times 1 + 5 = 9\))... wait, that's 15. But the table says 10. Let's check: drive to city 1 (cost 0), switch to train at city 1, train 1 \(\to\) 2 costs \(3 + 5 = 8\)... no. Train 1 \(\to\) 2 \(\to\) 3: \(8 + 9 = 17\).
Actually: switch at city 2. Car 1 \(\to\) 2 costs \(3 \times 2 = 6\). Train 2 \(\to\) 3 costs \(4 \times 1 + 5 = 9\). Total = 15.
Or: switch at city 1. Train 1 \(\to\) 3 directly: \(8 \times 1 + 5 = 13\). Total = 13.
Hmm, the Dijkstra found 10 at step 6. Path: \((1, 0) \to (2, 0)\) cost 6, then switch \((2, 0) \to (2, 1)\) cost 0, then \((2, 1) \to (3, 1)\) cost \(4 \times 1 + 5 = 9\)... that's \(6 + 9 = 15\), not 10.
Let me recheck. At step 4, we push \((6 + 4 \times 1 + 5, 3, 1) = (15, 3, 1)\). But step 2 pushed \((0 + 8 + 5, 3, 1) = (13, 3, 1)\). So the correct answer is 13. Let me redo:
| Step | Pop (cost, city, mode) | Update | Push |
|---|---|---|---|
| 1 | (0, 1, 0) | dist[1][0]=0 | (6, 2, 0), (16, 3, 0), (0, 1, 1) |
| 2 | (0, 1, 1) | dist[1][1]=0 | (8, 2, 1), (13, 3, 1) |
| 3 | (6, 2, 0) | dist[2][0]=6 | (14, 3, 0), (6, 2, 1) |
| 4 | (6, 2, 1) | dist[2][1]=6 | (15, 3, 1) |
| 5 | (8, 2, 1) | skip | --- |
| 6 | (13, 3, 1) | dist[3][1]=13 | --- |
| 7 | (14, 3, 0) | dist[3][0]=14 | --- |
| 8 | (15, 3, 1) | skip | --- |
| 9 | (16, 3, 0) | skip | --- |
Answer: \(\min(14, 13) = 13\). Switch at city 1, take train directly to city 3.
The Two-Dijkstra Alternative
Here's a cleaner approach that avoids building the layered graph entirely.
Observation: the mode switch happens at exactly one city \(k\). You drive from city 1 to \(k\), then take the train from \(k\) to \(N\). So the answer is:
Where:
- \(\text{car\_dist}[k]\) = shortest car-only distance from city 1 to \(k\).
- \(\text{train\_dist}[k]\) = shortest train-only distance from \(k\) to \(N\).
Compute \(\text{car\_dist}\) with a forward Dijkstra from city 1. Compute \(\text{train\_dist}\) with a reverse Dijkstra from city \(N\) (reversing all edges). Sweep over \(k\) to find the minimum.
auto car_dist = dijkstra_from(1, [&](int u, int v) {
return D[u][v] * A;
});
auto train_dist = dijkstra_reverse_from(N, [&](int u, int v) {
return D[v][u] * B + C; // reversed
});
long long ans = LLONG_MAX;
for (int k = 0; k < n; k++)
ans = min(ans, car_dist[k] + train_dist[k]);
Key insight. The two-Dijkstra approach works whenever the mode switch is irreversible and happens at a single point. You decompose the journey into "before switch" and "after switch" and optimize each half independently.
Comparing the Two Approaches
| Layered Dijkstra | Two-Dijkstra | |
|---|---|---|
| States | \(2N\) | \(N\) per run |
| Runs | 1 | 2 |
| Complexity | \(O(N^2 \log N)\) | \(O(N^2 \log N)\) |
| Generalizes to 3+ modes | Yes | Gets messy |
| Conceptual clarity | Mechanical | Insightful |
Both give \(O(N^2 \log N)\) for dense graphs. For sparse graphs, the layered approach scales better with more modes.
The General Pattern: Irreversible Mode Switches
Any time a problem says "you can switch from X to Y but never back," think layers.
- Walk to teleport: layer 0 = walking, layer 1 = teleporting. Switch is free but permanent.
- Healthy to injured: layer 0 = full speed, layer 1 = reduced speed after taking damage.
- Pre-upgrade to post-upgrade: layer 0 = normal costs, layer 1 = discounted costs after a one-time purchase.
The cross-layer edges are always one-directional. The mode you came from is gone forever.
Gotcha. If the switch is reversible (you can go back and forth between car and train), you don't get a layered DAG. Instead, you get a general expanded graph where both layers are fully connected. This is still solvable with Dijkstra on \(2N\) nodes, but you lose the DAG structure and the two-Dijkstra shortcut.
Exercises
-
Edge direction. In the layered model, why must cross-layer edges be \((u, 0) \to (u, 1)\) and not \((u, 0) \to (v, 1)\)? What would the second version mean?
-
Three modes. Car, train, and airplane. You can switch car \(\to\) train \(\to\) airplane but never backward. How many layers? How many cross-layer edge types?
-
Reversible switch. If you can switch between car and train freely (cost \(S\) each time), does the two-Dijkstra approach still work? Why or why not?
Problems
| Problem | Link | Difficulty |
|---|---|---|
| ABC325-E — Our Clients, Please Wait | atcoder.jp/contests/abc325/tasks/abc325_e | Medium |
| LC 2577 — Minimum Time to Visit a Cell In a Grid | leetcode.com/problems/minimum-time-to-visit-a-cell-in-a-grid | Hard |