C++ Dijkstra + DP
See my latest update in repo LeetCode\n\n## Solution 1. Dijkstra + DP\n\nWe run Dijkstra algorithm starting from the nth node. \n\nLet dist[u] be the distance f
See my latest update in repo [LeetCode](https://github.com/lzl124631x/LeetCode)\n\n## Solution 1. Dijkstra + DP\n\nWe run Dijkstra algorithm starting from the `n`th node. \n\nLet `dist[u]` be the distance from the `u` node to `n`th node.\n\nLet `cnt[u]` be the number of restricted path from `u` node to `n`th node.\n\nEach time we visit a new node `u`, we can update its `cnt[u]` to be the sum of `cnt[v]` where `v` is a neighbor of `u` and `dist[v]` is smaller than `dist[u]`.\n\nThe answer is `cnt[0]`.\n\n```cpp\n// OJ: https://leetcode.com/problems/number-of-restricted-paths-from-first-to-last-node/\n// Author: github.com/lzl124631x\n// Time: O(ElogE)\n// Space: O(E)\nclass Solution {\n    typedef pair<int, int> PII;\npublic:\n    int countRestrictedPaths(int n, vector<vector<int>>& E) {\n        long mod = 1e9 + 7;\n        vector<vector<pair<long, int>>> G(n);\n        for (auto &e : E) {\n            int u = e[0] - 1, v = e[1] - 1, w = e[2];\n            G[u].emplace_back(v, w);\n            G[v].emplace_back(u, w);\n        }\n        priority_queue<PII, vector<PII>, greater<PII>> pq;\n        vector<long> dist(n, INT_MAX), cnt(n, 0);\n        dist[n - 1] = 0;\n        cnt[n - 1] = 1;\n        pq.emplace(0, n - 1);\n        while (pq.size()) {\n            auto [w, u] = pq.top();\n            pq.pop();\n            if (w > dist[u]) continue;\n            for (auto &[v, d] : G[u]) {\n                if (dist[v] > w + d) {\n                    dist[v] = w + d;\n                    pq.emplace(dist[v], v);\n                }\n                if (w > dist[v]) {\n                    cnt[u] = (cnt[u] + cnt[v]) % mod;\n                }\n            }\n        }\n        return cnt[0];\n    }\n};\n```
[]