[Python3] Dijkstra + dp
\n\nclass Solution:\n    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n        graph = {} # graph as adjacency list \n        for u, v
\n```\nclass Solution:\n    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n        graph = {} # graph as adjacency list \n        for u, v, w in edges: \n            graph.setdefault(u, []).append((v, w))\n            graph.setdefault(v, []).append((u, w))\n        \n        queue = [n]\n        dist = {n: 0}\n        while queue: \n            newq = []\n            for u in queue: \n                for v, w in graph[u]:\n                    if v not in dist or dist[u] + w < dist[v]: \n                        dist[v] = dist[u] + w\n                        newq.append(v)\n            queue = newq\n        \n        @cache\n        def fn(u): \n            """Return number of restricted paths from u to n."""\n            if u == n: return 1 # boundary condition \n            ans = 0\n            for v, _ in graph[u]: \n                if dist[u] > dist[v]: ans += fn(v)\n            return ans \n        \n        return fn(1) % 1_000_000_007\n```\n\nEdited on 3/7/2021\nAdding the implemetation via Dijkstra\'s algo\n```\nclass Solution:\n    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n        graph = {} # graph as adjacency list \n        for u, v, w in edges: \n            graph.setdefault(u-1, []).append((v-1, w))\n            graph.setdefault(v-1, []).append((u-1, w))\n        \n        # dijkstra\'s algo\n        pq = [(0, n-1)]\n        dist = [inf]*(n-1) + [0]\n        while pq: \n            d, u = heappop(pq)\n            for v, w in graph[u]: \n                if dist[u] + w < dist[v]: \n                    dist[v] = dist[u] + w\n                    heappush(pq, (dist[v], v))\n        \n        @cache\n        def fn(u): \n            """Return number of restricted paths from u to n."""\n            if u == n-1: return 1 # boundary condition \n            ans = 0\n            for v, _ in graph[u]: \n                if dist[u] > dist[v]: ans += fn(v)\n            return ans \n        \n        return fn(0) % 1_000_000_007\n```
['Python3']