Dijkstra algorithm || C++
We may use here Dijkstra algorithm with small modification. \nLet\'s use additional array numWays, where numWays[i] - number of shortest paths from 0 to i verte
We may use here Dijkstra algorithm with small modification. \nLet\'s use additional array numWays, where numWays[i] - number of shortest paths from 0 to i vertex. \nWhen we update distance from current vertex to neighbors, we should check two situations:\n\t1. distance to u + w(u, v) < distance to v. Update distance, and update numWays.\n\t2. distance to u + w(u, v) == distance to v. Add numWays[v] to numWays[u].\n```\nclass Solution {\nprivate:\n    typedef long long ll;\n    const int MOD = 1E9 + 7;\n    \n    int dijkstra(const vector<vector<pair<int, ll>>>& adj){\n        set<pair<ll, int>> pq;\n        int n = adj.size();\n        vector<ll> numWays(n, 1), dist(n, LLONG_MAX);\n        dist[0] = 0;\n        for (int i = 0; i < n; ++i){\n            pq.insert({dist[i], i});\n        }\n        \n        while (!pq.empty()){\n            int u = pq.begin()->second;\n            ll uDist = pq.begin()->first;\n            pq.erase(pq.begin());\n            for (auto [v, w]: adj[u]){\n                ll vDist = dist[v], newDist = uDist + w;\n                if (vDist > newDist){\n                    pq.erase({vDist, v});\n                    pq.insert({newDist, v});\n                    dist[v] = newDist;\n                    numWays[v] = numWays[u];\n                } else if (vDist == newDist){\n                    numWays[v] = (numWays[v] + numWays[u]) % MOD;\n                }\n            }\n        }\n        return numWays[n - 1];\n    }\n    \n    \npublic:\n    int countPaths(int n, vector<vector<int>>& roads) {\n        vector<vector<pair<int, ll>>> adj(n);\n        for (auto road: roads){\n            adj[road[0]].push_back({road[1], ll(road[2])});\n            adj[road[1]].push_back({road[0], ll(road[2])});\n        }\n        return dijkstra(adj);\n    }\n};\n```\n\n**Time complexity**: O(ElogV + VlogV) \n**Space complexity**: O(V + E)\nV - number of vertices, E - number of edges.
[]