Earliest Arrival Time with Bus Schedules (Time-Dependent Shortest Path)

Problem: Earliest Arrival Time with Bus Schedules (Time-Dependent Shortest Path) You are given several bus route schedules / operational data. Each route provides: An ordered list of stops along the route. Travel time (minutes) between each pair of consecutive stops. Waiting time at stops (minutes). Given a trip request: origin start destination end departure time t0 (integer timestamp in minutes) Compute and return the earliest arrival time (in minutes timestamp) at end when starting from start at time t0, using the available bus routes (transfers allowed). Notes Model this as a graph path-planning problem where nodes are stops and edges represent rideable bus legs. The cost of a leg includes waiting and travel time, and may depend on the time you arrive at a stop (if departure times exist). Output Output an integer: the earliest arrival time (timestamp in minutes). If end is unreachable, output -1. Suggested constraints Number of stops N <= 1e4 Number of routes M <= 1e3 Total stops across all routes S <= 2e5 All times are non-negative integers within 0 ~ 1e9 Test cases Because the original post does not provide a concrete input format, below are 5 logical test scenarios to validate your implementation: Start equals end: start=end, any t0, output should be t0. Single-route direct ride: one route contains start -> ... -> end, no transfer; output is t0 + waiting + travel + .... Transfer is faster: a direct route exists but slower; transferring across two routes is faster; output should reflect the transfer plan. Unreachable: no route combination can reach end; output -1. Cycles exist: routes form cycles; algorithm must avoid infinite loops and still return the earliest arrival time. Example Input (logical) start=end, t0=120 routes=any Output 120