LC 743. Network Delay Time

gistfile1.txt

743. Network Delay Time

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] = (ui, vi, wi), 
where ui is the source node, vi is the target node, 
and wi 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 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

class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        //from ,[to, distance]
        Map<Integer, List<int[]>> map = new HashMap<>();
        int[] distance = new int[n + 1];

        for(int i = 0; i <= n; i++) {
            distance[i] = Integer.MAX_VALUE;
        }
        
        for(int[] t: times) {
            map.putIfAbsent(t[0], new ArrayList<>());
            map.get(t[0]).add(new int[]{t[1], t[2]});
        }

        // [current, total distance from beginning]
        Queue<int[]> queue = new LinkedList<>();
        
        queue.offer(new int[]{k, 0});
        distance[k] = 0;
        
        int max = 0;
        while(!queue.isEmpty()) {
            int[] current = queue.poll();
            List<int[]> next = map.get(current[0]);
            if(next == null) continue;
            int currentDistance = current[1];
            
            for(int[] ne: next) {
                int nextDistance = ne[1];
                int nextTag = ne[0];
                if(nextDistance + currentDistance < distance[nextTag]) {
                    distance[nextTag] = nextDistance + currentDistance;
                    queue.offer(new int[]{nextTag, distance[nextTag]});
                }
            }
        }
        
        for(int i = 1; i < distance.length; i++) {
            if(distance[i] == Integer.MAX_VALUE) return -1;
            max = Math.max(max, distance[i]);
        }
        
        return max;
    }
}