代码随想录算法训练营第58天|卡码网 117. 软件构建、47. 参加科学大会

1. 卡码网 117. 软件构建

题目链接：https://kamacoder.com/problempage.php?pid=1191
文章链接：https://www.programmercarl.com/kamacoder/0117.软件构建.html

在这里插入图片描述
思路：使用BFS
BFS的实现思路：
拓扑排序的过程，其实就两步：
1.找到入度为0 的节点，加入结果集
2.将该节点从图中移除
循环以上两步，直到所有节点都在图中被移除了。
结果集的顺序，就是我们想要的拓扑排序顺序（结果集里顺序可能不唯一）

import java.util.*;public class Main {public static void main (String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt(); //  文件数量int m = sc.nextInt(); //  依赖关系int[] inDegree = new int[n];Map<Integer,List<Integer>> map = new HashMap<>();for (int i=0;i<m;i++) {int s = sc.nextInt();int t = sc.nextInt();inDegree[t]++;List<Integer> list = map.getOrDefault(s,new ArrayList<>());list.add(t);map.put(s,list);}Deque<Integer> deque = new ArrayDeque<>();for (int i=0;i<n;i++) {if (inDegree[i] == 0) {deque.offer(i); // 注意：使用队列保存入度为0的节点。}}List<Integer> res = new ArrayList<>(); // 结果集while (!deque.isEmpty()) {// 1.找到入度为0的节点，并加入结果集int s = deque.poll();res.add(s);List<Integer> files = map.get(s); // 获取所有依赖s的集合if (files == null) {continue;}for (Integer t:files) {// 2.将s节点从图中移除inDegree[t]--; if (inDegree[t] == 0) {deque.offer(t);}}}if (res.size() != n) {System.out.println(-1);} else {for (int i=0;i<res.size()-1;i++) {System.out.print(res.get(i));System.out.print(" ");}System.out.print(res.get(res.size() - 1));}}
}

2. 卡码网 47. 参加科学大会

题目链接：https://kamacoder.com/problempage.php?pid=1047
文章链接：https://www.programmercarl.com/kamacoder/0047.参会dijkstra朴素.html

在这里插入图片描述

思路：本题是求最短路径问题。可以使用dijkstra算法。
dijkstra算法：在有权图（权值非负数）中求从起点到其他节点的最短路径算法。
dijkstra三部曲：
1.第一步，选源点到哪个节点近且该节点未被访问过
2.第二步，该最近节点被标记访问过
3.第三步，更新非访问节点到源点的距离（即更新minDist数组）
minDist数组用来记录每一个节点距离源点的最小距离。这里的源点指的是起始点，即本题中的节点1。
需要注意两点：

dijkstra 算法可以同时求起点到所有节点的最短路径
权值不能为负数（注意这里）。

import java.util.*;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt(); // 公共汽车站数量int m = sc.nextInt(); // 公路数量int[][] timeArray = new int[n+1][n+1];for (int i=0;i<n;i++) {Arrays.fill(timeArray[i],Integer.MAX_VALUE);}// 构建邻接矩阵for (int i=0;i<m;i++) {int s = sc.nextInt();int e = sc.nextInt();int v = sc.nextInt();timeArray[s][e] = v; // 注意：这里只对[s][e]填值，而最小生成树也会对[e][s]填值}// 节点是否被访问到boolean[] visited = new boolean[n+1];// 所有节点到源点到最短时间int[] minTime = new int[n+1];Arrays.fill(minTime,Integer.MAX_VALUE);minTime[1] = 0; // 节点1到源点的时间为0for (int t=1;t<=n;t++) {// 1. 寻找所有未访问节点中到源点最短时间的节点int min = Integer.MAX_VALUE;int cur = 1;for (int i=1;i<=n;i++) {if (!visited[i] && minTime[i] < min) {min = minTime[i];cur = i;}}// 2. 标记被访问visited[cur] = true;// 3. 更新所有未被访问节点到源点的最短时间// 注意：这里只更新与cur直连的节点 由其判断：timeArray[cur][i] != Integer.MAX_VALUE for (int i=1;i<=n;i++) {if (!visited[i]  && timeArray[cur][i] != Integer.MAX_VALUE && timeArray[cur][i] + minTime[cur] < minTime[i]) {minTime[i] = timeArray[cur][i] + minTime[cur];}}}// 未访问到最终节点if (minTime[n] == Integer.MAX_VALUE) {System.out.println(-1);return;}System.out.println(minTime[n]);}
}