代码随想录算法训练营第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到源点的时间为0
        
        for (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]);
        
    }
}

原文地址：https://blog.csdn.net/summersnowzgq/article/details/142436589

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！