代码随想录算法训练营第59天|卡码网 47. 参加科学大会、94. 城市间货物运输 I

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

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

思路依然是 dijkstra 三部曲：
1.第一步，选源点到哪个节点近且该节点未被访问过
2.第二步，该最近节点被标记访问过
3.第三步，更新非访问节点到源点的距离（即更新minDist数组）
只不过之前是通过遍历节点来遍历边，通过两层for循环来寻找距离源点最近节点。这次我们直接遍历边，且通过堆来对边进行排序，达到直接选择距离源点最近节点。
优化部分
1.针对稀疏图，从边的角度使用邻接表进行图存储。
2.选源点到哪个节点近且该节点未被访问过。
我们要选择距离源点近的节点（即：该边的权值最小），所以我们需要一个小顶堆来帮我们对边的权值排序，每次从小顶堆堆顶取边就是权值最小的边。注意：这里的权值是节点到源点的权值，小顶堆需要按照该权值来排序。
小顶堆可以使用优先级队列实现。最小堆中保存着所有未被访问的且权值不是默认最大值的节点。
3.该最近节点被标记访问过
和朴素dijkstra 一样。
4.更新非访问节点到源点的距离（即更新minDist数组）
和朴素dijkstra 一样。唯一的区别是因为使用的是邻接表，则可以直接获取到当前最近节点的所有直连节点，而不用同邻接矩阵一样，需要遍历所有节点再判断。

class Edge {int to; // 邻接顶点int val; // 边的权值Edge(int to,int val) {this.to = to;this.val = val;}
}class MyComparison implements Comparator<Pair<Integer,Integer>> {@Overridepublic int compare(Pair<Integer,Integer> a,Pair<Integer,Integer> b) {return Integer.compare(a.second,b.second); // 权值排序}
}class Pair<U,V> {public final U first; // 节点public final V second; // 节点到源点的最小权值public Pair(U first,V second) {this.first = first;this.second = second;}
}public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt(); // 公共汽车站数量int m = scanner.nextInt(); // 公路数量List<List<Edge>> grid = new ArrayList<>(n+1);for (int i=0;i<=n;i++) {grid.add(new ArrayList<>());}for (int i=0;i<m;i++) {int p1 = scanner.nextInt();int p2 = scanner.nextInt();int val = scanner.nextInt();grid.get(p1).add(new Edge(p2,val));}int start = 1; // 起点int end = n; // 终点// 存储从源点到每个节点的最短距离int[] minDist = new int[n+1];Arrays.fill(minDist,Integer.MAX_VALUE);// 记录顶点是否被访问过boolean[] visited = new boolean[n + 1];// 优先队列中存放Pair<节点，源点到该节点的权值>PriorityQueue<Pair<Integer, Integer>> pd = new PriorityQueue<>(new MyComparison());// 初始化队列，源点到源点的距离为0，所以初始为0pd.add(new Pair<>(start,0));minDist[start] = 0; // 起始点到自身的距离为0while (!pd.isEmpty()) {// 1. 第一步 选源点到哪个节点近且该节点未被访问过Pair<Integer,Integer> cur = pd.poll();if (visited[cur.first]) continue; // 注意：因为最小堆中会存在多个不同权值的相同节点。当该节点的最小权值节点被取出后，//节点会被标记为被访问true。那么该节点的其他权值节点就无用了，直接跳过。// 2. 第二步，该最近节点被标记访问过visited[cur.first] = true;// 3. 第三步，更新非访问节点到源点的距离for (Edge edge:grid.get(cur.first)) {if (!visited[edge.to] && minDist[cur.first] + edge.val < minDist[edge.to]) {minDist[edge.to] = minDist[cur.first] + edge.val;pd.add(new Pair<>(edge.to,minDist[edge.to])); // 将更新后的距源点的权值的节点加入到最小堆中// 注意：这里并没有删除原来权值的相同节点，而是将新的最小权值作为新的节点加入了最小堆中。// 也就是说最小堆中会存在多个不同权值的相同节点。}}}if (minDist[end] == Integer.MAX_VALUE) {System.out.println(-1);} else {System.out.println(minDist[end]);}}
}

2. 卡码网 94. 城市间货物运输 I

题目链接：https://kamacoder.com/problempage.php?pid=1152
文章链接：https://www.programmercarl.com/kamacoder/0094.城市间货物运输I.html

在这里插入图片描述

思路：
使用Bellman_ford算法
核心思想是对所有边进行松弛n-1次操作（n为节点数量），从而求得目标最短路。
针对：图中边的权值可以有负数，且不存在任何负权回路的情况（在有向图中出现有向环且环的总权值为负数）。
对所有边松弛一次，可以计算起点到达 与起点一条边相连的节点 的最短距离。
对所有边松弛两次，可以计算起点到达 与起点两条边相连的节点 的最短距离。
对所有边松弛三次，可以计算起点到达 与起点三条边相连的节点 的最短距离。
若计算起点到终点的最短距离，则需要对边松弛n-1次，其中n为节点数。

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(); // 道路数量List<List<Integer>> roadList = new ArrayList<>();for (int i=0;i<m;i++) {int s = sc.nextInt();int t = sc.nextInt();int v = sc.nextInt();List<Integer> list = new ArrayList<>();list.add(s);list.add(t);list.add(v);roadList.add(list);}int[] minDist = new int[n+1]; // 记录起点到各个节点的最短距离Arrays.fill(minDist,Integer.MAX_VALUE);minDist[1]=0;// 松弛n-1次for(int j=1;j<n;j++) {// 对所有道路进行分析for(int i=0;i<m;i++) {int from = roadList.get(i).get(0);int to = roadList.get(i).get(1);int value = roadList.get(i).get(2);if (minDist[from] != Integer.MAX_VALUE && minDist[from] + value < minDist[to]) {minDist[to] = minDist[from] + value;}}}if (minDist[n] == Integer.MAX_VALUE) {System.out.println("unconnected");} else {System.out.println(minDist[n]);}}
}