Two-Source Combine

Product graphs cost O(N²). But many "two-sided" problems don't need them. Run two independent shortest-path computations and combine per vertex. O(V log V), not O(V² log V).

---

The Pattern

1. Dijkstra from source S → dist_fwd[v] for all v.
2. Dijkstra from target T on reversed graph → dist_rev[v] for all v.
3. For each vertex v: shortest S → v → T = dist_fwd[v] + dist_rev[v].

---

Problem 1: Typical90 #13 — Passing

For each city v, find the shortest path from 1 to N that passes through v.

auto d1 = dijkstra(1, adj, n);
auto dn = dijkstra(n, radj, n);
for (int v = 1; v <= n; v++)
    cout << d1[v] + dn[v] << "\n";

Two Dijkstra runs. One line of combination.

---

Problem 2: ABC035-D — Treasure Hunt

Directed graph. Town i earns A[i] yen per minute. Start at town 1, return at exactly time T. Maximize earnings.

💡 Key insight. Travel to one town, stay the whole time collecting, travel back. Splitting across towns is never better.

City v	A[v]	dist_fwd[v]	dist_rev[v]	Stay	Profit
1	2	0	0	10	20
2	8	3	3	4	32
3	5	2	4	4	20

Answer = max over v of A[v] × (T - dist_fwd[v] - dist_rev[v]).

---

Problem 3: SoundHound 2018 D — Saving Snuuk

Two currency graphs (yen, snuuk). Exchange at one city. Offices close over time.

1. Dijkstra from s using yen → dist_yen[v].
2. Dijkstra from t using snuuk (reversed) → dist_snuuk[v].
3. Profit at city v = 10^15 - dist_yen[v] - dist_snuuk[v].
4. Suffix max sweep as offices close.

auto dy = dijkstra(s, adj_yen, n);
auto ds = dijkstra(t, radj_snuuk, n);
ll mx = -1e18;
for (int i = n; i >= 1; i--) {
    mx = max(mx, (ll)1e15 - dy[i] - ds[i]);
    cout << mx << "\n";
}

---

Two-Source vs Product Graph

	Two-Source	Product Graph
States	O(V)	O(V²)
Use when	Agents move independently	Agents' moves are coupled
Example	"Best meeting point"	"Both must move each step"

⚠ Gotcha. For directed graphs, the reverse Dijkstra runs on the reversed graph (all edges flipped). For undirected, same adjacency list works.

---

Exercises

1. In Treasure Hunt, why is one-town-stay always optimal?
2. Can you solve LC 1976 (Number of Ways to Arrive) with two-source combine?
3. What if the graph has negative edges — does the pattern still work?

Problems

Problem	Link	Difficulty
Typical90 #13 — Passing	atcoder.jp	Medium
ABC035-D — Treasure Hunt	atcoder.jp	Medium
SoundHound 2018 D	atcoder.jp	Hard
LC 1976 — Number of Ways	leetcode.com	Medium