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

一、题目

1
题目：一个局域网内有很多台电脑，分别标注为 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输出：感染网络内所有的电脑最少需要多长时间示例：输入：432 1 12 3 13 4 12输出：2
1
题目：一个局域网内有很多台电脑，分别标注为 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输出：感染网络内所有的电脑最少需要多长时间示例：输入：432 1 12 3 13 4 12输出：2

二、题解

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