743

743. Network Delay Time (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 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.)

Companies:
Google, Amazon

Related Topics:
Depth-First Search, Breadth-First Search, Graph, Heap (Priority Queue), Shortest Path

Similar Questions:

• The Time When the Network Becomes Idle (Medium)
• Second Minimum Time to Reach Destination (Hard)

Solution 1. Dijkstra

// OJ: https://leetcode.com/problems/network-delay-time/
// Author: github.com/lzl124631x
// Time: O(E + VlogV)
// Space: O(E)
class Solution {
    typedef pair<int, int> PII;
public:
    int networkDelayTime(vector<vector<int>>& E, int n, int k) {
        vector<vector<PII>> G(n);
        for (auto &e : E) G[e[0] - 1].emplace_back(e[1] - 1, e[2]);
        vector<int> dist(n, INT_MAX);
        dist[k - 1] = 0;
        priority_queue<PII, vector<PII>, greater<>> pq;
        pq.emplace(0, k - 1);
        while (pq.size()) {
            auto [cost, u] = pq.top();
            pq.pop();
            if (dist[u] > cost) continue; 
            for (auto &[v, w] : G[u]) {
                if (dist[v] > dist[u] + w) {
                    dist[v] = dist[u] + w;
                    pq.emplace(dist[v], v);
                }
            }
        }
        int ans = *max_element(begin(dist), end(dist));
        return ans == INT_MAX ? -1 : ans;
    }
};

Solution 2. Bellman-Ford

// OJ: https://leetcode.com/problems/network-delay-time/
// Author: github.com/lzl124631x
// Time: O(VE)
// Space: O(V)
class Solution {
public:
    int networkDelayTime(vector<vector<int>>& E, int n, int k) {
        vector<int> dist(n, INT_MAX);
        dist[k - 1] = 0;
        for (int i = 1; i < n; ++i) {
            for (auto &e : E) {
                int u = e[0] - 1, v = e[1] - 1, w = e[2];
                if (dist[u] != INT_MAX) dist[v] = min(dist[v], dist[u] + w);
            }
        }
        int ans = *max_element(begin(dist), end(dist));
        return ans == INT_MAX ? -1 : ans;
    }
};