Bus Routes

Problem

You are given a list routes, where routes[i] is the list of bus stops that bus i visits, looping forever. You start at stop source, not on any bus, and want to reach stop target. You can board any bus at any stop it serves, ride it to any other stop it serves, and switch buses at shared stops. Return the minimum number of buses you must board to reach target, or -1 if it is impossible. If source == target, the answer is 0.

• There are at most a few hundred bus routes, and the total number of stops across all of them fits comfortably in memory.
• Stop ids are arbitrary integers; each route lists distinct stops.

Examples

• routes = [[2,5,9],[4,9,11],[11,14]], source = 2, target = 14 → 3. Bus 0 to stop 9, bus 1 to stop 11, bus 2 to stop 14.
• routes = [[10,20],[5,8,25],[3],[25,30],[16,20,22]], source = 25, target = 20 → -1. No chain of shared stops links 25 to 20.
• routes = [[3,4]], source = 4, target = 4 → 0. Already there.

Hints

1. The cost is the number of buses, not the number of stops. What should a "step" in your search represent?
2. Two buses are "adjacent" if they share a stop. Which stops does a bus let you reach, and which buses can you reach from a stop?
3. BFS where each level is one bus ride: from the current set of stops, board every not-yet-taken bus through them, and add all their stops. Precompute stop -> buses for that.