Java / C++ Dijkstra Clean Effective Code with Explanation
Set up the classic Dijkstra algorithm keeping track of cost for each node and the number of paths with the smallest cost.\n\nA few tricks to make it work and ma
Set up the classic Dijkstra algorithm keeping track of cost for each node and the number of paths with the smallest cost.\n\nA few tricks to make it work and make it effective:\n\n1. Push to the queue only the nodes with the smallest cost. If you encounter the node with the same cost on a different path, update the paths but don\'t push the node to the queue again.\n2. If you encounter the node for the first time, or found a more cost-effective path, use the number of paths of the parent.\n3. If you encounter the node more than once with the optimal cost, increment the number of paths by the number of paths of the parent.\n\n**Java:**\n```\n    public int countPaths(int n, int[][] roads) {\n        final long MODULO = 1000000007;\n        List<int[]>[] adj = new List[n];\n        Arrays.setAll(adj, x -> new ArrayList<>());\n        for (int[] r : roads) { // populate adjacency lists\n            adj[r[0]].add(new int[]{r[1], r[2]});\n            adj[r[1]].add(new int[]{r[0], r[2]});\n        }\n        long[] cost = new long[n], paths = new long[n];\n        Arrays.fill(cost, -1); // -1 -> not visited\n        Queue<long[]> q = new PriorityQueue<>((l, r) -> Long.compare(l[1], r[1])); // [node, cost]\n        q.offer(new long[]{0,0});\n        paths[0] = 1; // to make path accumulation work\n        cost[0] = 0;\n        \n        while (!q.isEmpty()) {\n            long[] f = q.poll();\n            int fnode = (int) f[0];\n            if (fnode == n - 1)\n                return (int)(paths[fnode] % MODULO);\n            for (int[] ch : adj[fnode]) {\n                long newCost = f[1] + ch[1];\n                if (newCost == cost[ch[0]]) // add all paths from the parent node\n                    paths[ch[0]] += paths[fnode] % MODULO;\n                if (cost[ch[0]] == -1 || newCost < cost[ch[0]]) {\n                    paths[ch[0]] = paths[fnode]; // all previous paths are irrelevant\n                    q.offer(new long[]{ch[0], newCost});\n                    cost[ch[0]] = newCost;\n                }\n            }\n        }\n        return -1; // shouldn\'t get here\n    }\n```\n**C++:**\n```\n    int countPaths(int n, vector<vector<int>>& roads) {\n        static constexpr long MODULO = 1000000007;\n        vector<vector<pair<int,int>>> adj(n, vector<pair<int,int>>());\n        for (const vector<int>& r : roads) { // populate adjacency lists with node and cost\n            adj[r[0]].emplace_back(r[1], r[2]);\n            adj[r[1]].emplace_back(r[0], r[2]);\n        }\n        vector<long> paths(n), cost(n, -1); // -1 -> not visited\n        static constexpr auto comp = [](const pair<int,long>& l, const pair<int,long>& r) { return l.second > r.second; };\n        priority_queue<pair<int,long>, vector<pair<int,long>>, decltype(comp)> q(comp); // [node, cost]\n        q.emplace(0, 0);\n        paths[0] = 1; // to make path accumulation work\n        cost[0] = 0;\n        \n        while (!q.empty()) {\n            auto [fnode, fCost] = q.top();\n            q.pop();\n            if (fnode == n - 1)\n                return static_cast<int>(paths[fnode] % MODULO);\n            for (const auto& [ chNode, chCost ] : adj[fnode]) {\n                long newCost = fCost + chCost;\n                if (newCost == cost[chNode]) // add all paths from the parent node\n                    paths[chNode] += paths[fnode] % MODULO;\n                if (cost[chNode] == -1 || newCost < cost[chNode]) {\n                    paths[chNode] = paths[fnode]; // all previous paths are irrelevant\n                    q.emplace(chNode, newCost);\n                    cost[chNode] = newCost;\n                }\n            }\n        }\n        return -1; // shouldn\'t get here\n    }
['C', 'Java']