Solvarch
DSA ProblemsProgressPlanRoadmapsReviewCheat SheetsCompaniesSystem DesignCS FundamentalsQuestion Bank
Theme
Problems

Network Delay Time

Medium
graphdijkstrashortest-pathheap

A network has n nodes (1…n) and directed edges u v w meaning a signal takes w time to travel u → v. A signal starts at node k. Return the time for all nodes to receive it, or -1 if some node never does.

Input

  • Line 1: n m
  • Next m lines: u v w
  • Last line: the start node k

Output: the total time, or -1.

Example 1
Input:
4 3
2 1 1
2 3 1
3 4 1
2
Output:
2
Example 2
Input:
2 1
1 2 1
1
Output:
1
Example 3
Input:
2 1
1 2 1
2
Output:
-1

Constraints

  • 1 ≤ n ≤ 100
  • 1 ≤ m ≤ 6000
  • 1 ≤ w ≤ 100
Watch a video walkthrough

Run your code against the sample tests, or Submit to run the full suite.