Untitled
unknown
plain_text
a month ago
900 B
4
Indexable
class Solution: def countPaths(self, n: int, roads: List[List[int]]) -> int: graph = defaultdict(dict) for u, v, t in roads: graph[u][v] = t graph[v][u] = t distance = [math.inf] * n ways = [1] * n processed = [False] * n distance[0] = 0 queue = [(0,0)] heapq.heapify(queue) while queue: _, u = heapq.heappop(queue) if processed[u]: continue processed[u] = True for v, vt in graph[u].items(): if processed[v]: continue if distance[v] == distance[u] + vt: ways[v] += 1 else: distance[v] = min(distance[v], distance[u] + vt) heapq.heappush(queue, (distance[v], v)) return ways[n - 1] % (10**9 + 7)
Editor is loading...
Leave a Comment