c++ Djikstra and dfs
Please upvote if you find this useful\n\nDefinition of Restricted Paths : Path from source node(n) to target node(1) should have strictly increasing shortest di
**Please upvote if you find this useful**\n\nDefinition of Restricted Paths : Path from source node(n) to target node(1) should have strictly increasing shortest distance to source(n) for all nodes in path.\n\n- Idea is to calculate shortest distance from node n to all nodes and save it in dist array.\n- Then use dfs from source to all the nodes whose weight is greater than source node. \n- Return 1 if we have reached node 1 or return saved value for source if it\'s value is not -1(which means it\'s not visited yet)\n- Save the result for reuse later.\n- Return result. (this is the count of Restricted paths)\n\n```\ntypedef pair<int, int> pii;\nclass Solution {\npublic:\n    int countRestrictedPaths(int n, vector<vector<int>>& edges) {\n        unordered_map<int, vector<pair<int, int>>> gp;\n        for (auto& edge : edges) {\n            gp[edge[0]].push_back({edge[1], edge[2]});\n            gp[edge[1]].push_back({edge[0], edge[2]});\n        }\n        \n        vector<int> dist(n + 1, INT_MAX);\n        priority_queue<pii, vector<pii>, greater<pii> > pq;\n        pq.push({0, n});\n        dist[n] = 0;\n        \n\t\tint u, v, w;\n        while (!pq.empty()) {\n            pii p = pq.top(); pq.pop();\n            u = p.second;\n            for (auto& to : gp[u]) {\n                v = to.first, w = to.second;\n                if (dist[v] > dist[u] + w) {\n                    dist[v] = dist[u] + w;\n                    pq.push({dist[v], v});\n                }\n            }\n        }\n        vector<int> dp(n + 1, -1);\n        return dfs(gp, n, dp, dist);\n    }\n    \n    int dfs(unordered_map<int, vector<pair<int, int>>>& gp, int s, vector<int>& dp, vector<int>& dist) {\n        int mod = 1e9+7;\n        if (s == 1) return 1;\n        if (dp[s] != -1) return dp[s];\n        int sum = 0, weight, val;\n        for (auto& n : gp[s]) {\n            weight = dist[s];\n            val = dist[n.first];\n            if (val > weight) {\n                sum = (sum % mod + dfs(gp, n.first, dp, dist) % mod) % mod;\n            }\n        }\n        return dp[s] = sum % mod;\n    }\n};\n```\n
['C']