C++ implementation: Dijkstra + dfs with memorization
The algo is divided in two parts:\n1. Finding path using Dikstra algorithm: shortest path from last node (n) to all other nodes.\n2. Applying dfs to find the re
The algo is divided in two parts:\n1. Finding path using Dikstra algorithm: shortest path from last node (n) to all other nodes.\n2. Applying dfs to find the restricted path: our task property mentioned in the description.\n\n```\nclass Solution {\npublic:\n    using ip = pair<int, int>;\n    const int mod = 1e9 + 7;\n\n    int dfs(vector<vector<ip>>& adj, vector<int>& dist, int start, vector<int>& dp) {\n        if (start == 1) {\n            return 1;\n        }\n        \n        if (dp[start] != -1) {\n            return dp[start];\n        }\n        int count = 0;\n        \n        for (auto& [next, _] : adj[start]) {\n            if (dist[next] > dist[start]) {\n              count = (count + dfs(adj, dist, next, dp)) % mod;  \n            }\n        }\n        \n        dp[start] = count;\n        \n        return dp[start];\n    }\n    \n    int countRestrictedPaths(int n, vector<vector<int>>& edges) {\n        vector<vector<ip>> adj(n + 1, vector<ip>{});\n        \n        for (auto& e : edges) {\n            adj[e[0]].push_back({e[1], e[2]});\n            adj[e[1]].push_back({e[0], e[2]});\n        }\n        \n        priority_queue<ip, vector<ip>, greater<ip>> pq;\n        vector<int> dist(n + 1, INT_MAX);\n        \n        pq.push({0, n});\n        dist[n] = 0;\n        \n        while (!pq.empty()) {\n            auto [_, node] = pq.top(); pq.pop();\n            \n            for (auto & [next, w] : adj[node]) {\n                if (dist[next] > dist[node] + w) {\n                    dist[next] = dist[node] + w;\n                    pq.push({dist[next], next});\n                }\n            }\n        }\n        \n        vector<int> dp(n + 1, -1);\n        \n        return dfs(adj, dist, n, dp);\n    }\n};\n```
['Depth-First Search', 'Memoization', 'C']