✅✅C++ -  Beats 100%  || Dijkstra algorithm || Easy Understanding ✅✅
Intuition\nThe code likely implements Dijkstra\'s algorithm with modifications to track the number of shortest paths.\n# Approach\n1. Graph Representation: The 
# Intuition\nThe code likely implements Dijkstra\'s algorithm with modifications to track the number of shortest paths.\n# Approach\n1. Graph Representation: The roads vector represents edges between nodes with their weights.\n2. Initialization: Initializes necessary data structures like adj (adjacency list), weight (distances), and way (counts of paths).\n3. Dijkstra\'s Algorithm: Performs a modified Dijkstra\'s algorithm using a priority queue (pq) to find the shortest paths.\n4. Track Shortest Paths: While traversing the graph, it keeps track of the shortest paths (way) and updates counts for each node\'s shortest path to the destination node (n - 1).\n\n# Complexity\n- Time complexity:\nThe code uses Dijkstra\'s algorithm, taking O(E * log(V)) time, where E is the number of edges and V is the number of vertices. The loop complexity is mainly determined by the number of edges and the priority queue operations.\n- Space complexity:\nIt uses additional space for adj (O(E)) to store the adjacency list, weight and way arrays (O(V)) to store distances and counts of paths, and a priority queue (O(E)) for Dijkstra\'s algorithm. Overall, it\'s O(V + E).\n# Code\n```\nclass Solution\n{\n    int mod = 1e9 + 7;\n\npublic:\n    int countPaths(int n, vector<vector<int>> &roads)\n    {\n        vector<vector<pair<int, int>>> adj(n);\n        for (int i = 0; i < roads.size(); i++)\n        {\n            // {u, v, w}\n            adj[roads[i][0]].push_back({roads[i][1], roads[i][2]});\n            adj[roads[i][1]].push_back({roads[i][0], roads[i][2]});\n        }\n        vector<long long> weight(n, 1e15);\n        vector<int> way(n, 0);\n        priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;\n        pq.push({0, 0});\n        weight[0] = 0;\n        way[0] = 1;\n        while (!pq.empty())\n        {\n            auto it = pq.top();\n            pq.pop();\n\n            long long dist = it.first;\n            int node = it.second;\n\n            if (node == n - 1)\n            {\n                break;\n            }\n            for (auto &&neighbour : adj[node])\n            {\n                int newnode = neighbour.first;\n                long long newdist = neighbour.second;\n\n                if (newdist + dist < weight[newnode])\n                {\n                    weight[newnode] = newdist + dist;\n                    way[newnode] = way[node];\n                    pq.push({newdist + dist, newnode});\n                }\n                else if (newdist + dist == weight[newnode])\n                {\n                    way[newnode] = (way[newnode] + way[node] * 1LL) % mod;\n                }\n            }\n        }\n        return way[n - 1];\n    }\n};\n```
['Dynamic Programming', 'Graph', 'Topological Sort', 'Shortest Path', 'C++']