LeetCode link:[743. Network Delay Time](https://leetcode.com/problems/network-delay-time), difficulty:**Medium**.

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`.

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

**Output**:`2`

**Input**:`times = [[1,2,1]], n = 2, k = 1`

**Output**:`1`

**Input**:`times = [[1,2,1]], n = 2, k = 2`

**Output**:`-1`

- All the pairs`(ui, vi)` are**unique**. (i.e., no multiple edges.)

<details>

<summary>Hint 1</summary>

We visit each node at some time, and if that time is better than the fastest time we've reached this node, we travel along outgoing edges in sorted order. Alternatively, we could use Dijkstra's algorithm.

</details>

* Time:`O()`.

* Space:`O()`.

classSolution:

defnetworkDelayTime(self,items: List[List[int]],n:int,start:int) ->int:

min_distances= [float('inf')]* (n+1)

min_distances[start]=0

node_to_pairs= defaultdict(set)

for source, target, distancein items:

node_to_pairs[source].add((target, distance))

for _inrange(n-1):

for node, min_distanceinenumerate(min_distances):

if min_distance==float('inf'):

for target_node, distancein node_to_pairs[node]:

distance_= distance+ min_distance

if distance_< min_distances[target_node]:

min_distances[target_node]= distance_

result=max(min_distances[1:])

if result==float('inf'):

return result