Loading...
Loading...
Loading...
A city has k bus routes. Each route is a list of stops, and its bus runs along them again and again in both directions. So on one bus you can ride from any of its stops to any other of its stops.
Pooja starts at stop s and wants to reach stop t. She can get off at any stop and change to another bus that also stops there.
Print the fewest buses she must take. Print 0 if s and t are the same stop, and -1 if t cannot be reached.
Example
Input
2 3 1 2 7 3 3 6 7 1 6
Output
2
Take the first bus from 1 to 7, then change to the second bus and ride to 6. That is 2 buses.
Try the problem first. Open one hint at a time.
The cost is the number of buses, not the number of stops. Riding further on the same bus is free.
So think of each route as one point. Two routes are linked when they share a stop.
Start with every route that serves s (1 bus). The routes linked to those need 2 buses, and so on, level by level.
Run a breadth-first search over the routes, using a HashMap from stop to the routes that serve it. Mark routes (and stops) as used so each is handled once.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor