C++ BFS + DFS
This problem was difficult for me to understand. Though, when I finally was able to unpack it, implementing it did not seem that hard.\n\n> Update: the initial 
This problem was difficult for me to understand. Though, when I finally was able to unpack it, implementing it did not seem that hard.\n\n> Update: the initial solution was accepted (< 500 ms), but now it gives TLE. We now need to use a priority queue for picking the next number during BFS.\n\n**BFS**\nTo figure out restricted paths, we first need to compute the distance to the last node for each node `i`.\n\nWe can do it using BFS (Dijkstra\'s) **starting from the last node**. In the code below, the distance for each node is stored in `dist`.\n\n**DFS**\nNow, we need to accumulate the number of restricted paths:\n- For the first node, the number of paths is `1`.\n- For node `i`, the number is a sum of restricted paths for all connected nodes `j`, where and `dist[i] < dist[j]`.\n\nWe can compute this using DFS, and we need to memoise the results in `dp` to avoid recomputation.\n\n**C++**\n```cpp\nint dfs(vector<vector<pair<int, int>>> &al, vector<int> &dist, vector<int> &dp, int i) {\n    if (i == 1)\n        return 1;\n    if (dp[i] == -1) {\n        dp[i] = 0;\n        for (auto [j, w] : al[i])\n            if (dist[i] < dist[j])\n                dp[i] = (dp[i] + dfs(al, dist, dp, j)) % 1000000007;\n    }\n    return dp[i];\n}\nint countRestrictedPaths(int n, vector<vector<int>>& edges) {\n    vector<vector<pair<int, int>>> al(n + 1);\n    vector<int> dist(n + 1), dp(n + 1, -1);\n    for (auto &e : edges) {\n        al[e[0]].push_back({e[1], e[2]});\n        al[e[1]].push_back({e[0], e[2]});\n    }\n    priority_queue<pair<int, int>, vector<pair<int, int>>> pq;\n    pq.push({0, n});\n    while (!pq.empty()) {\n        auto i = pq.top().second; pq.pop();\n        for (auto [j, w] : al[i]) {\n            if (j != n && (dist[j] == 0 || dist[j] > dist[i] + w)) {\n                dist[j] = dist[i] + w;\n                pq.push({-dist[j], j});\n            }\n        }\n    }\n    return dfs(al, dist, dp, n);\n}\n```
[]