链式前向星+dijkstra

https://leetcode-cn.com/problems/network-delay-time/submissions/

// n <= 100

class Solution {

    int N = 105, M = 6005;

    // （邻接表-链式前向星）

    int[] w = new int[M];       // 边的权重

    int[] edge = new int[M];    // 边指向的节点

    int[] head = new int[N];    // 存储的是某个节点的链表（节点指向边的结合）的第一个节点

    int[] next = new int[M];    // 表示链表中的下一条边

    int[] dist = new int[N];    // 起点到i的最短路

    boolean[] vis = new boolean[N];

    int n, k;

    int idx = 0;

    int inf = 0x3f3f3f3f;

    void add(int a, int b, int c) {

        // 链表中添加新节点

        w[idx] = c;

        edge[idx] = b;

        next[idx] = head[a];

        head[a] = idx;

        idx++;

    }

    void dijkstra() {

        // 起始先将所有的点标记为「未更新」和「距离为正无穷」

        Arrays.fill(dist, inf);

        Arrays.fill(vis, false);

        // 只有起点最短距离为 0

        dist[k] = 0;

        // (点编号， 到起点的距离)

        PriorityQueue<int[]> pq = new PriorityQueue<>((x, y) -> {

            return x[1] - y[1];

        });

        pq.offer(new int[]{k, 0});

        while (!pq.isEmpty()) {

            int[] poll = pq.poll();

            int index = poll[0], distance = poll[1];

            if (vis[index]) continue;

            vis[index] = true;

            // 标记该点「已更新」，并使用该点更新其他点的「最短距离」

            for (int i = head[index]; i != -1; i = next[i]) {   // 链表最末端都是-1

                int to = edge[i];

                if (dist[to] > dist[index] + w[i]) {

                    dist[to] = dist[index] + w[i];

                    pq.offer(new int[]{to, dist[to]});

                }

            }

        }

    }

    public int networkDelayTime(int[][] times, int n, int k) {

        this.n = n;

        this.k = k;

        // 初始化每个节点的链表的头结点

        Arrays.fill(head, -1);

        // 建图

        for (int[] time: times) {

            int from = time[0], to = time[1], val = time[2];

            add(from, to, val);

        }

        // 最短路

        dijkstra();

        // 遍历答案

        int ans = 0;

        for (int i = 1; i <= n; i++) {

            ans = Math.max(ans, dist[i]);

        }

        return ans == inf? -1: ans;

    }

}

进阶：https://leetcode-cn.com/problems/count-nodes-with-the-highest-score/solution/gong-shui-san-xie-jian-tu-dfs-by-ac_oier-ujfo/

// 链式前向星 求 每一个节点能到达的节点数量

class Solution {

    int[] cnt;

    int N = 100010, M = 100010 * 2;

    int[] head = new int[N];

    int[] next = new int[M];

    int[] edge = new int[M];

    int idx = 0;

    void add(int x, int y) {

        edge[idx] = y;

        next[idx] = head[x];

        head[x] = idx;

        idx++;

    }

    public int countHighestScoreNodes(int[] parents) {

        int n = parents.length;

        cnt = new int[n];

        Arrays.fill(head, -1);

        for (int i = 0; i < n; i++) {

            int from = parents[i];

            int to = i;

            if (from == -1) continue;

            add(from, to);

        }

        // dfs

        dfs(0);

        long maxVal = 0L;

        int maxNum = 0;

        for (int i = 0; i < n; i++) {

            long tmp = 0;

            if (parents[i] == -1) { // 根节点

                long res = 1;

                for (int j = head[i]; j != -1; j = next[j]) {

                    int to = edge[j];

                    res *= cnt[to];

                }

                tmp = res;

            } else if (head[i] == -1) {  // 叶子节点

                tmp = n-1;

            } else {    // 非叶子节点

                long res = 1;

                for (int j = head[i]; j != -1; j = next[j]) {

                    int to = edge[j];

                    res *= cnt[to];

                }

                tmp = res * (n-cnt[i]);

            }

            if (tmp > maxVal) {

                maxVal = tmp;

                maxNum = 1;

            } else if (tmp == maxVal) {

                maxNum++;

            }

        }

        return maxNum;

    }

    // 求以u为根节点的子树的节点数量

    public int dfs(int u) {

        int num = 1;

        // 遍历所有的边

        for (int i = head[u]; i != -1; i = next[i]) {

            int to = edge[i];

            num += dfs(to);

        }

        cnt[u] = num;

        return num;

    }

}

链式前向星+dijkstra的相关教程结束。