Clean Python 3, Dijkstra and top-down dp
Use Dijkstra algorithm to find the shortest path from n.\nAnd use top-down dp to find all valid paths.\n\nTime: O(E + (V + E)logV + 2 * E) = O((V + E)logV)\nSpa
Use Dijkstra algorithm to find the shortest path from `n`.\nAnd use top-down dp to find all valid paths.\n\nTime: `O(E + (V + E)logV + 2 * E) = O((V + E)logV)`\nSpace: `O(E + V)`\n\n```\nimport collections\nimport functools\nimport heapq\nclass Solution:\n    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n        @functools.cache\n        def dfs(node: int) -> int:\n            if node == 1: return 1\n            result = 0\n            for nei in graph[node]:\n                if dist[nei] > dist[node]:\n                    result = (result + dfs(nei)) % mod\n            return result\n\n        graph = collections.defaultdict(dict)\n        for u, v, w in edges:\n            graph[u][v] = w\n            graph[v][u] = w\n        dist, heap, mod = {n: 0}, [(0, n)], 10**9 + 7\n        while heap:\n            shortest, node = heapq.heappop(heap)\n            if shortest != dist[node]: continue\n            for nei, w in graph[node].items():\n                if dist[node] + w < dist.get(nei, float(\'inf\')):\n                    dist[nei] = dist[node] + w\n                    heapq.heappush(heap, (dist[nei], nei))\n        return dfs(n)\n```
[]