0781MediumBreadth-First SearchGraph Theory

Alternating Road And Rail Legs

Tracked in this browser only

Trains the technique from

LeetCode 1129Shortest Path with Alternating Colors

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a 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)

The intended approach

Time O(n + E) for E legs in total: each of the 2n states leaves the queue once and each leg is read once from each state that owns it.Space O(n + E) for the two adjacency lists, the state counts and the queue.

Search over pairs of (depot, which network the arriving leg used) rather than over depots alone, because how you arrived decides what you may take next. Seed both pairs for depot `0` with zero legs so the route can open with either network, then run a breadth-first search that only ever leaves a pair by the other network. Each depot's answer is the smaller of its two settled counts, and `-1` when neither was reached.

Pythonentry point: shortest_alternating_paths

def shortest_alternating_paths(n, roadLegs, railLegs):
    # Breadth-first search over states (depot, mode of the leg that arrived here).
    # Both states of depot 0 start at zero legs, which lets the first leg be either
    # mode, and every state is settled once because the search widens by one leg at
    # a time. Time O(n + E), space O(n + E).
    road = [[] for _ in range(n)]
    rail = [[] for _ in range(n)]
    for a, b in roadLegs:
        road[a].append(b)
    for a, b in railLegs:
        rail[a].append(b)

    legs = [[-1, -1] for _ in range(n)]
    legs[0][0] = 0
    legs[0][1] = 0
    queue = [(0, 0), (0, 1)]
    seat = 0
    while seat < len(queue):
        depot, mode = queue[seat]
        seat += 1
        nxt = 1 - mode
        for to in (rail[depot] if nxt else road[depot]):
            if legs[to][nxt] == -1:
                legs[to][nxt] = legs[depot][mode] + 1
                queue.append((to, nxt))

    out = []
    for v in range(n):
        by_road, by_rail = legs[v][0], legs[v][1]
        if by_road == -1:
            out.append(by_rail)
        elif by_rail == -1:
            out.append(by_road)
        else:
            out.append(by_road if by_road < by_rail else by_rail)
    return out

The obvious version

Keep a best-known leg count for every (depot, arriving network) pair and sweep the whole leg list over and over, improving a pair whenever a leg of the other network reaches it more cheaply, until a full sweep changes nothing.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_shortest_alternating_paths(n, roadLegs, railLegs):
    BIG = 10 ** 9
    best = [[BIG, BIG] for _ in range(n)]
    best[0][0] = 0
    best[0][1] = 0
    moved = True
    while moved:
        moved = False
        for a, b in roadLegs:
            if best[a][1] < BIG and best[a][1] + 1 < best[b][0]:
                best[b][0] = best[a][1] + 1
                moved = True
        for a, b in railLegs:
            if best[a][0] < BIG and best[a][0] + 1 < best[b][1]:
                best[b][1] = best[a][0] + 1
                moved = True
    out = []
    for v in range(n):
        low = min(best[v])
        out.append(-1 if low >= BIG else low)
    return out

How this problem was checked

Reference solution executed against 12 test cases — 12 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in