113. Network Delay Time
Send a signal from the source at time zero. Each directed edge takes its weight in time units to traverse; determine when the last reachable vertex first receives the signal.
A faster route can beat an earlier-discovered route. Return -1 if any declared vertex never receives the signal.
Example 1
Input
n=4, edges=[[0,1,9],[0,2,1],[2,1,1],[1,3,0]], source=0
Output
2
Explanation: Shortest distances are [0,2,1,2]. The direct cost-nine discovery for vertex one becomes stale.
Example 2
Input
n=3, edges=[[0,1,4]], source=0
Output
−1
Explanation: Vertex two belongs to the declared universe despite not appearing in an edge.
Example 3
Input
n=3, edges=[[0,1,MAX],[1,2,MAX]], source=0
Output
4294967294
Explanation: The sum exceeds int; casting only after addition would be too late.
Constraints
1 <= n <= 1050 <= edge occurrences <= 2 * 1050 <= vertex label < nedges[i].length == 30 <= source < n0 <= weight <= 231 - 1
Hints
Hint 1
What value does each vertex need before you can compute the overall delay?
Hint 2
Nonnegative weights let the minimum tentative label become final.
Hint 3
Use immutable heap snapshots, skip stale costs, relax strictly, then take the maximum or return −1.
Submissions
Your recent submissions for this problem.
Checking sign-in…
Discussion
Ask a question or share an approach. Posts are public; avoid personal information and mark solution spoilers clearly.
No discussion yet. Start the conversation with a question about this problem.
Checking sign-in…
Run your code to check the sample cases, or submit it to check the full validation suite.
A cheaper detour replaces an old heap proposal
4
[[0,1,9],[0,2,1],[2,1,1],[1,3,0]]
0
2