Fewest Bus Transfers to Reach a Stop
Each bus route is a fixed loop of stops. You may board and ride any route, transferring between routes only at shared stops. Find the minimum number of buses to ride from a source stop to a target stop.
Problem
You are given an array routes where routes[i] is the list of stops the i-th bus visits repeatedly. Starting at the bus stop source, you want to reach target. Return the least number of buses you must take, or -1 if impossible. You may walk between routes only by being at a shared stop.
Input
An array routes (each a list of stop ids), and integers source and target.
Output
An integer: minimum number of buses, or -1.
Constraints
- 1 <= routes.length <= 500
- Sum of all stops across routes <= 10^5
- 0 <= source, target < 10^6
Examples
Example 1
Input
routes = [[1,2,7],[3,6,7]], source = 1, target = 6
Output
2
Take bus 0 (1→7), transfer at 7, take bus 1 (7→6).
Example 2
Input
routes = [[7,12],[4,5,15],[6],[15,19],[9,12,13]], source = 15, target = 12
Output
-1
No sequence of buses connects 15 to 12.