743. Network Delay Time

Problem Statement

Medium

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] = (u_i, v_i, w_i), where u_i is the source node, v_i is the target node, and w_i 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.

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

Constraints:

1 <= k <= n <= 100
1 <= times.length <= 6000
times[i].length == 3
1 <= u_i, v_i <= n
u_i != v_i
0 <= w_i <= 100
All the pairs (u_i, v_i) are unique. (i.e., no multiple edges.)

Java

Source file

class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        List<int[]>[] adj = new List[n+1];
        Set<Integer> vis = new HashSet<>();
        for(int i=1; i<=n; i++)
            adj[i] = new ArrayList<>();
        for(int[] edge: times)
            adj[edge[0]].add(new int[]{edge[1], edge[2]});
        int maxDelay = Integer.MAX_VALUE;
        return djikstra(adj, k, vis, n);
    }

    private int djikstra(List<int[]>[] adj, int src, Set<Integer> vis, int n){
        Queue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[1],b[1]));
        pq.offer(new int[]{src, 0});
        while(!pq.isEmpty()){
            int[] top = pq.poll();
            if(vis.contains(top[0]))
                continue;
            vis.add(top[0]);
            if(vis.size()==n)
                return top[1];
            for(int[] nbr: adj[top[0]])
                pq.offer(new int[]{nbr[0], top[1]+nbr[1]});
        }
        return -1;
    }
}