Fewest Service Hops Across Shared Routes
A transit-style service mesh runs fixed routes, each visiting a set of stops in a loop. Boarding or staying on a route is free; switching routes counts as one hop. Find the minimum number of routes you must board to travel from a source stop to a target stop.
Problem
Given routes where routes[i] is the list of stops served by route i (cyclically), and integers source and target stops, return the least number of routes taken to get from source to target. Return -1 if impossible. Taking a route lets you reach any stop on it.
Input
A 2D array routes, and integers source and target.
Output
The minimum number of routes boarded, or -1.
Constraints
- 1 ≤ routes.length ≤ 500
- 1 ≤ total stops across routes ≤ 1e5
- 0 ≤ stop id ≤ 1e6
Examples
Example 1
Input
routes=[[1,2,7],[3,6,7]] source=1 target=6
Output
2
Board route 0 (stop 1→7), switch to route 1 (7→6): 2 routes.
Example 2
Input
routes=[[7,12],[4,5,15],[6],[15,19],[9,12,13]] source=15 target=12
Output
-1
No chain of shared stops links 15 to 12.