cyga

Untitled

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