Marc Lester Tan

class Solution {
    public int networkDelayTime(int[][] times, int N, int K) {
        // use djikstra
        // make an adjancecy map
        // use priority queue to process nodes starting from K
        // then start processing other neighbors
        
        
        int result = 0;
        
        final Map<Integer, List<int[]>> graph = new HashMap<>();
        for(int[] time : times){
            if(!graph.containsKey(time[0])){
                graph.put(time[0], new ArrayList<>());                
            }
            graph.get(time[0]).add(new int[]{time[1], time[2]});
        }
        
        final PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
        final Map<Integer, Integer> distMap = new HashMap<>();
       
        pq.add(new int[] {K, 0});
        
        while(!pq.isEmpty()){
            int[] current = pq.poll();
            int d = current[1];
            int node = current[0];
            
            if(distMap.containsKey(node)) continue;
            
            distMap.put(node, d);
            
            // explore the neighbors
            if(graph.containsKey(node)){
                final List<int[]> neighbors = graph.get(node);    
                for(int[] neighbor : neighbors){
                    int d2 = neighbor[1];
                    int n2 = neighbor[0];
                    
                    if(!distMap.containsKey(n2)){
                        pq.add(new int[]{n2, d + d2});
                    }
                }
            }
        }
        
        if(distMap.size() != N) return -1;
        
        for(Map.Entry<Integer, Integer> entry: distMap.entrySet()){
            result = Math.max(result, entry.getValue());
        }
        
        return result;
    }
}