DijKstra + DP in C++
\n#define pii pair<long,int>\n# define mod 1000000007\nclass Solution {\npublic:\n    \n    long DFS(int x, int n,vector<long>&dp , vector<long>&dis,  vector<pa
```\n#define pii pair<long,int>\n# define mod 1000000007\nclass Solution {\npublic:\n    \n    long DFS(int x, int n,vector<long>&dp , vector<long>&dis,  vector<pair<int,long>>*g){\n        if(x==n)\n            return 1;\n        else if(dp[x]!=-1)\n            return dp[x];\n        long ans =0;\n        for(int i=0;i<g[x].size();i++){\n            int v = g[x][i].first;\n            if( dis[x]>dis[v]){\n               ans  = (ans+ DFS(v,n, dp, dis, g))%mod;\n            }\n        }\n        dp[x] = ans;\n        return ans;\n    }\n    int countRestrictedPaths(int n, vector<vector<int>>& edges) {\n        vector<long>dis(n+1, INT_MAX);\n        vector<pair<int,long>>g[n+1];\n        for(int i=0;i<edges.size();i++){\n            g[edges[i][0]].push_back({edges[i][1],edges[i][2]});\n             g[edges[i][1]].push_back({edges[i][0],edges[i][2]});\n        }\n        priority_queue<pii,vector<pii>, greater<pii>>pq;\n        pq.push({0,n});\n        dis[n]=0;\n        while(!pq.empty()){\n            pii temp = pq.top();\n            pq.pop();\n            int u = temp.second;\n            for(int i =0;i<g[u].size();i++){\n                int v = g[u][i].first;\n                long wt = g[u][i].second;\n                if(dis[u]+wt<dis[v]){\n                    dis[v]=wt+dis[u];\n                    pq.push({dis[v],v});\n                }\n            }\n        }\n\n        vector<long>dp(n+1,-1);\n        return DFS(1,n,dp,dis,g);\n    }\n};\n```
[]