_743. Network Delay Time.md

743. Network Delay Time

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : July 28, 2024

Last updated : July 28, 2024

---

Related Topics : Depth-First Search, Breadth-First Search, Graph, Heap (Priority Queue), Shortest Path

Acceptance Rate : 55.86 %

---

Solutions

• m743.java
• m743.py

Java

m743.java

import java.awt.Point;

class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        boolean[] reached = new boolean[n + 1];
        reached[0] = true;

        HashMap<Integer, ArrayList<Point>> adj = new HashMap<>(n); 
        for (int[] time : times) {
            if (!adj.containsKey(time[0])) {
                adj.put(time[0], new ArrayList<Point>());
            }
            adj.get(time[0]).add(new Point(time[1], time[2]));
        }

        PriorityQueue<Point> pq = new PriorityQueue<>(20, (a, b) -> a.x - b.x);
        pq.add(new Point(0, k));

        int maxDelay = 0;
        while (!pq.isEmpty()) {
            Point curr = pq.poll();

            if (reached[curr.y]) {
                continue;
            }
            maxDelay = curr.x;
            reached[curr.y] = true;

            if (!adj.containsKey(curr.y))
                continue;
            for (Point nxt : adj.get(curr.y)) {
                if (!reached[nxt.x]) {
                    pq.add(new Point(curr.x + nxt.y, nxt.x));
                }
            }
        }

        for (boolean b : reached) {
            if (!b)
                return -1;
        }
        return maxDelay;

    }
}

Python

m743.py

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        reached = [True] + [False for _ in range(n)]

        adj = defaultdict(list)
        for u, v, w in times :
            adj[u].append((v, w))
        
        # (delay when reached, node reached)
        toVisit = [(0, k)]
        maxDelay = 0
        while toVisit :
            delay, curr = heapq.heappop(toVisit)

            if reached[curr] :
                continue

            maxDelay = delay
            reached[curr] = True

            for nxt, w in adj[curr] :
                # This if statement is in theory doubled
                # but provides benefits if a node is queued up
                # in the PQ twice
                if not reached[nxt] :
                    heapq.heappush(toVisit, (delay + w, nxt))

        if any(not x for x in reached) :
            return -1
        return maxDelay