Decide If a Passenger Can Reach a Station Using Time-Indexed Train Routes and Transfers

A train schedule is a collection of trains moving between stations, where stations are named by strings. Time starts at `0`. Each train is given as a list of stations, and the index in the list is the time at which the train is at that station: train `j` is at station `schedule[j][t]` at time `t`. A passenger starts at station `start` at time `0`. The passenger can ride trains, get off at any station, wait there, and board another train later. Return whether the passenger can reach station `dest`. ### Function Signature ```python def can_reach(schedule: list[list[str]], start: str, dest: str) -> bool: ``` ### Rules - Train `j` is at `schedule[j][t]` for `0 <= t < len(schedule[j])`, and is out of service after its last index. - At time `t`, a passenger at station `s` may either wait at `s` until time `t + 1`, or board any train `j` with `schedule[j][t] == s` and `t + 1 < len(schedule[j])`, arriving at `schedule[j][t + 1]` at time `t + 1`. - On arriving, the passenger may stay on the same train or get off. Changing trains at the same station at the same time takes no time. Waiting at a station has no time limit. - A train may stay at a station for several time steps, or visit a station more than once. - Return `True` if the passenger can be at `dest` at some time, and `False` otherwise. If `start == dest`, return `True`. ### Constraints - `1 <= len(schedule) <= 1000` - `1 <= len(schedule[j]) <= 1000`, and the total length of all trains is at most `2 * 10^5` - Station names consist of 1 to 10 uppercase English letters. - `start` and `dest` are station names. Either may be absent from every train. ### Examples **Example 1** ```text Input: schedule = [["A", "B", "C", "D", "E"], ["O", "B", "G", "H", "Z"]] start = "A", dest = "Z" Output: True ``` Ride the first train from `A` at time 0 to `B` at time 1. The second train is also at `B` at time 1, so change trains there and ride to `Z`, arriving at time 4. **Example 2** ```text Input: schedule = [["A", "B", "C"], ["B", "D"]] start = "A", dest = "D" Output: False ``` The second train leaves `B` after time 0, but the passenger cannot be at `B` before time 1. **Example 3** ```text Input: schedule = [["A", "B"], ["X", "Y", "B", "D"]] start = "A", dest = "D" Output: True ``` Arrive at `B` at time 1, wait until time 2, board the second train at `B`, and reach `D` at time 3.