c++ | easy | fast
\n\n# Code\n\n\nclass Solution {\n    typedef pair<int, int> PII;\npublic:\n    int countRestrictedPaths(int n, vector<vector<int>>& E) {\n        long mod = 1e
\n\n# Code\n```\n\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```
['C++']