1086MediumDynamic ProgrammingGraph TheoryTopological SortShortest PathDijkstra's Algorithm

Counting the Quickest Courier Routes

Tracked in this browser only

Trains the technique from

LeetCode 1976Number of Ways to Arrive at Destination

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 city has n junctions numbered 0 through n - 1, joined by two-way lanes. lanes[i] = [a, b, minutes] means a lane runs between junction a and junction b and takes minutes to ride in either direction.

At most one lane joins any pair of junctions, and every junction can be reached from every other one.

A courier sets off from junction 0 bound for junction n - 1 and will only ride a route whose total time is the smallest possible. Report how many such routes there are, reduced modulo 10^9 + 7 because the tally outgrows any fixed-width integer.

Examples

Example 1

Input: n = 4, lanes = [[0, 3, 5], [0, 1, 1], [1, 3, 1], [0, 2, 1], [2, 3, 1]]
Output: 2

The single lane straight to junction 3 takes 5 minutes. Hopping through junction 1 takes 2 minutes and so does hopping through junction 2, and those two are the only quickest routes.

Example 2

Input: n = 2, lanes = [[1, 0, 7]]
Output: 1

One lane joins the two junctions and it can be ridden either way, so there is a single route.

Example 3

Input: n = 6, lanes = [[0, 1, 1], [1, 2, 1], [2, 5, 1], [0, 3, 1], [3, 4, 1], [4, 5, 1], [0, 5, 3]]
Output: 3

Three minutes is the least possible: the direct lane, the chain through junctions 1 and 2, and the chain through junctions 3 and 4.

Constraints

1 <= n <= 200
n - 1 <= lanes.length <= n * (n - 1) / 2
lanes[i].length == 3
0 <= lanes[i][0] <= n - 1
0 <= lanes[i][1] <= n - 1
1 <= lanes[i][2] <= 10^9
the two junctions on a lane are never the same
at most one lane joins any pair of junctions
every junction can be reached from every other junction

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 count_paths(n: int, lanes: list[list[int]]) -> int:

Java

public int countPaths(int n, int[][] lanes)

The intended approach

Time O(m log n) for the search over m lanes.Space O(n + m) for the lane lists and the two arrays.

Carry a tally alongside the usual shortest-time search. Beside each junction keep two numbers: the best time known to reach it and how many quickest routes achieve that time. Settle junctions in order of increasing best time, always taking the unsettled junction with the smallest known time. When a junction is settled its time is final, so its tally is final too, and it can be handed on. For each lane leaving a settled junction, work out the arrival time at the far end. A strictly better time throws the old tally away and copies the settled junction's tally instead. An equal time means a second, separate family of quickest routes arrives, so the two tallies add. Because every lane costs at least one minute, an already settled junction can never be reached again in exactly its own best time, so no tally is ever added twice. Reduce the tallies as they grow, since they outrun any fixed-width integer long before the junction count does. The answer is the tally on the last junction, which starts at one for junction zero: the empty route.

Pythonentry point: count_paths

def count_paths(n, lanes):
    import heapq
    mod = 1000000007
    adj = [[] for _ in range(n)]
    for lane in lanes:
        adj[lane[0]].append((lane[1], lane[2]))
        adj[lane[1]].append((lane[0], lane[2]))
    inf = 1 << 62
    dist = [inf] * n
    ways = [0] * n
    done = [False] * n
    dist[0] = 0
    ways[0] = 1
    heap = [(0, 0)]
    while heap:
        d, node = heapq.heappop(heap)
        if done[node]:
            continue
        done[node] = True
        for nb, cost in adj[node]:
            step = d + cost
            if step < dist[nb]:
                dist[nb] = step
                ways[nb] = ways[node]
                heapq.heappush(heap, (step, nb))
            elif step == dist[nb]:
                ways[nb] = (ways[nb] + ways[node]) % mod
    return ways[n - 1] % mod

The obvious version

Walk out every route that never repeats a junction, since with positive lane times a quickest route can never revisit one. Keep the smallest total seen and how many routes hit it, pruning a walk the moment its running total passes the best already found. The number of such routes grows factorially, so this only survives a handful of junctions.

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_count_paths(n, lanes):
    mod = 1000000007
    adj = [[] for _ in range(n)]
    for lane in lanes:
        adj[lane[0]].append((lane[1], lane[2]))
        adj[lane[1]].append((lane[0], lane[2]))
    state = {"best": None, "count": 0}
    seen = [False] * n

    def walk(node, total):
        if state["best"] is not None and total > state["best"]:
            return
        if node == n - 1:
            if state["best"] is None or total < state["best"]:
                state["best"] = total
                state["count"] = 1
            elif total == state["best"]:
                state["count"] += 1
            return
        for nb, cost in adj[node]:
            if not seen[nb]:
                seen[nb] = True
                walk(nb, total + cost)
                seen[nb] = False

    seen[0] = True
    walk(0, 0)
    return state["count"] % mod

How this problem was checked

Reference solution executed against 15 test cases — 15 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