更多关于刷题的内容欢迎订阅我的专栏华为刷题笔记

该专栏题目包含两部分：
100 分值部分题目
200 分值部分题目
所有题目都会陆续更新，订阅防丢失

题目描述

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

输入描述

4
3
2 1 1
2 3 1
3 4 1
2

输出描述

2

补充说明：

第一个参数:局域网内电脑个数N 1<=N<=200;
第二个参数：总共多少条网络连接
第三个 1 2 1 表示1->2时间为1
第七行：表示病毒最开始所在的电脑号1

示例1

输入：

4
3
2 1 1
2 3 1
3 4 1
2

输出：

2

题解

dijkstra算法

https://www.bilibili.com/video/BV1q4411M7r9/?spm_id_from=333.880.my_history.page.click&vd_source=8c30d3bb47fd24185cf1bd4501038841

源码

import java.util.*;

public class ComputerVirus {

	static Input input;
	static {
		input = new Input("4\n" +
				"3\n" +
				"2 1 1\n" +
				"2 3 1\n" +
				"3 4 1\n" +
				"2");
	}

	static boolean[] cs;
	static int[] distance;
	static int[] parent;
	static Map<Integer, List<Path>> map;
	public static void main(String[] args) {
		int n = Integer.parseInt(input.nextLine())+1;
		distance = new int[n];
		Arrays.fill(distance, Integer.MAX_VALUE);
		parent = new int[n];
		Arrays.fill(parent, -1);
		cs = new boolean[n];
		int pathes = Integer.parseInt(input.nextLine()) ;

		map = new HashMap<>();
		for (int i = 0; i < pathes; i++) {
			String[] ss = input.nextLine().split(" ");
			int  from = Integer.parseInt(ss[0]);
			int  to = Integer.parseInt(ss[1]);
			int time = Integer.parseInt(ss[2]);
			List<Path> orDefault = map.getOrDefault(from, new ArrayList<>());
			orDefault.add(new Path(from, to, time));
			map.put(from,orDefault);
		}

		int start = Integer.parseInt(input.nextLine());
		cs[start] = true;
		distance[start] = 0;
		dfs(map.get(start));

		boolean flag = true;
		int max = 0;
		for (int i = 1; i < cs.length; i++) {
			if (!cs[i]) {flag = false;}
			max = Math.max(max, distance[i]);
		}
		if (!flag) {
			System.out.println(-1);
		} else {
			System.out.println(max);
		}
	}

	public static void dfs(List<Path> path) {
		if (path == null || path.size() == 0) {
			return;
		}
		for (int i = 0; i < path.size(); i++) {
			Path p = path.get(i);
			int dis = distance[p.i] + p.t;
			if (cs[p.j]) {
				if (dis < distance[p.i]) {
					distance[p.i] = dis;
					parent[p.j] = p.i;
				}
			} else {
				cs[p.j] = true;
				distance[p.j] = dis;
				parent[p.j] = p.i;
			}
			dfs(map.get(p.j));
		}
	}

	static class Path{
		public int i;
		public int j;
		public int t;
		public Path(int i, int j, int t){
			this.i = i;
			this.j = j;
			this.t = t;
		}
	}
}