Network Delay Time Problem

Network Delay Time Problem — ExecCode Medium DSA Practice

Solve the Network Delay Time problem on ExecCode. Free online medium DSA practice in Arrays - Basics. Write and run code in Java, C++, Python — no signup required to run.

Problem description

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.

Examples

Input times = [[1, 2, 2], [1, 3, 5], [2, 3, 1], [2, 4, 3], [3, 5, 2], [4, 6, 1], [5, 6, 2]], n = 6, k = 1; Output 6. Input times = [[1, 2, 1]], n = 2, k = 1; Output 1. 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 pairs (ui, vi) are unique

Practice Network Delay Time free on ExecCode. Browse DSA problems, topic map, and placement guides.