# 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