[C++] Dijkstra + DP + DFS
\nclass Solution {\npublic:\n    int MOD = 1e9 + 7;\n    unordered_map<int, vector<pair<int, int>>> hash;\n    int countRestrictedPaths(int n, vector<vector<int
```\nclass Solution {\npublic:\n    int MOD = 1e9 + 7;\n    unordered_map<int, vector<pair<int, int>>> hash;\n    int countRestrictedPaths(int n, vector<vector<int>>& e) {\n        for(auto& a: e){\n            hash[a[0]].push_back({a[1], a[2]});\n            hash[a[1]].push_back({a[0], a[2]});\n        }\n        vector<int> dist(n + 1, INT_MAX);\n        vector<int> memo(n + 1, -1);\n        dist[n] = 0;\n        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;\n        pq.push({0, n});\n        while(!pq.empty()){\n            auto [cost, node] = pq.top();\n            pq.pop();\n            for(auto& to: hash[node]){\n                int b = cost + to.second;\n                if(dist[to.first] > b){\n                    dist[to.first] = b;\n                    pq.push({b, to.first});\n                }\n            }\n        }\n        return dfs(n, dist, memo) % MOD;\n    }\n    int dfs(int start, vector<int>& dist, vector<int>& memo){\n        if(start == 1) return 1;\n        if(memo[start] != -1) return memo[start];\n        long long sum = 0;\n        for(auto& to: hash[start])\n            if(dist[start] < dist[to.first])\n                sum += dfs(to.first, dist, memo) % MOD;\n        return memo[start] = sum % MOD;\n    }\n};\n```
['Dynamic Programming', 'Depth-First Search', 'C', 'C++']