Dijkstra's | DP | DFS
Code


# Code
```cpp []
class Solution {
public:

    const int mod = 1e9 + 7;

    vector<int> smallest(vector<vector<pair<int,int>>> &adj, int n, int src){
        // distance node
        priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>> > pq;
        vector<int> dist(n+1,INT_MAX);

        dist[src] = 0;
        pq.push({0,src});

        while(!pq.empty()){
            int w = pq.top().first, u = pq.top().second;
            pq.pop();

            for(auto it : adj[u]){
                int v = it.first, wt = it.second;
                int cost = wt + w;
                if(dist[v] > cost){
                    dist[v] = cost;
                    pq.push({cost,v});
                }
            }
        }

        return dist;
    }

    int dfs(int node, int n, vector<vector<pair<int,int>>> &adj,vector<int> &dist,vector<int> &dp){
        if(node == n) return 1;
        if(dp[node] != -1) return dp[node];

        int count = 0;
        for(auto it : adj[node]){
            int v = it.first, w = it.second;
            if(dist[node] > dist[v] ){
                count = (count + dfs(v,n,adj,dist,dp))%mod;
            }
        }

        return dp[node] = count;
    }

    int countRestrictedPaths(int n, vector<vector<int>>& edges) {
        vector<vector<pair<int,int>>> adj(n+1);
        for(auto it : edges){
            int u = it[0], v = it[1], wt = it[2];
            adj[u].push_back({v,wt});
            adj[v].push_back({u,wt});
        }

        vector<int> dist = smallest(adj,n,n);
        vector<int> dp(n+1,-1);

        int ans = dfs(1,n,adj,dist,dp);
        return ans;
        
    }
};
```
['C++']