网络延迟时间

/*
 * Problem: Given a list of travel times between directed edges in a network, determine how long it will take for all nodes to receive a signal sent from a starting node K. If not all nodes can receive the signal, return -1.
 * Approach: Use Java Streams to process the input and apply Dijkstra's algorithm. The result will be the maximum time required for the signal to reach all nodes or -1 if not all nodes can be reached.
 */
import java.util.*;
import java.util.stream.Collectors;

public class NetworkDelayTimeStream {
    public int networkDelayTime(int[][] times, int n, int k) {
        // Create an adjacency list
        Map<Integer, List<int[]>> graph = Arrays.stream(times)
            .collect(Collectors.groupingBy(
                time -> time[0],
                Collectors.mapping(time -> new int[]{time[1], time[2]}, Collectors.toList())
            ));
        // PriorityQueue to get the minimum distance node
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
        pq.offer(new int[]{k, 0});
        Map<Integer, Integer> dist = new HashMap<>();
        dist.put(k, 0);
        // Dijkstra's algorithm
        while (!pq.isEmpty()) {
            int[] info = pq.poll();
            int node = info[0], time = info[1];
            if (time > dist.get(node)) continue;
            if (!graph.containsKey(node)) continue;
            for (int[] edge : graph.get(node)) {
                int neighbor = edge[0], d = time + edge[1];
                if (d < dist.getOrDefault(neighbor, Integer.MAX_VALUE)) {
                    dist.put(neighbor, d);
                    pq.offer(new int[]{neighbor, d});
                }
            }
        }
        // Find the maximum distance
        if (dist.size() != n) return -1;
        return dist.values().stream().max(Integer::compareTo).orElse(-1);
    }
}