Assign Waiting Riders to the Earliest-Arriving Car on Fixed Routes

A map has `n` attractions, numbered `0` to `n - 1`, joined by two-way roads. `roads[i] = [u, v, t]` is a road between attractions `u` and `v` that takes `t` minutes to drive in either direction. Several cars each drive one fixed route. `routes[c]` is the ordered list of attractions that car `c` visits. Every car leaves the first attraction of its route at time `0` and drives the route once without waiting anywhere, so it reaches each later attraction after the total driving time of the roads along its route up to that attraction. Riders are waiting at attractions from time `0`. `riders[p] = [start, dest]` means rider `p` is at attraction `start` and wants to reach attraction `dest`. Each rider takes the earliest-arriving car that can carry them there. Return which riders each car carries. ### Function Signature ```python def assign_riders(n: int, roads: list[list[int]], routes: list[list[int]], riders: list[list[int]]) -> list[list[int]]: ``` ### Rules - The arrival time of car `c` at position `i` of its route (0-based) is the sum, over every `j < i`, of the time of the road between `routes[c][j]` and `routes[c][j + 1]`. The arrival time at position `0` is `0`. - Car `c` can carry rider `p` only if `start` appears in `routes[c]` and `dest` appears in `routes[c]` at a later position. - Among the cars that can carry rider `p`, the rider boards the one with the smallest arrival time at `start`. If several of those cars tie, the rider boards the one with the smallest index. - A rider whom no car can carry boards no car. Cars have unlimited capacity, and riders never change cars. - Return a list `result` with one list per car: `result[c]` holds the indices of the riders that car `c` carries, in increasing order. A car that carries nobody gets an empty list. ### Constraints - `2 <= n <= 10^4` - `1 <= len(roads) <= 5 * 10^4`. Each road `[u, v, t]` has `0 <= u, v < n`, `u != v` and `1 <= t <= 10^4`, and at most one road joins any pair of attractions. - `1 <= len(routes) <= 1000`. Each route has at least 2 attractions, never visits an attraction twice, and every two consecutive attractions on it are joined by a road. All routes together hold at most `10^5` attractions. - `1 <= len(riders) <= 10^5`. Each rider `[start, dest]` has `0 <= start, dest < n` and `start != dest`. - Every arrival time is below `10^9`, so it fits in a 32-bit signed integer. ### Examples **Example 1** ```text Input: n = 5, roads = [[0, 1, 4], [1, 2, 3], [2, 3, 2], [0, 4, 1], [4, 2, 2], [1, 3, 6]], routes = [[0, 1, 2, 3], [4, 2, 1], [0, 4, 2, 3]], riders = [[0, 3], [2, 3], [2, 1], [4, 0], [1, 2]] Output: [[0, 4], [2], [1]] ``` Car 0 reaches attractions 0, 1, 2, 3 at times 0, 4, 7, 9. Car 1 reaches 4, 2, 1 at times 0, 2, 5. Car 2 reaches 0, 4, 2, 3 at times 0, 1, 3, 5. - Rider 0 (0 to 3): cars 0 and 2 both reach attraction 0 at time 0, so the tie goes to car 0. - Rider 1 (2 to 3): car 0 reaches 2 at time 7 and car 2 at time 3, so car 2. Car 1 never reaches 3. - Rider 2 (2 to 1): only car 1 visits 1 after 2. - Rider 3 (4 to 0): no car visits 0 after 4, so rider 3 rides nothing. - Rider 4 (1 to 2): only car 0 visits 2 after 1. **Example 2** ```text Input: n = 3, roads = [[0, 1, 5], [1, 2, 5], [0, 2, 20]], routes = [[0, 2], [0, 1, 2]], riders = [[0, 2], [1, 2]] Output: [[0], [1]] ``` Both cars reach attraction 0 at time 0, so rider 0 boards car 0 by index, even though car 1 reaches attraction 2 sooner. Only car 1 visits attraction 1. **Example 3** ```text Input: n = 2, roads = [[0, 1, 7]], routes = [[1, 0]], riders = [[0, 1]] Output: [[]] ``` The car visits attraction 1 before attraction 0, so it cannot take the rider from 0 to 1.