[Leetcode] 743. Network Delay Time

https://leetcode.com/problems/network-delay-time/description/

intial

typical dijkstra but i made few mistakes since its first time in a while

1) no visited list needed, u should revisit nodes if cur_cost+dist is less than the already recorded cost to visit that node
2) first time in java so more complex impl than py

sol

class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a->a[0]));
        int[] dist = new int[n+1];
        Arrays.fill(dist,Integer.MAX_VALUE);
        dist[k]=0;
        pq.offer(new int[]{0,k});

        List<List<int[]>> graph = new ArrayList<>();
        for(int i=0;i<n+1;i++) graph.add(new ArrayList<>());
        for(int[] time:times){
            graph.get(time[0]).add(new int[]{time[1],time[2]});
        }
        int ans=0;

        while(!pq.isEmpty()){
            int[] polled = pq.poll();
            int node=polled[1], cur_dist=polled[0];
            if (dist[node]<cur_dist) continue;
            for(int[] info: graph.get(node)){
                int neigh=info[0],cost=info[1];
                if(dist[neigh]>cost+cur_dist){
                    pq.offer(new int[]{cost+cur_dist,neigh});
                    dist[neigh]=cost+cur_dist;
                }
            }
        }
        for (int i = 1; i <= n; i++) {
            if (dist[i] == Integer.MAX_VALUE) return -1; // unreachable node
            ans = Math.max(ans, dist[i]);
        }
        return ans;
    }
}

complexity

v+e time and space

nope dijkstra is n+e log n time
n+e space