When the places are groups
Count the fewest bus rides by treating each whole route as one place in the graph. About 15 minutes.
Count rides, not stops
A city has several bus routes. Each route is a list of stops and runs both ways. You want the fewest buses to get from one stop to another. Staying on the same bus is free. Getting off and boarding a different bus costs a ride.
That suggests making each route a place. Two routes are joined if they share a stop, because you can change there. The first ride puts you on any route that serves your starting stop. The answer is how many routes you pass through before you reach one that serves the target.
at_stop = {}
at_stop.setdefault(stop, []).append(route)- rides
- 1
Stop 1 is served only by R1. Board it: 1 ride.
Searching over routes
Look up which routes serve the starting stop and put them all in the line with a ride count of 1. Then run the usual search. Taking a route from the line, check whether the target is one of its stops. If so, its ride count is the answer.
Otherwise, for each stop on the route, every other route at that stop gets one more ride and joins the line. Skip routes already reached. If the start is the target, no ride is needed. If the line empties, the answer is -1.
rides = 1 # the first bus rides += 1 # change to another
Two routes share a stop. What does moving from one to the other count as?
- AOne more ride, because you change buses there
- BNothing, because it is the same place
- CThe number of stops between the two
Show the answer
One more ride, because you change buses there. Each time you board a different route, the ride count goes up by one.
Fewest buses
routes[i] is the list of stops served by bus route i, and each route can be ridden in either direction. You start at stop source and want to reach stop target, and you may only travel by bus. Return the fewest bus rides needed, counting each time you board a bus. Return 0 if source equals target and -1 if you cannot get there.
routes = [[1, 2, 7], [3, 6, 7], [7, 9], [9, 10]], source = 1, target = 10 → 3
1 ≤ routes ≤ 300 · 1 ≤ stops on a route ≤ 20 · stop numbers up to 1,000,000