Dijkstra + DFS with DP || C++ || explained
First find the minimum distance to each node from the last node. Using dijkstra algorithm\n- Using DFS go to each path and check if dist[adjnode] < dist[node]\n
- First find the minimum distance to each node from the last node. Using dijkstra algorithm\n- Using DFS go to each path and check if ```dist[adjnode] < dist[node]```\n# Code\n```\nclass Solution {\npublic:\n    int mod = 1e9 + 7;\n    vector<int> dijkstra(int n, vector<vector<pair<int,int>>> &adj){\n        vector<int> dist(n+1, INT_MAX);\n        priority_queue<pair<int,int>, vector<pair<int, int>>, greater<pair<int,int>>> pq;\n        dist[n] = 0;\n        pq.push({0, n});\n\n        while(!pq.empty()){\n            int node = pq.top().second;\n            int d = pq.top().first;\n            pq.pop();\n\n            for(auto it: adj[node]){\n                int adjnode = it.first;\n                int wt = it.second;\n                if(d + wt < dist[adjnode]){\n                    dist[adjnode] = d + wt;\n                    pq.push({dist[adjnode], adjnode});\n                }\n            }\n        }\n        return dist;\n    }\n\n    int dfs(int node, vector<vector<pair<int,int>>> &adj, int n, vector<bool> &vis, vector<int> &dist, vector<int> &dp){\n        if(node == n){\n            return 1;\n        }\n\n        if(dp[node] != -1){\n            return dp[node];\n        }\n\n        vis[node] = 1;\n\n        int ans = 0;\n        for(auto it : adj[node]){\n            int adjnode = it.first;\n            if(!vis[adjnode] && dist[adjnode] < dist[node]){\n                ans = ans%mod + dfs(adjnode, adj, n, vis, dist, dp)%mod;\n            }\n        }\n\n        vis[node] = 0;\n        return dp[node] = ans%mod;\n    }\n\n    int countRestrictedPaths(int n, vector<vector<int>>& edges) {\n        vector<vector<pair<int,int>>> adj(n+1);\n        for(auto it: edges){\n            adj[it[0]].push_back({it[1],it[2]});\n            adj[it[1]].push_back({it[0],it[2]});\n        }\n\n        vector<int> dist = dijkstra(n, adj);\n        vector<bool> pathvis(n+1, 0);\n        vector<int> dp(n+1, -1);\n\n        return dfs(1, adj, n, pathvis, dist, dp);\n    }\n};\n```
['Dynamic Programming', 'Depth-First Search', 'Graph', 'Shortest Path', 'C++']