Dijkstra | DP | Memoized DFS | Optimal | C++
Time Complexity: O((E + V) log V)\nSpace Complexity: O(E + V)\n\ntypedef pair<int, int> pii;\nconst int MOD = 1e9 + 7;\nclass Solution {\n    vector<int> dijkst
**Time Complexity**: O((E + V) log V)\n**Space Complexity**: O(E + V)\n```\ntypedef pair<int, int> pii;\nconst int MOD = 1e9 + 7;\nclass Solution {\n    vector<int> dijkstra(const vector<vector<pii>>& adj, int src) {\n        vector<int> dist(src + 1, INT_MAX);\n \xA0 \xA0 \xA0 \xA0dist[src] = 0;\n        priority_queue<pii, vector<pii>, greater<pii>> minHeap;\n        minHeap.push({0, src});\n        while (!minHeap.empty()) {\n            auto [cost, vertex] = minHeap.top();\n            minHeap.pop();\n            if (cost > dist[vertex]) {\n                continue;\n            }\n            for (const auto& p : adj[vertex]) {\n                auto [weight, ngbr] = p;\n                if (dist[vertex] + weight < dist[ngbr]) {\n                    dist[ngbr] = dist[vertex] + weight;\n                    minHeap.push({dist[ngbr], ngbr});\n                }\n            }\n        }\n        return dist;\n    }\n    int dfs(const vector<vector<pii>>& adj, const vector<int>& v, vector<int>& dp, int node) {\n        if (node == 1) {\n            return 1;\n        }\n        if (dp[node] != -1) {\n            return dp[node];\n        }\n        int a = 0;\n        for (const auto& p : adj[node]) {\n            int ngbr = p.second;\n            if (v[node] < v[ngbr]) {\n                a = (a + dfs(adj, v, dp, ngbr)) % MOD;\n            }\n        }\n        return dp[node] = a;\n    }\npublic:\n    int countRestrictedPaths(int n, vector<vector<int>>& edges) {\n        vector<vector<pii>> adj(n + 1);\n        for (const auto& v : edges) {\n            adj[v[0]].push_back({v[2], v[1]});\n            adj[v[1]].push_back({v[2], v[0]});\n        }\n        auto v = dijkstra(adj, n);\n        vector<int> dp(n + 1, -1);\n        return dfs(adj, v, dp, n);\n    }\n};\n```
[]