[Python3] Memoized Dijkstra + Memoized DFS Beats 100%
\nclass Solution:\n    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n        mod = 10 ** 9 + 7\n        dist = [float(\'inf\')] * (n +
```\nclass Solution:\n    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n        mod = 10 ** 9 + 7\n        dist = [float(\'inf\')] * (n + 1)\n        graph = defaultdict(list)\n        def dijkstra():\n            pq = [(0, n)]\n            dist[n] = 0\n            while pq:\n                weight, node = heappop(pq)\n                for next, nweight in graph[node]:\n                    if weight + nweight < dist[next]:\n                        dist[next] = weight + nweight\n                        heappush(pq, (dist[next], next))\n        @lru_cache(None)\n        def dfs(node):\n            if node == n:\n                return 1\n            total = 0\n            for next, weight in graph[node]:\n                if dist[node] > dist[next]:\n                    total = (total + dfs(next)) % mod\n            return total\n        for x, y, w in edges:\n            graph[x].append((y, w))\n            graph[y].append((x, w))\n        dijkstra()\n        res = dfs(1)\n        dfs.cache_clear()\n        return res\n```
[]