C++ | Djikstra + DFS + Memorization  |
\nclass Solution {\n    vector<vector<pair<int, int>>> graph;\n    vector<int> distance;\n    vector<int> memo;\n    int N;\n\n    // O(E)\n    int dfs(int u) {
```\nclass Solution {\n    vector<vector<pair<int, int>>> graph;\n    vector<int> distance;\n    vector<int> memo;\n    int N;\n\n    // O(E)\n    int dfs(int u) {\n        if (memo[u] != -1) return memo[u];\n        if (u == N) return 1;\n        int ans = 0;\n\n        for (auto e : graph[u]) {\n            int v = e.second;\n            if (distance[v] >= distance[u]) continue;\n            ans = (ans +  dfs(v)) % 1000000007;\n        }\n        return memo[u] = ans;\n    }\n\npublic:\n    int countRestrictedPaths(int n, vector<vector<int>>& edges) {\n        N = n;\n        graph = vector<vector<pair<int, int>>>(n + 1);\n        // O(E)\n        for (auto e : edges) {\n            graph[e[0]].push_back({e[2], e[1]});\n            graph[e[1]].push_back({e[2], e[0]});\n        }\n\n        // djikstra\n        distance = vector<int>(n + 1, INT_MAX);\n        memo = vector<int>(n + 1, -1);\n        distance[n] = 0;\n\n        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;\n        q.push({0, n});\n\n        // O(ElogV)\n        while (!q.empty()) {\n            int u = q.top().second; int d = q.top().first;\n            q.pop();\n\n            for (auto e : graph[u]) {\n                int v = e.second; int wt = e.first;\n                if (distance[v] <= wt + d) continue;\n                distance[v] = wt + d;\n                q.push({wt + d, v});\n            }\n        }\n\n        return dfs(1);\n    }\n};\n```
[]