We use Dijkstra’s shortest path distance algorithm to find delays to all nodes from source. Max distance from source is the minimum time it would take for the signal to reach all nodes.
heapq does not allow updating key, so we insert new entries like (d_v, v) whenever there is a better distance and get rid of stale entries after pop.
Time: 
from heapq import heappush as push, heappop as pop
class Solution:
def get_adj_list(self, times, n) -> Dict[int, List[Tuple[int]]]:
adj_list = {u: [] for u in range(1, n+1)}
for u, v, w in times:
adj_list[u].append( (v, w) )
return adj_list
def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
adj_list = self.get_adj_list(times, n)
dist = [float("inf")] * (n+1)
dist[k] = 0
q = [(0, k)]
while q:
d_u, u = pop(q)
# stale
if d_u > dist[u]:
continue
for v, w in adj_list[u]:
d_v = dist[u] + w
if d_v >= dist[v]:
continue
dist[v] = d_v
push(q, (d_v, v) )
max_delay = max(dist[1:])
return max_delay if max_delay != float("inf") else -1
To make it more efficient, we could use updatable minq based on bst and dict.
from sortedcontainers import SortedSet
class UpdatableMinQ:
def __init__(self):
self.sset = SortedSet()
self.map = {}
def push(self, key, priority):
item = (priority, key)
self.sset.add(item)
self.map[key] = item
def pop(self):
_, key = self.sset.pop(0)
del self.map[key]
return key
def update(self, key, priority):
old_item = self.map[key]
del self.map[key]
self.sset.remove(old_item)
self.push(key, priority)
def __bool__(self):
return bool(self.sset)
class Solution:
def get_adj_list(self, times, n) -> Dict[int, List[Tuple[int]]]:
adj_list = {u: [] for u in range(1, n+1)}
for u, v, w in times:
adj_list[u].append( (v, w) )
return adj_list
def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
adj_list = self.get_adj_list(times, n)
dist = [float("inf")] * (n+1)
dist[k] = 0
q = UpdatableMinQ()
q.push(k, 0)
visited = {k}
while q:
u = q.pop()
for v, w in adj_list[u]:
d_v = dist[u] + w
if v in visited:
if d_v < dist[v]:
dist[v] = d_v
q.update(v, d_v)
continue
visited.add(v)
dist[v] = d_v
q.push(v, d_v)
max_delay = max(dist[1:])
return max_delay if max_delay != float("inf") else -1
unreasonably effective 
Leave a comment