Bus Routes
You are given an array routes representing bus routes where routes[i] is a bus route that the i^th bus repeats forever.
- For example, if
routes[0] = [1, 5, 7], this means that the0^thbus travels in the sequence1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ...forever.
You will start at the bus stop source; you are not on any bus initially. You want to go to the bus stop target, and you can travel between bus stops by buses only.
Return the least number of buses you must take to travel from source to target. Return -1 if it is not possible.
Example 1
Input
routes = [[1,2,7],[3,6,7]], source = 1, target = 6Output
2The best strategy is to take the first bus to bus stop 7, then take the second bus to bus stop 6.
Example 2
Input
routes = [[7,12],[4,5,15],[6],[15,19],[9,12,13]], source = 15, target = 12Output
-1There is no sequence of buses that can take you from bus stop 15 to bus stop 12.
Constraints
- 1 <= routes.length <= 500.
- 1 <= routes[i].length <= 10^5
- All the values of routes[i] are unique.
- sum(routes[i].length) <= 10^5
- 0 <= routes[i][j] < 10^6
- 0 <= source, target < 10^6