LC-1786 Medium LeetCode

1786. Number of Restricted Paths From First to Last Node

Dynamic Programming Graph Topological Sort Heap (Priority Queue) Shortest Path

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 40% Topics: Dynamic Programming, Graph, Topological Sort, Heap (Priority Queue), Shortest Path

View full problem on LeetCode

Reading material

1-D Dynamic Programming 16 min Graphs 16 min Heaps & Priority Queues 13 min

Reference solution (spoiler · python)

# Time:  O(|E| * log|V|)
# Space: O(|E| + |V|)

import heapq


class Solution(object):
    def countRestrictedPaths(self, n, edges):
        """
        :type n: int
        :type edges: List[List[int]]
        :rtype: int
        """
        MOD = 10**9+7
        adj = [[] for _ in xrange(n)]
        for u, v, w in edges:
            adj[u-1].append((v-1, w))
            adj[v-1].append((u-1, w))
        dist = [float("inf")]*n
        dp = [0]*n
        dist[n-1] = 0
        dp[n-1] = 1
        min_heap = [(0, n-1)]
        while min_heap:
            w, u = heapq.heappop(min_heap)
            if w > dist[u]:
                continue
            for v, d in adj[u]:
                if w+d < dist[v]:
                    dist[v] = w+d
                    heapq.heappush(min_heap, (dist[v], v))
                elif w > dist[v]:
                    dp[u] = (dp[u]+dp[v])%MOD
            if u == 0:  # early return
                break
        return dp[0]

Solution from kamyu104/LeetCode-Solutions · MIT