#743
Network Delay Time
specialist · 715 · lc medium +30 · verified · 59.8% accepted · 8,348 likes · top 58%
Description
A directed weighted graph has n nodes labeled 1 to n, and directed edges times[i] = (ui, vi, wi) representing a connection from node ui to node vi with travel time wi. A signal is broadcast from node k.
Return the time at which the last node receives the signal (i.e., the maximum shortest-path distance from k to any node). If some node cannot be reached, return -1.
Example 1:
Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2
Example 2:
Input: times = [[1,2,1]], n = 2, k = 1
Output: 1
Example 3:
Input: times = [[1,2,1]], n = 2, k = 2
Output: -1
Code
1
2
3