[Python3] Dijkstra + Cache DFS ~ DP Top-down Memorization - Simple
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: $$O(V)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(V + E)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:\n        if n == 1: return 0\n        g = collections.defaultdict(list)\n        sum_w, mod = 0, 10 ** 9 + 7\n        for u, v, w in edges:\n            g[u].append((w, v))\n            g[v].append((w, u))\n            sum_w += w\n        \n        def dijkstra() -> List[int]:\n            pq = [(0, n)]\n            distance = [sum_w + 1 for _ in range(n + 1)]\n            distance[n] = 0\n            while pq:\n                w, u = heapq.heappop(pq)\n                for v_w, v in g[u]:\n                    if w + v_w < distance[v]:\n                        distance[v] = w + v_w\n                        heapq.heappush(pq, (w + v_w, v))\n            return distance\n        \n        @cache\n        def dfs(u: int) -> int:\n            if u == n: return 1\n            cnt = 0\n            for _, v in g[u]:\n                if distance[u] > distance[v]: cnt = (cnt + dfs(v)) % mod\n                    \n            return cnt\n        \n        distance = dijkstra()\n        return dfs(1)\n\n```
['Depth-First Search', 'Breadth-First Search', 'Shortest Path', 'Python3']