Simple dijkstra's/dfs with dp
cpp\nclass Solution {\npublic:\n    void dijkstra(vector<vector<pair<int, int>>> &adj, vector<int> &dists) {\n        vector<bool> seen(adj.size(), false);\n   
```cpp\nclass Solution {\npublic:\n    void dijkstra(vector<vector<pair<int, int>>> &adj, vector<int> &dists) {\n        vector<bool> seen(adj.size(), false);\n        auto comp = [&dists](int a, int b) {return dists[a]>dists[b];};\n        priority_queue<int, vector<int>, decltype(comp)> pq(comp);\n        pq.push(adj.size()-1);\n        dists[adj.size()-1] = 0;\n        while (!pq.empty()) {\n            int a = pq.top();\n            pq.pop();\n            for (auto [b, w] : adj[a]) {\n                if (dists[b] > dists[a]+w) {\n                    dists[b] = dists[a] + w;\n                    pq.push(b);\n                }\n            }\n        }\n    }\n    \n    int dfs(vector<vector<pair<int, int>>> &adj, vector<int> &dists, int a, vector<bool> &seen, vector<int> &dp) {\n        if (seen[a]) return 0;\n        if (dp[a]) return dp[a];\n        seen[a] = true;\n        int res = 0;\n        for (auto [b, w] : adj[a]) {\n            if (dists[b]>=dists[a]||dists[a]==0) continue;\n            else if (b == adj.size()-1) {\n                ++res;\n            } else {\n                res = (res + dfs(adj, dists, b, seen,dp))%((int)1e9+7);\n            }\n        }\n        seen[a] = false;\n        return dp[a] = res;\n    } \n    \n    int countRestrictedPaths(int n, vector<vector<int>>& edges) {\n        vector<vector<pair<int, int>>> adj(n+1);\n        for (auto &i : edges) {\n            int a = i[0], b = i[1], w = i[2];\n            adj[a].emplace_back(b,w);\n            adj[b].emplace_back(a, w);\n        }\n        \n        vector<int> dists(n+1, INT_MAX);\n        dijkstra(adj, dists);\n        \n        vector<bool> seen(n+1, false);\n        vector<int> dp(n+1, 0);\n        return dfs(adj, dists, 1, seen,dp);\n    }\n};\n```
['Dynamic Programming', 'C']