743. Network Delay Time

Version #1 Dijastra

1 BUG-> it is possible that a node be added to minHeap more than once
Since we are marking visited when we are polling it -> it is possible that one node is not polled yet and it is added one more time with an larger distance
So we have to check visited in to place
-> right after we poll out one node
-> before we add a node to minHeap


25.65 %
class Solution {
    /*
times[i] = (u, v, w), where u is the source node, v is the target node,
and w is the time it takes for a signal to travel from source to target.
*/
public int networkDelayTime(int[][] times, int N, int K) {
//  source        target   weight
Map<Integer, Map<Integer, Integer>> graph = new HashMap<>();
for (int[] time : times) {
// time[0]-source, time[1]-target, time[2]-weight
graph.computeIfAbsent(time[0], weightMap -> new HashMap<>()).put(time[1], time[2]);
}
int max = Integer.MIN_VALUE;
boolean[] visited = new boolean[N + 1]; // since nodes are 1 indexed
// a[0]-current node, a[1]-weight from source
PriorityQueue<int[]> minHeap = new PriorityQueue<>(Comparator.comparing(a -> a[1]));
minHeap.offer(new int[]{K, 0});
while (!minHeap.isEmpty()) {
int[] curr = minHeap.poll();
int index = curr[0], distance = curr[1];
if (visited[index]) continue;
// System.out.println(index + " " + distance);
max = Math.max(max, distance);
visited[index] = true;
Map<Integer, Integer> neighbors = graph.get(index);
if (neighbors != null) {
for (int neighbor : neighbors.keySet()) {
if (!visited[neighbor]) {
minHeap.offer(new int[]{neighbor, distance + neighbors.get(neighbor)});
}
}
}
}
for (int i = 1; i < visited.length; i++) {
if (!visited[i]) return -1;
}
return max;
}
}