743. 网络延迟时间

解法一：Dijkstra

import java.util.*;
class Solution {
    public int networkDelayTime(int[][] times, int N, int K) {
        Point[] points = new Point[N + 1];
        for (int i = 1; i <= N; ++i) {
            points[i] = new Point(i);
        }
        for (int[] time : times) {
            points[time[0]].next.add(new int[]{time[1], time[2]});
        }
        Comparator<Integer> comparator = new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return points[o1].dis - points[o2].dis;
            }
        };
        PriorityQueue<Integer> heap = new PriorityQueue<Integer>(comparator);
        points[K].dis = 0;
        heap.offer(K);
        int cnt = 0;
        while (!heap.isEmpty()) {
            int id = heap.poll();
            if (points[id].isVisited) {
                continue;
            }
            if (++cnt == N) {
                break;
            }
            points[id].isVisited = true;
            for (int[] line : points[id].next) {
                if (points[line[0]].isVisited) {
                    continue;
                }
                points[line[0]].dis = Math.min(points[line[0]].dis, points[id].dis + line[1]);
                heap.offer(line[0]);
            }
        }
        int max = 0;
        for (int i = 1; i <= N; ++i) {
            max = Math.max(max, points[i].dis);
        }
        if (max == Integer.MAX_VALUE) {
            return -1;
        } else {
            return max;
        }
    }
}
class Point {
    int id;
    int dis;
    boolean isVisited;
    List<int[]> next;
    Point(int id) {
        this.id = id;
        dis = Integer.MAX_VALUE;
        isVisited = false;
        next = new ArrayList<>();
    }
}

解法二：SPFA

import java.util.*;
class Solution {
    public int networkDelayTime(int[][] times, int N, int K) {
        Point[] points = new Point[N + 1];
        for (int i = 1; i <= N; ++i) {
            points[i] = new Point(i);
        }
        for (int[] time : times) {
            points[time[0]].next.add(new int[]{time[1], time[2]});
        }
        Queue<Integer> queue = new LinkedList<>();
        points[K].dis = 0;
        queue.offer(K);
        while (!queue.isEmpty()) {
            int id = queue.poll();
            points[id].isVisited = false;
            for (int[] line : points[id].next) {
                int cur = points[id].dis + line[1];
                if (points[line[0]].dis > cur) {
                    points[line[0]].dis = cur;
                    if (!points[line[0]].isVisited) {
                        points[line[0]].isVisited = true;
                        queue.offer(line[0]);
                    }
                }
            }
        }
        int max = 0;
        for (int i = 1; i <= N; ++i) {
            max = Math.max(max, points[i].dis);
        }
        if (max == Integer.MAX_VALUE) {
            return -1;
        } else {
            return max;
        }
    }
}
class Point {
    int id;
    int dis;
    boolean isVisited;
    List<int[]> next;
    Point(int id) {
        this.id = id;
        dis = Integer.MAX_VALUE;
        isVisited = false;
        next = new ArrayList<>();
    }
}