[Leetcode] Medium : Network Delay time

Description

You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times as directed edges times[i] = (ui, vi, wi), where ui is the source node, vi is the target node, and wi is the time it takes for a signal to travel from source to target.

We will send a signal from a given node k. Return the time it takes for all the n nodes to receive the signal. If it is impossible for all the n nodes to receive the signal, return -1.

 

Example 1:

Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2

 

My Solution

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        import heapq
        
        graph = [[] for i in range(n + 1)]
        distance = [1e9] * (n + 1)
        
        for node1, node2, dist in times:
            graph[node1].append((node2, dist))
            
        def dijkstra(start):
            q = []
            heapq.heappush(q, (0, start))
            distance[start] = 0
            
            while q:
                dist, now = heapq.heappop(q)
                if distance[now] < dist:
                    continue
                for i in graph[now]:
                    cost = dist + i[1]
                    if cost < distance[i[0]]:
                        distance[i[0]] = cost
                        heapq.heappush(q,(cost, i[0]))
            
        
        dijkstra(k)
        
        max_distance = 0
        for d in distance:
            if d != 1e9:
                max_distance = max(max_distance, d)
            
        
        return max_distance if (max_distance < 1e9 and distance.count(1e9) <= 1)  else -1

 

문제 출처 : https://leetcode.com/problems/network-delay-time/

Network Delay Time - LeetCode