A city runs len(routes) bus lines. Bus i drives around the loop routes[i] forever, calling at each of its stops in turn, so you can ride it from any of its stops to any other. You can get on or off a bus at any stop it calls at, and change to another bus at a stop they share.
You are standing at stop source, not on any bus. Write fewest_buses(routes, source, target) -> int that returns the fewest buses you need to take to reach stop target, or -1 if you can't get there. Staying on one bus for many stops counts as one bus. Walking isn't allowed.
fewest_buses([[1, 4, 7], [3, 7, 9], [9, 12]], 1, 12) # 3 (bus 0 to 7, bus 1 to 9, bus 2 to 12)
fewest_buses([[2, 5, 8], [8, 6, 11], [11, 5]], 2, 11) # 2 (bus 0 to 8, then bus 1; or bus 0 to 5, then bus 2)
fewest_buses([[1, 2], [3, 4]], 1, 4) # -1 (the lines never meet)
fewest_buses([[1, 2]], 6, 6) # 0 (you're already there)
Constraints:
1 <= len(routes) <= 500and1 <= len(routes[i]) <= 10^5.- All routes together have at most
10^5stops. The stops on one route are distinct. - Stop numbers,
sourceandtargetare in0 .. 10^6 - 1.sourceandtargetneed not be on any route. Ifsource == targetthe answer is0. - ⭐ Bonus: a speed test with routes of 50,000 stops earns a star in O(total number of stops). A search that rescans a whole route each time it reaches one of the route's stops is too slow for it.
Show hint
The answer counts buses, not stops. Think of each bus as one node: you can switch between two buses if they share a stop. Breadth-first search from the buses that call at source then counts buses directly. To keep it fast, read each bus's stop list at most once.