Network Delay Time

You are given n nodes numbered from 1 to n.

You are also given a list of directed edges:

times[i] = [u, v, w]

which means a signal takes w units of time to travel from node u to node v.

A signal is sent from node k.

Return the minimum time required for all nodes to receive the signal.

If it is impossible for every node to receive the signal, return:

-1

Example

n = 4

k = 2

times =

[2,1,1]

[2,3,1]

[3,4,1]

The signal travels:

2 → 1 = 1

2 → 3 = 1

3 → 4 = 1

So the farthest node receives the signal after:

1 + 1 = 2

Therefore:

2

Main Idea

This is a Shortest Path problem with weighted edges.

Since all edge weights are positive, we can use Dijkstra's Algorithm.

Steps

1. Build an adjacency list.
2. Set the distance of the starting node k to 0.
3. Put (0, k) into a min-priority queue.
4. Take the node with the smallest known distance.
5. Relax all its outgoing edges.
6. Continue until the queue is empty.
7. Find the maximum shortest distance among all nodes.
8. If any node is unreachable, return -1.

The answer is:

maximum shortest distance