> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Number of Ways to Arrive at Destination

> Tested Python solution for LeetCode 1976 with 17 pytest cases. Generate a practice environment with lcpy.

LeetCode 1976, [Medium](/catalog/medium). Topics: [Dynamic Programming](/catalog/topics/dynamic-programming), [Graph Theory](/catalog/topics/graph-theory), [Topological Sort](/catalog/topics/topological-sort), [Shortest Path](/catalog/topics/shortest-path), Dijkstra's Algorithm. [View on LeetCode](https://leetcode.com/problems/number-of-ways-to-arrive-at-destination/description/).

Generate this problem as a practice environment: tested reference solution, 17 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 1976   # by problem number
lcpy gen -s number_of_ways_to_arrive_at_destination   # by problem name
```

## Problem

You are in a city that consists of `n` intersections numbered from `0` to `n - 1` with **bi-directional** roads between some intersections. The inputs are generated such that you can reach any intersection from any other intersection and that there is at most one road between any two intersections.

You are given an integer `n` and a 2D integer array `roads` where `roads[i] = [u<sub>i</sub>, v<sub>i</sub>, time<sub>i</sub>]` means that there is a road between intersections `u<sub>i</sub>` and `v<sub>i</sub>` that takes `time<sub>i</sub>` minutes to travel. You want to know in how many ways you can travel from intersection `0` to intersection `n - 1` in the **shortest amount of time**.

Return *the **number of ways** you can arrive at your destination in the **shortest amount of time***. Since the answer may be large, return it **modulo** `10<sup>9</sup> + 7`.

### Examples

![Example 1](https://assets.leetcode.com/uploads/2025/02/14/1976_corrected.png)

```
Input: n = 7, roads = [[0,6,7],[0,1,2],[1,2,3],[1,3,3],[6,3,3],[3,5,1],[6,5,1],[2,5,1],[0,4,5],[4,6,2]]
Output: 4
Explanation: The shortest amount of time it takes to go from intersection 0 to intersection 6 is 7 minutes.
The four ways to get there in 7 minutes are:
- 0 ➝ 6
- 0 ➝ 4 ➝ 6
- 0 ➝ 1 ➝ 2 ➝ 5 ➝ 6
- 0 ➝ 1 ➝ 3 ➝ 5 ➝ 6
```

```
Input: n = 2, roads = [[1,0,10]]
Output: 1
Explanation: There is only one way to go from intersection 0 to intersection 1, and it takes 10 minutes.
```

### Constraints

* 1 \<= n \<= 200
* n - 1 \<= roads.length \<= n \* (n - 1) / 2
* roads\[i].length == 3
* 0 \<= u\<sub>i\</sub>, v\<sub>i\</sub> \<= n - 1
* 1 \<= time\<sub>i\</sub> \<= 10\<sup>9\</sup>
* u\<sub>i\</sub> != v\<sub>i\</sub>
* There is at most one road connecting any two intersections.
* You can reach any intersection from any other intersection.

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/number_of_ways_to_arrive_at_destination/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/number_of_ways_to_arrive_at_destination/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
import heapq


class Solution:
    # Time: O((n + m) log n) where m = len(roads)
    # Space: O(n + m)
    def count_paths(self, n: int, roads: list[list[int]]) -> int:
        mod = 1_000_000_007
        adj: list[list[tuple[int, int]]] = [[] for _ in range(n)]
        for u, v, t in roads:
            adj[u].append((v, t))
            adj[v].append((u, t))

        # max path cost is n * max(time) <= 200 * 10^9, far below the sentinel
        inf = 1 << 62
        dist = [inf] * n
        ways = [0] * n
        dist[0] = 0
        ways[0] = 1
        heap: list[tuple[int, int]] = [(0, 0)]
        while heap:
            d, node = heapq.heappop(heap)
            if d > dist[node]:
                continue
            for nxt, t in adj[node]:
                nd = d + t
                if nd < dist[nxt]:
                    dist[nxt] = nd
                    ways[nxt] = ways[node]
                    heapq.heappush(heap, (nd, nxt))
                elif nd == dist[nxt]:
                    ways[nxt] = (ways[nxt] + ways[node]) % mod
        return ways[n - 1]
```

## Complexity

| Time | Space |
| - | - |
| O((n + m) log n) where m = len(roads) | O(n + m) |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.