Route Planner

You're given a Network of stations connected by edges. Each edge carries a travel time (in minutes) and a line name ("Blue", "Express", etc.). Some edges are one-way. The main planner method takes a start and end station and returns the route that minimizes total travel time, where switching lines costs an extra 5 minutes per transfer. A second planner method takes the same inputs plus a cap on how many times you can switch lines.

On the shipped test map, three routes exist from Central to Airport.

Green:  Central → Park → Airport                        4 + 6   = 10 min
Red:    Central → Harbor → Airport                      5 + 3   = 8 min
Blue:   Central → Mall → Stadium → Airport              2 + 3 + 2 = 7 min  (best)

The Blue route wins with three hops, even though by hop count you'd pick the two-hop Red route.

That transfer penalty looks like a small detail, but it's the thing the whole problem turns on. It means the cost of your next edge depends on which line you arrived on, and that single fact is what trips up every solution short of the last one.

BFS is the first algorithm most people reach for when they hear "shortest path". The template is short. You keep a queue of partial paths and a visited set of stations. On each step you pop the front of the queue and push every unvisited neighbor onto the back. The search stops the first time the destination comes off the queue, and that's the returned path.