🛣️ Simple 🧠 Python Solution beats 93 % | Dijkstra algo |
\n\n---\n\n## \uD83D\uDEA6 Count Paths from Intersection 0 to n-1 in Shortest Time \u23F1\uFE0F\n\n### \uD83D\uDE80 Problem Statement:\n\nYou are in a city with
![image.png](https://assets.leetcode.com/users/images/00664d02-4e8a-48a5-a096-4521c7847256_1724225669.1745865.png)\n\n---\n\n## \uD83D\uDEA6 Count Paths from Intersection 0 to n-1 in Shortest Time \u23F1\uFE0F\n\n### \uD83D\uDE80 Problem Statement:\n\nYou are in a city with `n` intersections numbered from `0` to `n - 1`. The city has some **bi-directional** roads between the intersections, where `roads[i] = [ui, vi, timei]` represents a road between intersection `ui` and intersection `vi` that takes `timei` minutes to travel. \uD83D\uDE97\uD83D\uDEE3\uFE0F\n\nYou want to know in how many ways you can **travel from intersection 0 to intersection n-1 in the shortest amount of time**.\n\nGiven `n` intersections and an array `roads`, return **the number of ways** to arrive at your destination in the shortest amount of time. Since the answer can be large, return it **modulo** `10^9 + 7`.\n\n### \uD83D\uDCA1 Intuition:\n\n- This problem is a twist on Dijkstra\'s algorithm! \uD83C\uDFAF\n- Instead of just finding the shortest path, we also need to **count how many ways** we can reach the destination intersection in the same shortest time.\n- **Dijkstra\'s Algorithm** helps us calculate the shortest time to reach each node.\n- We maintain a **ways array** to track the number of ways to reach each node in the shortest time.\n\n### \uD83E\uDDE0 Approach:\n\n1. **Adjacency List:** Build an adjacency list for the city where every road connects two intersections with a specific travel time.\n  \n2. **Dijkstra\'s Algorithm:** Use a **min-heap** (priority queue) to explore nodes based on the shortest travel time.\n\n3. **Track Shortest Paths:** Maintain a `dis[]` array to store the shortest time to reach each node and a `ways[]` array to count the number of ways to reach that node in the shortest time.\n\n4. **Count Ways:** For each neighboring node, if the new calculated time matches the shortest time, add the number of ways from the current node to the neighbor. If the new time is shorter, update the shortest time and reset the ways to match the number of ways from the current node.\n\n5. **Final Answer:** Once all nodes have been processed, return the number of ways to reach the destination `n-1`, **modulo `10^9 + 7`**.\n\n### \uD83D\uDCDD Code:\n\n```python\nimport heapq\n\nclass Solution:\n    def countPaths(self, n: int, roads: List[List[int]]) -> int:\n        # Step 1\uFE0F\u20E3: Build the adjacency list for the graph\n        adj = [[] for _ in range(n)]\n        for u, v, w in roads:\n            adj[u].append([v, w])\n            adj[v].append([u, w])\n        \n        # Step 2\uFE0F\u20E3: Initialize arrays to store shortest distance and number of ways\n        ways = [0] * n\n        ways[0] = 1\n        dis = [float("inf")] * n\n        dis[0] = 0\n        \n        # Step 3\uFE0F\u20E3: Min-heap to store (time, node)\n        heap = [(0, 0)]  # (current time, node)\n        \n        while heap:\n            time, node = heapq.heappop(heap)\n            \n            # Explore all neighbors of the current node\n            for neighbor, travel_time in adj[node]:\n                new_time = time + travel_time\n                \n                # Case 1\uFE0F\u20E3: If we found another way with the same shortest time\n                if new_time == dis[neighbor]:\n                    ways[neighbor] += ways[node]\n                \n                # Case 2\uFE0F\u20E3: If we found a shorter time to reach the neighbor\n                elif new_time < dis[neighbor]:\n                    dis[neighbor] = new_time\n                    heapq.heappush(heap, (new_time, neighbor))\n                    ways[neighbor] = ways[node]\n        \n        # Step 4\uFE0F\u20E3: Return the number of ways to reach the destination modulo 10^9 + 7\n        MOD = 10**9 + 7\n        return ways[n-1] % MOD\n```\n\n### \uD83D\uDD75\uFE0F\u200D\u2642\uFE0F Example Simulation:\n\nConsider an example:\n\n```\nn = 4\nroads = [[0,1,2],[0,2,4],[1,3,1],[2,3,1]]\n```\n\n- **Adjacency List** looks like this:\n  - `0 -> [(1, 2), (2, 4)]`\n  - `1 -> [(0, 2), (3, 1)]`\n  - `2 -> [(0, 4), (3, 1)]`\n  - `3 -> [(1, 1), (2, 1)]`\n\n- Start with the min-heap `[(0, 0)]` (i.e., 0 minutes at node 0).\n- Process nodes:\n  - From node 0: Reach node 1 (time 2), and node 2 (time 4).\n  - From node 1: Reach node 3 (time 3).\n  - From node 2: Reach node 3 (time 5).\n- **Shortest time** to reach node `3` is `3` minutes. There is **1 way** to reach it.\n\n**Final Output:** `1`\n\n### \uD83D\uDD0D Complexity Analysis:\n\n- **Time Complexity:** `O(E log V)`, where `E` is the number of edges (roads) and `V` is the number of intersections. Each edge is processed once, and we push nodes into the heap with logarithmic complexity.\n- **Space Complexity:** `O(V + E)` for storing the adjacency list and the heap.\n\n### \uD83D\uDEA8 Edge Cases to Consider:\n\n1. **Isolated Intersections:** There should be no isolated intersections, as the inputs guarantee that all intersections are reachable.\n2. **Single Path:** If there is only one way to reach the destination, return `1`.\n3. **Multiple Shortest Paths:** Accurately count all ways to reach the destination in the same shortest time.\n\n---\n\nWith this approach, you can count all the ways to travel from intersection `0` to intersection `n-1` in the shortest time while keeping the solution efficient! \uD83C\uDF1F
['Graph', 'Shortest Path', 'Python3']