Python  Djikstra and count path along the way (no need dfs or dp)
Just run Djikstra and use a dictionary count to keep track of the number of restricted paths to any node. Note that if we reach node v from u, then it must be t
Just run Djikstra and use a dictionary `count` to keep track of the number of restricted paths to any node. Note that if we reach node `v` from `u`, then it must be the case that` d[u] <= d[v] `, and we only update `count[v]` if `d[u] < d[v]` \uFF08 think about why :-) )\n```\nclass Solution:\n    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n        d = {n: 0}\n        for i in range(1,n):\n            d[i] = math.inf\n        \n        nb = collections.defaultdict(list)\n\n        for u,v,w in edges:\n            nb[u].append((v,w))\n            nb[v].append((u,w))\n        \n        h = [(0,n)] # min heap\n        visited = set()\n        count = {n:1}\n        while(h):\n            _, u = heapq.heappop(h)\n            if u not in visited:\n                visited.add(u)\n                for v,w in nb[u]:\n                    if v not in visited:\n                        if d[v] > d[u]:\n                            count[v] = count.get(v,0) + count[u]\n                        if d[u] + w < d[v]:\n                            d[v] = d[u] + w\n                            heapq.heappush(h, (d[v], v))\n        return count[1]%(10**9+7)\n```
[]