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. Topics: Dynamic Programming, Graph Theory, Topological Sort, Shortest Path, Dijkstra’s Algorithm. View on LeetCode.

Generate this problem as a practice environment: tested reference solution, 17 parametrized pytest cases, and a playground notebook:

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

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_i, v_i <= n - 1
• 1 <= time_i <= 10⁹
• u_i != v_i
• 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, full suite in test_solution.py:

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.