1976.Number_of_Ways_to_Arrive_at_Destination(Medium).md

1976. Number of Ways to Arrive at Destination (Medium)

Date and Time: Mar 24, 2025

Link: https://leetcode.com/problems/number-of-ways-to-arrive-at-destination

Edge Cases:

Edge Case 1:

Input: n = 1, roads = []
Output: 1
Explanation: There is one way to get node 0

Walk-through:

1. Build the undirected graph

2. Run Dijkstra to find the shortest path with a list for dist (keep track of the time to reach each node), path_cnt for how many path to reach a node.

Relaxation: If current time + neighbor's time less than the current time we have on dist[], we update the time and the number of path to reach this node to dist[node] (current node we at). If the new time equals to the time we have already, update the path_cnt[nei] with current counts and the prev node's count, so we can update how many ways we can reach at the destination with the same shortest time.

Python Solution:

class Solution:
    def countPaths(self, n: int, roads: List[List[int]]) -> int:
        # Run Dijkstra to find shortest time with path[] and dist[]
        # Use minHeap to process, if new time + nei_time < dist[node]: update time and update to be path[node]
        # If time is equal, update path[node] += path[nei]

        # TC: O((E+V)logV), E is total edges, V is total vertices, SC: O(V)
        graph = collections.defaultdict(list)
        # Build graph
        for u, v, t in roads:
            graph[u].append((v, t))
            graph[v].append((u, t))
        # Run Dijkstra
        minHeap = [[0, 0]]      # [time, node]
        path = [1] + [0] * (n-1)
        dist = [0] + [float("inf")] * (n-1)
        while minHeap:
            curr_t, node = heapq.heappop(minHeap)
            # Relaxation
            for nei, t in graph[node]:
                if t + curr_t < dist[nei]:
                    dist[nei] = t + curr_t
                    heapq.heappush(minHeap, [dist[nei], nei])
                    path[nei] = path[node]
                elif t + curr_t == dist[nei]:
                    path[nei] = (path[nei] + path[node]) % (10**9 + 7)
        return path[n-1]

Time Complexity: $O((E+V)log(V))$
Space Complexity: $O(V)$