算法：全部电脑感染病毒的最少时间

一、题目 §

题目：
一个局域网内有很多台电脑，分别标注为 0 \~ N-1 的数字。相连接的电脑距离不一样，所以感染时间不一样，感染时间用 t 表示。
其中网络内一台电脑被病毒感染，求其感染网络内所有的电脑最少需要多长时间。如果最后有电脑不会感染，则返回-1。
给定一个数组 times 表示一台电脑把相邻电脑感染所用的时间。如：path[i] = {i, j, t} 表示：电脑 i->j，电脑 i 上的病毒感染 j，需要时间 t。

输入：
第一个参数：局域网内电脑个数N，1 ≤ N ≤ 200；
第二个参数：总共多少条网络连接
第三个 2 1 1 表示2->1时间为1
第六行：表示病毒最开始所在电脑号2

输出：
感染网络内所有的电脑最少需要多长时间

示例：
输入：
4
3
2 1 1
2 3 1
3 4 1
2
输出：
2

二、题解 §

1. 使用迪杰斯特拉算法（Dijkstra）求加权图中找从源点到目标点之间的最短路径。本题需要求从源点到所有其他节点的最短路径，取最大的就是遍历所有节点的最小路径
2. 本解法没有考虑有向图有环

package org.stone.study.algo.ex202411;
 
import java.util.*;
 
public class VirusInfectTime {
 
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 4
        int n = Integer.parseInt(scanner.nextLine());
        // 3
        int m = Integer.parseInt(scanner.nextLine());
 
        int[][] conn = new int[m][3];
        //  2 1 1
        //  2 3 1
        //  3 4 2
        for(int i = 0; i < m; i++) {
            conn[i] = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        }
        // 2
        int src = scanner.nextInt();
        int ans = getMinInfectTime(n, m, conn, src);
        // 3
        System.out.println(ans);
    }
 
    /**
     * djikstra 算法找到遍历有向图全部节点最短路径。不能遍历全部节点时返回-1；能遍历全部时找花费时间最长的节点就是图全部遍历的最小时间
     * 没有考虑有环的有向图
     * @param n
     * @param m
     * @param conn
     * @param src
     * @return
     */
    private static int getMinInfectTime(int n, int m, int[][] conn, int src) {
        // 构建有向图的邻接表
        Map<Integer, List<int[]>> graph = new HashMap<>();
        for(int[] edge : conn) {
            int u = edge[0];
            int v = edge[1];
            int w = edge[2];
            graph.computeIfAbsent(u, k -> new ArrayList<>()).add(new int[]{v, w});
        }
 
        // dijkstra 算法找到最短路径
        PriorityQueue<int[]> queue = new PriorityQueue<>(Comparator.comparingInt(e -> e[0]));
        int[] dist = new int[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        queue.add(new int[]{0, src});
        dist[src] = 0;
        while(!queue.isEmpty()) {
            int[] cur = queue.poll();
            int curTime = cur[0];
            int curNode = cur[1];
 
            // 剪枝:其他路径可能修改过最短距离
            if(curTime > dist[curNode]) {
                continue;
            }
            for(int[] next : graph.getOrDefault(curNode, Collections.emptyList())) {
                int nextNode = next[0];
                int nextTime = next[1];
                if(curTime + nextTime < dist[nextNode]) {
                    dist[nextNode] = curTime + nextTime;
                    queue.add(new int[]{dist[nextNode], nextNode});
                }
            }
 
        }
 
        // 找到最长的最短路径，如果有节点未遍历到返回-1
        int ans = 0;
        for(int i = 1; i <= n; i++) {
            if(dist[i] == Integer.MAX_VALUE) {
                return -1;
            }
            ans = Math.max(ans, dist[i]);
        }
 
        return ans;
    }
 
}