Show problems as
Classic problem #1129MediumBreadth-First SearchGraph Theory

Shortest Path with Alternating Colors

Real-world version: Alternating Road And Rail Legs
Tracked in this browser only
Read Shortest Path with Alternating Colors on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A carrier moves pallets between n depots numbered 0 to n - 1 using two networks. roadLegs[i] = [a, b] is a one-way road leg that can take a pallet from depot a to depot b, and railLegs[j] = [u, v] is a one-way rail leg from depot u to depot v. The same leg may be listed more than once, and a leg may start and end at the same depot.

A pallet starts at depot 0. Its route must change network at every step: a road leg is never followed by another road leg, and a rail leg is never followed by another rail leg. The first leg of a route may be of either kind. A route may pass through the same depot more than once.

For every depot, work out the fewest legs on such a route from depot 0 to that depot, and return those counts in depot order. The count for depot 0 is 0, and a depot with no such route at all is reported as -1.

Examples

Example 1

Input
n = 6, roadLegs = [[0,1],[1,2],[2,3],[0,4]], railLegs = [[1,3],[3,4],[4,1]]
Output
[0, 1, 3, 2, 1, -1]

Depot 1 is one road leg away and depot 4 likewise. Depot 3 is reached by the road leg 0 to 1 followed by the rail leg 1 to 3. Depot 2 is reached by road 0 to 4, rail 4 to 1, road 1 to 2, which alternates the whole way. No leg of either network ends at depot 5.

Example 2

Input
n = 3, roadLegs = [], railLegs = [[0,1],[1,2]]
Output
[0, 1, -1]

The rail leg 0 to 1 gets a pallet to depot 1. Reaching depot 2 would mean taking the rail leg 1 to 2 straight after another rail leg, which the route rule forbids, and there are no road legs to break it up.

Example 3

Input
n = 2, roadLegs = [[0,0],[1,1]], railLegs = [[0,0]]
Output
[0, -1]

Every leg here starts and ends at the depot it already sits in, so depot 0 stays at 0 legs and nothing reaches depot 1.

Constraints

  • 1 <= n <= 100
  • 0 <= roadLegs.length <= 400
  • 0 <= railLegs.length <= 400
  • roadLegs[i].length == 2
  • railLegs[i].length == 2
  • Both endpoints of every leg are depot numbers, so they are at least 0 and below n.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def shortest_alternating_paths(n: int, roadLegs: list[list[int]], railLegs: list[list[int]]) -> list[int]:
Java
public int[] shortestAlternatingPaths(int n, int[][] roadLegs, int[][] railLegs)

More on the same topics