Skip to content

Reverse Time

It's 2 AM. Your last chance to catch a connection home leaves at 2:15. Every minute you push your departure later is a minute of extra sleep. You don't want the fastest route --- you want the latest possible departure that still gets you there.

Forward Dijkstra minimizes arrival time. But when you want to maximize departure time, you need to think backwards. Start at the destination, rewind the clock, and work outward.

The Setup: AtCoder abc342_e (Last Train)

Meet in the middle: forward and reverse BFS meet at optimal point

Reverse BFS from target: flip all edges and search backwards

\(N\) cities, \(M\) train lines. Train line \(i\) runs from city \(A_i\) to city \(B_i\). Departures at times \(l_i, l_i + d_i, l_i + 2d_i, \ldots, l_i + (k_i - 1) \cdot d_i\). Each train takes \(c_i\) time.

For each city \(1, 2, \ldots, N-1\): find the latest time you can depart and still reach city \(N\). Output \(-1\) if impossible.

Why Forward Search Fails

Forward Dijkstra from city \(u\) finds the earliest arrival at \(N\). But we want the latest departure, not earliest arrival. Worse, we'd need to try every possible departure time from every city --- that's an infinite search space.

Even running forward Dijkstra from a single source answers "earliest arrival," which is the wrong question. And we'd need \(N-1\) separate runs. That's \(O(N)\) Dijkstra calls.

Key insight. "Latest departure that still reaches the target" is the reverse of "earliest arrival from the source." One backward search from the target answers all \(N-1\) queries at once.

The Reverse Perspective

Start at city \(N\). You can "arrive" there at any time --- set latest[N] = +infinity.

Now work backwards. For each train arriving at city \(N\) (say from city \(u\)), find the latest departure from \(u\) that reaches \(N\) before the deadline. That departure time becomes a candidate for latest[u].

Then from city \(u\) with latest[u] known, work backwards again: for each train going to \(u\), find the latest departure that arrives before latest[u].

This is Dijkstra, but maximizing instead of minimizing.

Latest Departure Calculation

Trains from \(u\) to \(v\) depart at times \(l, l+d, l+2d, \ldots, l+(k-1)d\).

You must arrive at \(v\) by time \(T\) (the latest viable time at \(v\)). Travel takes \(c\). So you need:

\[\text{depart} + c \leq T \implies \text{depart} \leq T - c\]

Find the largest \(t = l + jd\) with \(t \leq T - c\):

\[j \leq \frac{T - c - l}{d}\]
long long deadline = T - c;
if (deadline < l) return -1;  // even the first train is too late
long long j = min(k - 1, (deadline - l) / d);
return l + j * d;

Gotcha. Don't forget min(k-1, ...). There are only \(k\) departures total. The formula might give \(j = 10^{18}\), but the schedule might only have 5 trains.

Max-Priority Dijkstra

Standard Dijkstra uses a min-priority queue: pop the smallest distance first. Here we want the largest latest-departure first.

Why does max-first work? Consider two arrivals at city \(v\): one allowing latest[v] = 100, another allowing latest[v] = 120. The value 120 is strictly better --- it gives you more flexibility on every outgoing (incoming, in reverse) edge. Once we pop \(v\) with value 120, any future update can only be \(\leq 120\).

This is exactly Dijkstra's argument with the inequality flipped.

const long long INF = 2e18;
priority_queue<pair<long long,int>> pq;  // max-heap
latest[n-1] = INF;
pq.push({INF, n-1});

while (!pq.empty()) {
    auto [T, v] = pq.top(); pq.pop();
    if (T < latest[v]) continue;  // stale entry
    for (auto& [u, l, d, k, c] : rev_adj[v]) {
        long long dep = latest_depart(T, l, d, k, c);
        if (dep == -1) continue;
        if (dep > latest[u]) {
            latest[u] = dep;
            pq.push({dep, u});
        }
    }
}

Key insight. This is Dijkstra with all comparisons flipped. Min becomes max. "Shorter" becomes "later." The correctness proof is a mirror image.

Building the Reverse Adjacency List

The problem gives trains from \(A\) to \(B\). For reverse Dijkstra, we need to know which trains arrive at each city. Store them by destination:

// For each destination v, store (source u, schedule l, d, k, travel c)
rev_adj[b].push_back({a, l, d, k, c});

When processing city \(v\), iterate rev_adj[v] to find all cities that send trains to \(v\).

Trace: 4-City Example

Cities: 1--4. Target = 4.

Train From To Schedule (\(l, d, k\)) Travel \(c\)
1 1 2 \(l=5, d=3, k=4\) (at 5, 8, 11, 14) \(c=2\)
2 2 4 \(l=10, d=5, k=3\) (at 10, 15, 20) \(c=3\)
3 1 3 \(l=1, d=1, k=20\) (at 1, 2, ..., 20) \(c=4\)
4 3 4 \(l=12, d=6, k=2\) (at 12, 18) \(c=1\)

Reverse adjacency:

  • rev_adj[2] = [(1, 5, 3, 4, 2)]
  • rev_adj[4] = [(2, 10, 5, 3, 3), (3, 12, 6, 2, 1)]
  • rev_adj[3] = [(1, 1, 1, 20, 4)]
Step Pop (T, v) latest[v] Train Calculation Update
1 (INF, 4) INF 2->4 deadline=INF-3, j=min(2,huge)=2, dep=20 latest[2]=20
1 (INF, 4) INF 3->4 deadline=INF-1, j=min(1,huge)=1, dep=18 latest[3]=18
2 (20, 2) 20 1->2 deadline=20-2=18, j=min(3,(18-5)/3)=min(3,4)=3, dep=14 latest[1]=14
3 (18, 3) 18 1->3 deadline=18-4=14, j=min(19,(14-1)/1)=min(19,13)=13, dep=14 14 <= 14, no update
4 (14, 1) 14 source, done --- ---

Answers:

  • City 1: latest departure = 14
  • City 2: latest departure = 20
  • City 3: latest departure = 18

Verification for city 1: Depart at 14 on train 1 (last scheduled departure: 5, 8, 11, 14). Arrive city 2 at \(14 + 2 = 16\). Take train 2 at time 20 (\(20 \geq 16\), valid). Arrive city 4 at \(20 + 3 = 23\). Success.

Could city 1 leave later? Train 1's departures are 5, 8, 11, 14. No departure after 14. So 14 is the latest.

The INF Initialization

We set latest[N] = INF because you can arrive at the destination at any time. There's no deadline for being at the target --- you just need to get there.

Gotcha. Using LLONG_MAX is dangerous. Computing deadline = T - c when \(T\) = LLONG_MAX causes overflow. Use a large sentinel like \(2 \times 10^{18}\) instead. This is safely within long long range and won't overflow in subtraction.

Forward + Reverse: A Powerful Pair

Many problems combine both directions:

  • Forward from source: earliest arrival at every node.
  • Reverse from target: latest viable departure from every node.

AtCoder abc035_d (Treasure Hunt) uses exactly this. Forward Dijkstra gives shortest travel time from home to each city. Reverse Dijkstra gives shortest return time from each city. The difference tells you how long you can stay and earn money.

Key insight. Forward search answers "when do I arrive?" Reverse search answers "when must I leave?" Together they bracket the time window at each node.

When Reverse Search Is the Right Tool

Use reverse Dijkstra when:

  1. Maximize departure time --- you want the latest start, not earliest arrival.
  2. One target, many sources --- reverse from the single target answers every source in one pass.
  3. Deadline at destination --- work backwards from the constraint.

Forward search is the wrong tool for all three. It would need \(O(N)\) separate runs.

Correctness of Max-Dijkstra

Why does processing in max-first order work? The argument mirrors standard Dijkstra:

  1. When we pop \((T, v)\) from the max-heap, \(T = \text{latest}[v]\) is optimal.
  2. Proof: any path not yet explored goes through some unpopped node \(w\) with \(\text{latest}[w] \leq T\).
  3. Going through \(w\) can only make things worse (arrive earlier at \(v\), giving a tighter deadline).
  4. So no future path can improve \(\text{latest}[v]\).

The only requirement: the "latest departure" function is monotone. If you have more time at \(v\) (\(T\) is larger), you get an equal or later departure from \(u\). This holds because a later deadline gives access to all the same trains plus possibly later ones.

Complexity

Single reverse Dijkstra: \(O((N + M) \log N)\). Answers all \(N-1\) queries at once. Forward Dijkstra from each source would cost \(O(N(N + M) \log N)\).

The reverse approach is a factor of \(N\) faster.

Exercises

  1. Overflow check. You set latest[N] = 2e18. A train has \(c = 10^9\). Is deadline = 2e18 - 1e9 safe in long long? What if \(d = 1\) and \(l = 0\)?

  2. No solution. City \(u\) has no trains to any city reachable from \(N\) in reverse. What value does latest[u] keep? How does this propagate to cities that only connect through \(u\)?

  3. Bidirectional trains. If every train runs both directions with the same schedule, how do you build the reverse adjacency list? Does it simplify?

Problems

Problem Link Difficulty
AtCoder abc342_e --- Last Train atcoder.jp/contests/abc342/tasks/abc342_e Hard
AtCoder abc035_d --- Treasure Hunt atcoder.jp/contests/abc035/tasks/abc035_d Hard