Number of Ways to Arrive at Destination

lcpy gen -n 1976   # by problem number
lcpy gen -s number_of_ways_to_arrive_at_destination   # by problem name

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.

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]