C++ Dijkstra + DP Solution
Runtime: 664 ms, faster than 26.59% of C++ online submissions for Number of Restricted Paths From First to Last Node.\nMemory Usage: 199 MB, less than 8.35% of 
Runtime: 664 ms, faster than 26.59% of C++ online submissions for Number of Restricted Paths From First to Last Node.\nMemory Usage: 199 MB, less than 8.35% of C++ online submissions for Number of Restricted Paths From First to Last Node.\n\nNote : Solution taken from other post.\n\n```\nHere we have to find the restricted paths count from source 1 to destination N. Now restricted path is such\nthat dist[j] > dist[j+1] and dist[x] is the shortest distance from node N and node x. So, we need to start \nDijkstra Algo from node N to node 1 to find the shortest distance of the nodes. Now in restricted path \nedge [u-to-v] can be restricted if dist[u] > dist[v] and so we can find the path ways of higher distance node\nfrom the lower distance node using DP as ways[u] += ways[v]. And initlially node N will have ways 1. \nIn Dijkstra Algo we go from lower distance to higher distance and so as we go to higher distance node u\nwe check the neighbor nodes which has lower distance and that neighbor v can make a restricted path\nand the higher distance node restricted path count comes from the lower distance node restricted path count.\n```\n\n```\nclass Solution {\npublic:\n    int countRestrictedPaths(int n, vector<vector<int>>& edges) {\n        \n        // Adj List and distance vector of nodes\n        vector<vector<vector<int>>>adjL(n);\n        vector<long>dist(n,LONG_MAX);\n        \n        // populate Adj List\n        for(int i=0;i<edges.size();i++)\n        {\n            adjL[edges[i][0]-1].push_back({edges[i][1]-1,edges[i][2]});\n            adjL[edges[i][1]-1].push_back({edges[i][0]-1,edges[i][2]});\n        }\n        \n        int MOD = 1000000007;\n        \n        // push node N in PQ and make node N distance 0\n        priority_queue<pair<long,int>,vector<pair<long,int>>,greater<>>pQ;\n        pQ.push({0,n-1});\n        dist[n-1] = 0;\n\n        // store restrited path count of nodes and node N has count 1 initially\n        vector<long>ways(n,0);\n        ways[n-1]=1;\n        \n        long cost;\n        int node;\n\n        // loop through PQ nodes and relax the neighbor nodes\n        // if dist[node] > dist[neighbor] then there is restricted edge and so\n        // we update node way count from neighbor way count as ways[node] += ways[neighbor]\n        // Also we update ways of node from neighbor cause in Dijkstra we move from lower to higher distance\n        // thus higher distance node way count depends on lower distance node ways count and also we\n        // start from node N which has dist 0 and ways 1\n        while(!pQ.empty())\n        {\n            cost = pQ.top().first;\n            node = pQ.top().second;\n            pQ.pop();\n            \n            if(dist[node]<cost)continue;\n            for(auto &adj: adjL[node])\n            {                \n                if(dist[node]+adj[1] < dist[adj[0]])\n                {\n                    dist[adj[0]] = dist[node]+adj[1];\n                    pQ.push({dist[adj[0]],adj[0]});\n                }\n                \n                // update node ways count as we find the restricted edge\n                if(dist[node] > dist[adj[0]])ways[node] = (ways[adj[0]] + ways[node])%MOD;\n            }\n        }\n\n        // return the restricted path count of node 0\n        return ways[0];\n    }\n};\n```
['Dynamic Programming', 'Graph', 'C']