[link](https://leetcode.com/problems/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 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

#### Constraints:

- 1 <= k <= n <= 100
- 1 <= times.length <= 6000
- times[i].length == 3
- 1 <= ui, vi <= n
- ui != vi
- 0 <= wi <= 100
- All the pairs (ui, vi) are unique. (i.e., no multiple edges.)

---

Create an adjacency dictionary adj to represent the directed graph. Initialize an empty dictionary shortest to store the shortest time taken to reach each node, and res to store the result (maximum time taken to reach all nodes).

Convert the times list of edges into an adjacency list representation. For each source node s, add a tuple (d, w) to the list of destination nodes and weights in the adj dictionary.

Initialize a min-heap minHeap with a tuple (0, k) representing the source node k with a weight of 0.

While the minHeap is not empty:
a. Pop the node n1 with the minimum weight w1 from the minHeap.
b. If n1 is already in the shortest dictionary, skip to the next iteration (node has already been visited).
c. Add n1 and w1 to the shortest dictionary to record the shortest time to reach n1.
d. Update the res variable with w1 (current maximum time to reach nodes).
e. For each neighbor node n2 and its corresponding weight w2 in the adj dictionary for node n1:

If n2 has not been visited (not in the shortest dictionary), add it to the minHeap with the updated weight (w1 + w2) to explore later.
Return res if all nodes have been visited (length of shortest is equal to n), otherwise, return -1 (signal cannot reach all nodes).

The time complexity of this solution is O(NlogN + ElogN), where N is the number of nodes, E is the number of edges, and logN accounts for the heap operations. The space complexity is O(N+E) due to the adjacency dictionary adj and the min-heap minHeap.

#### Solution 1

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        adj = {}
        for i in range(1, n + 1):
            adj[i] = []
        for s, d, w in times:
            adj[s].append((d, w))
        
        shortest = {}
        res = 0
        minHeap = [(0, k)]
        while minHeap:
            w1, n1 = heapq.heappop(minHeap)
            if n1 in shortest:
                continue
            shortest[n1] = w1
            res = w1
            for n2, w2 in adj[n1]:
                if n2 not in shortest:
                    heapq.heappush(minHeap, (w1 + w2, n2))

        return res if len(shortest) == n else -1

O(T): O(NlogN + ElogN)
O(S): O(N+E)

#### Solution 2

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        adj = collections.defaultdict(list)
        for s, d, w in times:
            adj[s].append((d, w))
        
        minHeap = [(0, k)]
        visit = set()
        res = 0
        while minHeap:
            w1, n1 = heapq.heappop(minHeap)
            if n1 in visit:
                continue
            visit.add(n1)
            res = w1
            for n2, w2 in adj[n1]:
                if n2 not in visit:
                    heapq.heappush(minHeap, (w1 + w2, n2))
        
        return res if len(visit) == n else -1