Fewest Shuttle Boardings

Hard

Shuttles run around a campus. Shuttle i circles its loop of stops loops[i] forever: it visits them in order and, after the last one, goes back to the first. You are standing at stop start and have not boarded anything yet. You need to reach stop finish, and you can only travel by shuttle; you may change shuttles at any stop that both of them serve. Return the smallest number of shuttles you have to board along the way, or -1 if the destination cannot be reached.

Example 1

loops=[[4, 9, 2], [9, 11], [11, 30, 7]], start=4, finish=7 → 3

Ride shuttle 0 to stop 9, change to shuttle 1 for stop 11, then shuttle 2 reaches 7: three boardings.

Example 2

loops=[[1, 3], [5, 8]], start=3, finish=8 → -1

The loops share no stop, so stop 8 cannot be reached from stop 3.

Example 3

loops=[[6, 2]], start=5, finish=5 → 0

We are already at the destination, so no boarding is needed.

Constraints

1 ≤ len(loops) ≤ 5000
1 ≤ len(loops[i]) ≤ 10⁵, and no stop repeats within one loop
The total length of all loops is at most 10⁵
0 ≤ loops[i][j] < 10⁶
0 ≤ start, finish < 10⁶

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Breadth-First Search Array Hash Table

Similar problems

One-Swap Word Families Hard Which Machine to Cure Hard Which Machine to Unplug Hard Escape the Huge Grid Hard Turn Every Lamp Off Hard

Input

loops=[[4, 9, 2], [9, 11], [11, 30, 7]], start=4, finish=7

Expected

Run checks the first 3 tests in your browser. Submit checks all 80 tests on the server, hidden ones included.