Network Delay Time

Problem

Nodes are labeled 1 to n. times is a list of [u, v, w] directed edges. Starting from node k, find the time for all n nodes to receive a signal: the maximum shortest-path distance from k.

Return -1 if some node is unreachable. A single node network takes 0 time.

Hint

The answer is the largest finite distance after running Dijkstra.

Test cases

case 1

in: [4,[[2,1,1],[2,3,1],[3,4,1]],2]

expected: 2

case 2

in: [2,[[1,2,1]],2]

expected: -1

case 3

in: [1,[],1]

expected: 0

case 4

in: [3,[[1,2,4],[1,3,2],[3,2,1]],1]

expected: 3

Starter codePython

import heapq
def network_delay_time(n, times, k):
    # Your code here
    pass

4 test cases · run your code against them in the editor