Medium

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 minimum 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`.

Examples

Input:times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2

Output:2

From node 2, the signal reaches nodes 1 and 3 in time 1. From node 3, the signal reaches node 4 in time 1. So the maximum time taken is 1 + 1 = 2.

Input:times = [[1,2,1]], n = 2, k = 1

Output:1

The signal reaches node 2 in time 1.

Input:times = [[1,2,1]], n = 2, k = 2

Output:-1

Node 1 can never receive the signal because the edge is directed from 1 to 2.

Constraints

1 <= k <= n <= 100
1 <= times.length <= 6000
times[i].length == 3
1 <= ui, vi <= n
ui != vi
0 <= wi <= 100
All the pairs (ui, vi) are unique. (i.e., no multiple edges.)

Dijkstra's Algorithm

Approach

We need to find the shortest path from the source node `k` to all other nodes. The answer is the maximum of these shortest paths. Dijkstra's algorithm uses a priority queue (min-heap) to explore the graph efficiently. We start by pushing `(0, k)` onto the heap. We continually extract the node with the minimum time. If it has not been visited, we mark it visited, update our maximum time, and push all its neighbors onto the heap with the accumulated time. If we visit all `n` nodes, we return the maximum time. Otherwise, if the heap empties and we haven't visited all nodes, some nodes are unreachable, so we return `-1`.

Complexity Analysis

Time Complexity

O(E log V)

Space Complexity

O(V + E)

Time complexity is O(E log V) because each edge could be pushed to the heap, and heap operations take O(log V) time (where V is the number of nodes, which bounds the heap size). Space complexity is O(V + E) for the adjacency list and priority queue.

Solution.java

1class Solution {2    public int networkDelayTime(int[][] times, int n, int k) {3        // Build adjacency list: node -> List of (neighbor, weight)4        Map<Integer, List<int[]>> adj = new HashMap<>();5        for (int i = 1; i <= n; i++) {6            adj.put(i, new ArrayList<>());7        }8        for (int[] time : times) {9            adj.get(time[0]).add(new int[]{time[1], time[2]});10        }11        12        // Min-heap to store (time, node)13        PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[0] - b[0]);14        minHeap.offer(new int[]{0, k});15        16        Set<Integer> visited = new HashSet<>();17        int maxTime = 0;18        19        while (!minHeap.isEmpty()) {20            int[] curr = minHeap.poll();21            int time = curr[0];22            int node = curr[1];23            24            if (visited.contains(node)) {25                continue;26            }27            28            visited.add(node);29            maxTime = Math.max(maxTime, time);30            31            for (int[] edge : adj.get(node)) {32                int neighbor = edge[0];33                int weight = edge[1];34                if (!visited.contains(neighbor)) {35                    minHeap.offer(new int[]{time + weight, neighbor});36                }37            }38        }39        40        return visited.size() == n ? maxTime : -1;41    }42}