743. Network Delay Time

2026, Oct 29 2 mins read

1. Description

Consider a directed network of n nodes numbered 1 through n.
Each entry times[i] = (u$_i$, v$_i$, w$_i$) describes an edge from u$_i$ to v$_i$ with travel time w$_i$.
A signal starts at node k at time 0. Return the earliest time by which every node has received it, or -1 if any node is unreachable.

2. Example

Example 1

Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2
Explanation: Nodes 1 and 3 receive the signal at time 1, and node 4 receives it at time 2.

Example 2

Input: times = [[1,2,1]], n = 2, k = 1
Output: 1
Explanation: Node 2 receives the signal one time unit after it is sent from node 1.

Example 3

Input: times = [[1,2,1]], n = 2, k = 2
Output: -1
Explanation: The edge only leads from node 1 to node 2, so a signal starting at node 2 cannot reach node 1.

3. Constraints

1 <= k <= n <= 100
1 <= times.length <= 6000
times[i].length == 3
1 <= u$_i$, v$_i$ <= n
u$_i$ != v$_i$
0 <= w$_i$ <= 100
Each ordered pair (u$_i$, v$_i$) occurs at most once.

4. Solutions

Dijkstra

n = number of nodes, m = times.size()
Time complexity: O(n + m log n)
Space complexity: O(n + m)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    int networkDelayTime(vector<vector<int>> &times, int n, int k) {
        vector<vector<pair<int, int>>> graph(n + 1);
        for (const auto &edge : times) {
            int s = edge[0], t = edge[1], w = edge[2];
            graph[s].emplace_back(t, w);
        }

        vector<int> delays(n + 1, numeric_limits<int>::max());
        delays[k] = 0;

        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
        pq.emplace(0, k);

        while (!pq.empty()) {
            const auto [delay, node] = pq.top();
            pq.pop();

            if (delay != delays[node]) {
                continue;
            }

            for (auto [next_node, weight] : graph[node]) {
                int next_delay = delay + weight;

                if (next_delay < delays[next_node]) {
                    delays[next_node] = next_delay;
                    pq.emplace(next_delay, next_node);
                }
            }
        }

        int max_delay = *max_element(delays.begin() + 1, delays.end());

        return max_delay == numeric_limits<int>::max() ? -1 : max_delay;
    }
};

Search

Tags