Apply Dijkstra's algorithm from the origin node to compute shortest distances to all nodes.

Network Delay Time

medium

Acceptance: 50%

GraphsBFS

A directed weighted graph of n nodes has edges described as (source, destination, weight). A signal is broadcast from a given origin node. Determine the earliest time at which every node in the network has received the signal, or return -1 if some nodes are unreachable.

Examples

Example 1:

Input:times = [[1,2,3],[1,3,5],[2,3,1]], n = 3, k = 1

Output:4

Explanation: From node 1: reach node 2 in 3 and node 3 in min(5, 3+1) = 4. The latest arrival is 4.

Hints

1234567

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

Network Delay Time

Examples

Hints

Related Problems