cyga

Untitled

Aug 3rd, 2021
708
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. # https://leetcode.com/problems/network-delay-time
  2. from sortedcontainers import SortedList
  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 = SortedList([(0, k-1)])
  13.         while q:
  14.             dist, v = q.pop(0)
  15.             dists[v] = dist
  16.             for u, distvu in graph[v]:
  17.                 if dist + distvu < dists[u]:
  18.                     if dists[u] < float('inf'):
  19.                         q.remove((dists[u], u))
  20.                     dists[u] = dist + distvu
  21.                     q.add((dist + distvu, u))
  22.        
  23.         maxDist = max(dists)
  24.         return -1 if float('inf') == maxDist else maxDist
RAW Paste Data