1660. Gates That Open on a Timetable

A depot network has n yards and m ONE-WAY tracks. Track (u, v, w) takes w minutes. Every yard has a gate on a timetable of period p: yard i may be LEFT only at a minute t with t mod p == off[i]. Waiting inside a yard is allowed and takes one minute per minute.

A wagon is at yard 1 at minute 0. Print the earliest minute it can be at yard n, or -1 if it never can.

3 yards, period 3, offsets 0 1 0 track 1 -> 2 takes 1, track 2 -> 3 takes 1 -> 2

Leave yard 1 at minute 0, which is allowed because 0 mod 3 == 0. Arrive at yard 2 at minute 1, which is allowed to be left because 1 mod 3 == 1. Arrive at yard 3 at minute 2.

## The four things that have to be said

directed? yes. A track may be used only in its stated direction. self-loops? allowed. One costs w minutes and returns you to the same yard, which is only ever a slow way to wait. parallel tracks? allowed, at different times. unreachable? yes. If no sequence of tracks leads from yard 1 to yard n, print -1. Note that the timetable alone can never make a reachable yard unreachable, because waiting is always available. When n is 1 the answer is 0.

## What most people try first

Dijkstra over the yards, and when a track cannot be taken at the current minute, add the wait to its weight. That is nearly right and it is wrong, because the wait depends on the minute of arrival and the search keeps only one arrival per yard. The earliest arrival is not always the best one: arriving at minute 4 at a yard whose gate opens at minute 5 is better than arriving at minute 1 at a yard whose gate opens at minute 10, and a single number per yard cannot express that.

Here, as it happens, earliest arrival IS best, because waiting is free of anything but time and the gate condition depends only on the minute. But that argument needs the clock in the state to be made at all, and the natural implementation without it computes the wait from a stale arrival minute.

## The node of the search is a pair

Only the minute MODULO p decides whether a gate is open, so the clock can be folded to p values. Search the PRODUCT graph whose vertices are pairs (yard, minute mod p). Its size is n * p, which at the limits is 2000 * 50 = 100000 states.

wait one minute (v, c) -> (v, (c + 1) mod p) cost 1, always take a track (u, off[u]) -> (v, (off[u] + w) mod p) cost w start (1, 0) answer the smallest distance over all states (n, c)

The second arc exists only out of the one clock value where the gate is open, which is what enforces the timetable. The distance being minimised is the ABSOLUTE minute, while the second coordinate is that minute reduced mod p, and keeping those two apart is the whole trick.

## Why reducing the clock is safe

Two states with the same yard and the same minute mod p have identical futures: every gate condition and every track is decided by the residue alone, and a track's duration is fixed. So the earlier of two such arrivals is at least as good, and nothing is lost by keeping only it. Without the reduction the state space is unbounded, since waiting can go on forever.

Every arc cost is positive, so Dijkstra is correct on the product graph as it stands.

## Cost

O((n * p + m) log(n * p)) time and O(n * p) memory. The answer is bounded by the number of states times the largest single step, about 100000 * 1000 = 10^8 minutes, which is inside the 2147483647 a signed 32 bit integer holds.

Constraints - `1 ≤ n ≤ 2000` - `0 ≤ m ≤ 10000` - `1 ≤ p ≤ 50` - `0 ≤ off[i] ≤ p - 1` - `1 ≤ w ≤ 1000`