ProblemNest
Sign In
You are coding as a Guest. Sign in with your RoleNest account to permanently track your streak, earn XP, and climb the Campus Leaderboard!
Sign In with RoleNest
🔥Network Delay Time: Dijkstra Shortest Path DelayMedium
DAILY PROBLEM OF THE DAY+50 XP • Daily Streak

Solve today's challenge or tackle one of the 3 Super Hard challenges for +150 XP.

MediumTrees & Graphs•Acceptance: 53.6%

Network Delay Time: Dijkstra Shortest Path Delay

Targeted in FAANG & Tech OA:UberGoogleAmazon
Real-World Engineering Context
Core to network packet routing (OSPF protocol), latency SLA analysis across AWS microservices, and Uber ETA calculation algorithms.
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`.

Sample Test Cases

Input: [[[2,1,1],[2,3,1],[3,4,1]],4,2]
Expected: 2
Input: [[[1,2,1]],2,1]
Expected: 1
Input: [[[1,2,1]],2,2]
Expected: -1

Constraints

  • 1 <= k <= n <= 100
  • 1 <= times.length <= 6000
  • times[i].length == 3
  • 1 <= ui, vi <= n
  • ui != vi
  • 0 <= wi <= 100
  • All the pairs (ui, vi) are unique.
Recruiter Fast-Track ReferralVerified Candidate
Direct pipeline to Google, Amazon, Microsoft, Swiggy, & Uber recruiters
DevScore: 750/1000

Top DevScore profiles bypass resume screening filters. Every verified problem solve writes authentic proof-of-work to your profile and dispatches you directly into employer inboxes on RoleNest.

Explore 5,000+ Direct ATS Openings on RoleNest ↗✓ Direct Referral Active