New update is available. Click here to update.

Network Delay Time

Posted: 4 Apr, 2021
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

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.

Note:
The signal which starts from the source node travels to all nodes simultaneously.
Input Format:
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’.
Output Format:
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.
Note:
You don’t need to print anything; It has already been taken care of. Just implement the function.
Constraints:
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