cyga

Untitled

Aug 3rd, 2021
625
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import heapq
  2.  
  3. class Solution:
  4.     def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
  5.         graph = [[] for _ in range(n)]
  6.         for src, dst, time in times:
  7.             graph[src-1].append((dst-1, time))
  8.        
  9.         dists = [float('inf')]*n
  10.        
  11.         q = [(0, k-1)]
  12.         while q:
  13.             dist, v = heapq.heappop(q)
  14.             if dists[v] < float('inf'):
  15.                 continue
  16.             dists[v] = dist
  17.             for u, distvu in graph[v]:
  18.                 if dists[u] == float('inf'):
  19.                     heapq.heappush(q, (dist + distvu, u))
  20.        
  21.         maxDist = max(dists)
  22.         return -1 if float('inf') == maxDist else maxDist
RAW Paste Data