Formatted question description: https://leetcode.ca/all/743.html

743. Network Delay Time (Medium)

There are N network nodes, labelled 1 to N.

Given times, a list of travel times as directed edges times[i] = (u, v, w), where u is the source node, v is the target node, and w is the time it takes for a signal to travel from source to target.

Now, we send a signal from a certain node K. How long will it take for all nodes to receive the signal? If it is impossible, return -1.

Example 1:

Input: times = [[2,1,1],[2,3,1],[3,4,1]], N = 4, K = 2
Output: 2

Note:

N will be in the range [1, 100].
K will be in the range [1, N].
The length of times will be in the range [1, 6000].
All edges times[i] = (u, v, w) will have 1 <= u, v <= N and 0 <= w <= 100.

Related Topics:
Heap, Depth-first Search, Breadth-first Search, Graph

Solution 1. Dijkstra

// OJ: https://leetcode.com/problems/network-delay-time/
// Time: O(E + VlogV)
// Space: O(E)
class Solution {
    typedef unordered_map<int, unordered_map<int, int>> Graph;
    typedef pair<int, int> iPair;
    vector<int> dijkstra(Graph graph, int N, int source) {
        priority_queue<iPair, vector<iPair>, greater<iPair>> pq;
        vector<int> dists(N, INT_MAX);
        pq.emplace(0, source);
        dists[source] = 0;
        while (pq.size()) {
            int u = pq.top().second;
            pq.pop();
            for (auto neighbor : graph[u]) {
                int v = neighbor.first, weight = neighbor.second;
                if (dists[v] > dists[u] + weight) {
                    dists[v] = dists[u] + weight;
                    pq.emplace(dists[v], v);
                }
            }
        }
        return dists;
    }
public:
    int networkDelayTime(vector<vector<int>>& times, int N, int K) {
        Graph graph;
        for (auto e : times) graph[e[0] - 1][e[1] - 1] = e[2];
        auto dists = dijkstra(graph, N, K - 1);
        int ans = 0;
        for (int d : dists) {
            if (d == INT_MAX) return -1;
            ans = max(ans, d);
        }
        return ans;
    }
};

Solution 2. Bellman-Ford

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

class Solution {
    public int networkDelayTime(int[][] times, int N, int K) {
        Map<Integer, List<int[]>> travelMap = new HashMap<Integer, List<int[]>>();
        for (int[] time : times) {
            int source = time[0] - 1, target = time[1] - 1, lapse = time[2];
            List<int[]> travels = travelMap.getOrDefault(source, new ArrayList<int[]>());
            travels.add(new int[]{target, lapse});
            travelMap.put(source, travels);
        }
        int[] received = new int[N];
        for (int i = 0; i < N; i++)
            received[i] = Integer.MAX_VALUE;
        received[K - 1] = 0;
        Queue<int[]> queue = new LinkedList<int[]>();
        queue.offer(new int[]{K - 1, 0});
        while (!queue.isEmpty()) {
            int[] nodeTime = queue.poll();
            int node = nodeTime[0], time = nodeTime[1];
            List<int[]> travels = travelMap.getOrDefault(node, new ArrayList<int[]>());
            for (int[] travel : travels) {
                int target = travel[0], lapse = travel[1];
                int totalLapse = time + lapse;
                if (totalLapse < received[target]) {
                    received[target] = totalLapse;
                    queue.offer(new int[]{target, totalLapse});
                }
            }
        }
        int maxTime = 0;
        for (int time : received) {
            if (time == Integer.MAX_VALUE)
                return -1;
            else
                maxTime = Math.max(maxTime, time);
        }
        return maxTime;
    }
}

############

class Solution {
    private static final int N = 110;
    private static final int INF = 0x3f3f;

    public int networkDelayTime(int[][] times, int n, int k) {
        int[][] g = new int[N][N];
        for (int i = 0; i < N; ++i) {
            Arrays.fill(g[i], INF);
        }
        for (int[] e : times) {
            g[e[0]][e[1]] = e[2];
        }
        int[] dist = new int[N];
        Arrays.fill(dist, INF);
        dist[k] = 0;
        boolean[] vis = new boolean[N];
        for (int i = 0; i < n; ++i) {
            int t = -1;
            for (int j = 1; j <= n; ++j) {
                if (!vis[j] && (t == -1 || dist[t] > dist[j])) {
                    t = j;
                }
            }
            vis[t] = true;
            for (int j = 1; j <= n; ++j) {
                dist[j] = Math.min(dist[j], dist[t] + g[t][j]);
            }
        }
        int ans = 0;
        for (int i = 1; i <= n; ++i) {
            ans = Math.max(ans, dist[i]);
        }
        return ans == INF ? -1 : ans;
    }
}

// OJ: https://leetcode.com/problems/network-delay-time/
// 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;
    }
};

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        INF = 0x3F3F
        g = defaultdict(list)
        for u, v, w in times:
            g[u - 1].append((v - 1, w))
        dist = [INF] * n
        dist[k - 1] = 0
        q = [(0, k - 1)]
        while q:
            _, u = heappop(q)
            for v, w in g[u]:
                if dist[v] > dist[u] + w:
                    dist[v] = dist[u] + w
                    heappush(q, (dist[v], v))
        ans = max(dist)
        return -1 if ans == INF else ans

############

class Solution:
    def networkDelayTime(self, times, N, K):
        """
        :type times: List[List[int]]
        :type N: int
        :type K: int
        :rtype: int
        """
        K -= 1
        nodes = collections.defaultdict(list)
        for u, v, w in times:
            nodes[u - 1].append((v - 1, w))
        dist = [float('inf')] * N
        dist[K] = 0
        done = set()
        for _ in range(N):
            smallest = min((d, i) for (i, d) in enumerate(dist) if i not in done)[1]
            for v, w in nodes[smallest]:
                if v not in done and dist[smallest] + w < dist[v]:
                    dist[v] = dist[smallest] + w
            done.add(smallest)
        return -1 if float('inf') in dist else max(dist)

const Inf = 0x3f3f3f3f

type pair struct {
	first  int
	second int
}

var _ heap.Interface = (*pairs)(nil)

type pairs []pair

func (a pairs) Len() int { return len(a) }
func (a pairs) Less(i int, j int) bool {
	return a[i].first < a[j].first || a[i].first == a[j].first && a[i].second < a[j].second
}
func (a pairs) Swap(i int, j int)   { a[i], a[j] = a[j], a[i] }
func (a *pairs) Push(x interface{}) { *a = append(*a, x.(pair)) }
func (a *pairs) Pop() interface{}   { l := len(*a); t := (*a)[l-1]; *a = (*a)[:l-1]; return t }

func networkDelayTime(times [][]int, n int, k int) int {
	graph := make([]pairs, n)
	for _, time := range times {
		from, to, time := time[0]-1, time[1]-1, time[2]
		graph[from] = append(graph[from], pair{to, time})
	}

	dis := make([]int, n)
	for i := range dis {
		dis[i] = Inf
	}
	dis[k-1] = 0

	vis := make([]bool, n)
	h := make(pairs, 0)
	heap.Push(&h, pair{0, k - 1})
	for len(h) > 0 {
		from := heap.Pop(&h).(pair).second
		if vis[from] {
			continue
		}
		vis[from] = true
		for _, e := range graph[from] {
			to, d := e.first, dis[from]+e.second
			if d < dis[to] {
				dis[to] = d
				heap.Push(&h, pair{d, to})
			}
		}
	}

	ans := math.MinInt32
	for _, d := range dis {
		ans = max(ans, d)
	}
	if ans == Inf {
		return -1
	}
	return ans
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

743 - Network Delay Time

743. Network Delay Time (Medium)

Solution 1. Dijkstra

Solution 2. Bellman-Ford

All Problems

All Solutions

Welcome to Subscribe On Youtube

743. Network Delay Time (Medium)

Solution 1. Dijkstra

Solution 2. Bellman-Ford

All Problems

All Solutions