1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46
| class Solution: def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
def dijkstra(start):
priority_queue = [] heapq.heappush(priority_queue, (0, start_node))
dis_table = collections.defaultdict(lambda: 20000) dis_table[start_node] = 0
while priority_queue:
shortest_dis, current_node = heapq.heappop(priority_queue) if dist[current_node] < shortest_dis: continue
for adjacent_node, dis in graph[current_node]: cost = shortest_dis + dis if cost < dist[adjacent_node]: dist[adjacent_node] = cost heapq.heappush(priority_queue, (cost, adjacent_node))
return dist
graph = collections.defaultdict(list) for u_node, v_node, dis in times: graph[u_node].append((v_node, dis))
result = dijkstra(k) return max(result.values()) if len(result) == n else -1
|