Number of Ways to Arrive at Destination

1976. Number of Ways to Arrive at Destination

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] = [ui, vi, timei] means that there is a road between intersections ui and vi that takes timei 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^9 + 7$.

Solution

Reference

1. We use Dijkstra algorithm to find the Shortest Path between src = 0 and dst = n - 1.

2. While dijkstra, we create ways array, let ways[i] denote the number of shortest path from src = 0 to dst = i. Then the answer is ways[n-1]

def countPaths(self, n: int, roads: List[List[int]]) -> int:
    graph = defaultdict(list)
    for u, v, time in roads:
        graph[u].append([v, time])
        graph[v].append([u, time])

    def dijkstra(src):
        dist = [math.inf] * n
        ways = [0] * n
        minHeap = [(0, src)]  # dist, src
        dist[src] = 0
        ways[src] = 1
        while minHeap:
            d, u = heappop(minHeap)
            if dist[u] < d: continue  # Skip if `d` is not updated to latest version!
            for v, time in graph[u]:
                if dist[v] > dist[u] + time:
                    dist[v] = dist[u] + time
                    ways[v] = ways[u]
                    heappush(minHeap, (dist[v], v))
                elif dist[v] == dist[u] + time:
                    ways[v] = (ways[v] + ways[u]) % 1_000_000_007
        return ways[n - 1]

    return dijkstra(0)