C++ | Djikstra + DFS + Memoization | Recursive and Iterative Solutions
Method 1 - Djikstra + Recursive DFS \n\n#define MOD 1000000007\nclass Solution\n{\n    public:\n    int dfs(unordered_map<int,vector<pair<int,int>>>& graph, int
Method 1 - Djikstra + Recursive DFS \n```\n#define MOD 1000000007\nclass Solution\n{\n    public:\n    int dfs(unordered_map<int,vector<pair<int,int>>>& graph, int u, int n, vector<long long int>& distance, vector<int>& paths)\n    {\n        if(paths[u]==-1)\n        {\n            paths[u]=0;\n            for(auto p:graph[u])\n            {\n                int v=p.first,w=p.second;\n                if(distance[v]<distance[u])\n                    paths[u]=(paths[u]+dfs(graph,v,n,distance,paths))%MOD;\n            }\n        }\n        return paths[u];\n    }\n    void djikstra(unordered_map<int,vector<pair<int,int>>>& graph, int start, vector<long long int>& distance)\n    {\n        priority_queue<pair<long long int,int>,vector<pair<long long int,int>>,greater<pair<long long int,int>>>pq;\n        \n        pq.push({0,start});\n        distance[start]=0;\n        \n        while(!pq.empty())\n        {\n            long long int du=pq.top().first;\n            int u=pq.top().second;\n            pq.pop();\n            \n            for(auto p:graph[u])\n            {\n                int v=p.first,dv=p.second;\n                long long int dist=distance[u]+dv;\n                if(dist<distance[v])\n                {\n                    distance[v]=dist;\n                    pq.push({distance[v],v});\n                }\n            }\n        }\n    }\n    int countRestrictedPaths(int n, vector<vector<int>>& edges)\n    {\n        unordered_map<int,vector<pair<int,int>>>graph;\n        \n        for(auto edge:edges)\n        {\n            graph[edge[0]].push_back({edge[1],edge[2]});\n            graph[edge[1]].push_back({edge[0],edge[2]});\n        }\n        \n        vector<long long int>distance(n+1,LLONG_MAX);\n        djikstra(graph,n,distance);\n\n        vector<int>paths(n+1,-1);\n        paths[n]=1;\n        dfs(graph,1,n,distance,paths);\n        \n        return paths[1];\n    }\n};\n```\nMethod 2 - Djikstra + Iterative DFS\n```\n#define MOD 1000000007\nclass Solution\n{\n    public:\n    void dfs(unordered_map<int,vector<pair<int,int>>>& graph, int start, int n, vector<long long int>& distance, vector<int>& paths)\n    {\n        stack<int>st;\n        st.push(start);\n        vector<int>visited(n+1,0);\n        \n        while(!st.empty())\n        {\n            int u=st.top();\n            if(visited[u]==0)\n            {\n                visited[u]=1;\n                for(auto p:graph[u])\n                {\n                    int v=p.first,w=p.second;\n                    if(distance[v]<distance[u])\n                        st.push(v);\n                }\n            }\n            else if(visited[u]==1)\n            {\n                visited[u]=2;\n                st.pop();\n                if(paths[u]==-1)\n                {\n                    paths[u]=0;\n                    for(auto p:graph[u])\n                    {\n                        int v=p.first,w=p.second;\n                        if(distance[v]<distance[u])\n                            paths[u]=(paths[u]+paths[v])%MOD;\n                    }\n                }\n            }\n            else\n                st.pop();\n        }\n    }\n    void djikstra(unordered_map<int,vector<pair<int,int>>>& graph, int start, vector<long long int>& distance)\n    {\n        priority_queue<pair<long long int,int>,vector<pair<long long int,int>>,greater<pair<long long int,int>>>pq;\n        \n        pq.push({0,start});\n        distance[start]=0;\n        \n        while(!pq.empty())\n        {\n            long long int du=pq.top().first;\n            int u=pq.top().second;\n            pq.pop();\n            \n            for(auto p:graph[u])\n            {\n                int v=p.first,dv=p.second;\n                long long int dist=distance[u]+dv;\n                if(dist<distance[v])\n                {\n                    distance[v]=dist;\n                    pq.push({distance[v],v});\n                }\n            }\n        }\n    }\n    int countRestrictedPaths(int n, vector<vector<int>>& edges)\n    {\n        unordered_map<int,vector<pair<int,int>>>graph;\n        \n        for(auto edge:edges)\n        {\n            graph[edge[0]].push_back({edge[1],edge[2]});\n            graph[edge[1]].push_back({edge[0],edge[2]});\n        }\n        \n        vector<long long int>distance(n+1,LLONG_MAX);\n        djikstra(graph,n,distance);\n\n        vector<int>paths(n+1,-1);\n        paths[n]=1;\n        dfs(graph,1,n,distance,paths);\n        \n        return paths[1];\n    }\n};\n```
['Depth-First Search', 'Memoization']