To solve the problem, I used Dijkstra’s algorithm to find the shortest path from node 0 to node n - 1. While doing that, I kept track of the number of ways to reach each node using a ways array. I initialized the distance to node 0 as 0 and the number of ways to reach it as 1. As I traversed the graph using a min-heap, I updated the shortest distance to each node. If I found a shorter path, I reset the ways count; if I found an equally short path, I added to the existing count. Finally, I returned the number of ways to reach the destination node in the shortest time, modulo (10^9 + 7).
class Solution:
def countPaths(self, n: int, roads: List[List[int]]) -> int:
MOD = 10**9 + 7
graph = [[] for _ in range(n)]
for u, v, time in roads:
graph[u].append((v, time))
graph[v].append((u, time))
min_time = [float('inf')] * n
ways = [0] * n
min_time[0] = 0
ways[0] = 1
pq = [(0, 0)]
while pq:
curr_time, node = heapq.heappop(pq)
if curr_time > min_time[node]:
continue
for nei, t in graph[node]:
new_time = curr_time + t
if new_time < min_time[nei]:
min_time[nei] = new_time
ways[nei] = ways[node]
heapq.heappush(pq, (new_time, nei))
elif new_time == min_time[nei]:
ways[nei] = (ways[nei] + ways[node]) % MOD
return ways[n - 1]- Time: O(n + e)
- Space: O(n + e)
