Show problems as
Classic problem #1976MediumDynamic ProgrammingGraph TheoryTopological SortShortest PathDijkstra's Algorithm

Number of Ways to Arrive at Destination

Real-world version: Counting the Quickest Courier Routes
Tracked in this browser only
Read Number of Ways to Arrive at Destination on LeetCode(opens in a new tab)

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

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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def count_paths(n: int, lanes: list[list[int]]) -> int:
Java
public int countPaths(int n, int[][] lanes)

More on the same topics