Well Explained
Intuition\nThe problem involves finding the number of distinct paths from the starting node 0 to the ending node n-1 in an undirected graph with weighted edges.
# Intuition\nThe problem involves finding the number of distinct paths from the starting node `0` to the ending node `n-1` in an undirected graph with weighted edges. Each path\'s weight is calculated as the sum of edge weights along that path. Additionally, we need to keep track of the number of such paths because the weights might be the same for different paths.\n\n# Approach\n1. **Graph Representation:**\n   - Use an adjacency list (`adj`) to represent the graph where each node points to a list of pairs representing its neighbors and the edge weights.\n\n2. **Dijkstra\'s Algorithm with Modifications:**\n   - Use a priority queue (`pq`) to facilitate Dijkstra\'s algorithm. Each entry in the priority queue is a pair of `(time_to_reach_node, node)`.\n   - Use two vectors, `time_to_reach` to store the minimum time to reach each node from the source node `0` and `ways` to store the number of distinct ways to reach each node.\n   - Initialize `time_to_reach[0] = 0` and `ways[0] = 1`, indicating there is one way to reach the starting node with a weight of `0`.\n\n3. **Processing Nodes:**\n   - Begin with the source node `0` in the priority queue with `time_to_reach[0] = 0` and `ways[0] = 1`.\n   - Extract the node with the smallest `time_to_reach` from the priority queue. Update the `time_to_reach` and `ways` for its neighbors if a shorter path is found or if the same path weight can be reached through multiple ways.\n\n4. **Result Computation:**\n   - After processing all nodes, return `ways[n-1] % MOD`, which represents the number of distinct paths to reach node `n-1`.\n\n5. **Edge Cases:**\n   - Handle cases where nodes might be unreachable by checking if `ways[n-1]` remains `0`, indicating no valid path exists.\n\n# Complexity\n- **Time Complexity:** $$(O((n + m) \\log n))$$\n  - Where \\(n\\) is the number of nodes and \\(m\\) is the number of edges (roads).\n  - Each node and edge is processed once. Operations involving the priority queue have a logarithmic time complexity.\n\n- **Space Complexity:** $$(O(n))$$\n  - Space is primarily used for the adjacency list (`adj`), priority queue (`pq`), `time_to_reach`, and `ways` vectors.\n\n\n# Code\n```\nclass Solution {\npublic:\n    int countPaths(int n, vector<vector<int>>& roads) {\n        const long long MOD = 1e9 + 7;\n        vector<pair<int, int>> adj[n];\n\n        for (int i = 0; i < roads.size(); i++) {\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\n        priority_queue<pair<long long, long long>, \n        vector<pair<long long, long long>>, \n        greater<pair<long long,long long>>>  pq;\n\n        vector<long long> time_to_reach(n, LONG_MAX);\n        vector<long long> ways(n, 0);\n\n        pq.push({0, 0});\n        time_to_reach[0] = 0;\n        ways[0] = 1;\n\n        while(!pq.empty()){\n            long long time = pq.top().first;\n            long long node = pq.top().second;\n\n            pq.pop();\n\n            if (time > time_to_reach[node]) continue;\n\n\n            for(auto it : adj[node]){\n                long long nxt_node = it.first;\n                long long new_time = it.second;\n\n                if(time_to_reach[nxt_node] > time + new_time){\n                    time_to_reach[nxt_node] = time + new_time;\n                    ways[nxt_node] = ways[node];\n                    pq.push({time_to_reach[nxt_node], nxt_node});\n                }\n                 else if (time_to_reach[nxt_node] == time + new_time) {\n                    ways[nxt_node] = (ways[nxt_node] + ways[node]) % MOD;\n\n                }\n            }\n        }\n\n        return ways[n-1]% MOD;\n    }\n};\n```
['Breadth-First Search', 'Graph', 'Heap (Priority Queue)', 'Shortest Path', 'C++']