Network Delay Time
Posted: 4 Apr, 2021
You have been given a network of ‘N’ nodes from 1 to ‘N’ and ‘M’ edges. For each edge, you are given three values (ui, vi, wi) where “ui” and “vi” denote the nodes and “wi” denotes an integer value which represents the time taken by a signal to travel from “ui” to “vi”. Now, you are supposed to find the time which a signal takes to travel from a given node ‘K’ to all nodes. If it is impossible for all nodes to receive the signal then print -1.
The signal which starts from the source node travels to all nodes simultaneously.
The first line contains a single integer ‘T’ representing the number of test cases. The first line of each test case will contain three space-separated integers ‘N’, ‘M’ and ‘K’ where ‘N’ is the number of the nodes in the network, and ‘M’ is the number of edges and ‘K’ is the source node. The next ‘M’ lines contain three space-separated integers (u, v, w) which denote a directed edge in the network from node ‘u’ to node ‘v’ with weight ‘w’.
For each test case, print a single line containing a single integer denoting the time it takes for all the ‘N’ nodes to receive the signal. Print -1 if it is impossible for all nodes to receive the signal from the source node. The output for every test case will be printed in a separate line.
You don’t need to print anything; It has already been taken care of. Just implement the function.
1 <= T <= 50 1 <= N <= 3000 0 <= M <= 10000 1 <= u, v, K <= N 0 <= w <= 10000 Where ‘T’ is the number of test cases, ‘N’ is the number of the nodes in the network, and ‘M’ is the number of edges and ‘K’ is the source node and ‘u’, ‘v’, ‘k’ are the nodes of the network and ‘w’ is the weight of the edges. Time limit: 1 sec