# 743. Network Delay Time

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 minimum 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

Example 2:

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

Example 3:

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

# Solution

Approach 1: Dijkstra's.

# Code (Python)

Approach 1:

import heapq

class Solution:
    def networkDelayTime(self, times, n: int, k: int) -> int:
        # Dijkstra: find shortest paths for graphs with positive edges from 1 source vertex to all others
        # Explanation -- https://leetcode.com/discuss/general-discussion/1059477/A-noob's-guide-to-Djikstra's-Algorithm
        
        k = k - 1 # translate to 0 indexed
        edges = {i: [] for i in range(n)}
        for start, end, length in times:
            edges[start - 1].append((end - 1, length))
        
        known_distances = [float('inf') for _ in range(n)] # necessary only to get all distances; otherwise not necessary
        visited = set()
        explore_list = [(0, k)]
        heapq.heapify(explore_list)
        
        while explore_list:
            distance, vertex = heapq.heappop(explore_list)
            if vertex in visited:
                continue
            visited.add(vertex)
            
            known_distances[vertex] = distance
            for neighbor, length in edges[vertex]:
                if neighbor not in visited:
                    heapq.heappush(explore_list, (distance + length, neighbor))

        return -1 if max(known_distances) == float('inf') else max(known_distances)

# Code (C++)

Approach 1:

Approach 2: