当前位置：首页 > news >正文

代码随想录算法训练营第五十一天

news 2025/5/29 14:58:57

卡码网题目:

47. 参加科学大会（第六期模拟笔试）
94. 城市间货物运输 I

其他:

今日总结
往期打卡

47. 参加科学大会（第六期模拟笔试）

跳转: 47. 参加科学大会（第六期模拟笔试）

学习: 代码随想录公开讲解

问题:

小明是一位科学家，他需要参加一场重要的国际科学大会，以展示自己的最新研究成果。

小明的起点是第一个车站，终点是最后一个车站。然而，途中的各个车站之间的道路状况、交通拥堵程度以及可能的自然因素（如天气变化）等不同，这些因素都会影响每条路径的通行时间。

小明希望能选择一条花费时间最少的路线，以确保他能够尽快到达目的地。

思路:

模拟链表 + 小根堆排序

昨日超时原来是因为使用了Lambda表达式,大量调用的场景能用匿名类还是不要使用Lambda表达式了
在这里插入图片描述

复杂度:

时间复杂度: $O(N^2)$
空间复杂度: $O ((N + M) l o g N)$

代码:

import java.util.*;class MyCompare implements Comparator<int[]>{@Overridepublic int compare(int[] o1, int[] o2) {return o1[1] - o2[1];}
}class Main {public static void main(String[] args) {int INF = 0x3f3f3f3f;Scanner scanner = new Scanner(System.in);int N = scanner.nextInt();int M = scanner.nextInt();// int[][] w = new int[N + 1][N + 1];// for(int i = 1;i <= N;i++){//     for(int j = 1;j <= N;j++){//         w[i][j] = i == j ? 0 : INF;//     }// }int[] head = new int[N + 1];Arrays.fill(head, -1);int[] e = new int[M];int[] w = new int[M];int[] next = new int[M];for (int i = 0; i < M; i++) {int a = scanner.nextInt();int b = scanner.nextInt();int c = scanner.nextInt();// w[a][b] = c;{e[i] = b;w[i] = c;next[i] = head[a];head[a] = i;}}boolean[] vis = new boolean[N + 1];int[] dist = new int[N + 1];Arrays.fill(dist, INF);dist[1] = 0;// System.arraycopy(w[1], 0, dist, 0, N + 1);PriorityQueue<int[]> priorityQueue =new PriorityQueue<>(new MyCompare());priorityQueue.offer(new int[] {1, 0});while (!priorityQueue.isEmpty()) {int cur = priorityQueue.poll()[0];if (vis[cur]) continue;vis[cur] = true;for (int i = head[cur]; i != -1; i = next[i]) {int j = e[i];int tmp = dist[cur] + w[i];if (!vis[j] && tmp < dist[j]) {dist[j] = tmp;priorityQueue.offer(new int[] {j, tmp});}}}// for (int i = 1; i < N; i++) {//     int min = 0;//     for (int j = 2; j <= N; j++) {//         if (vis[j]) continue;//         if (min == 0 || dist[j] < dist[min]) {//             min = j;//         }//     }////     vis[min] = true;////     for (int j = 2; j <= N; j++) {//         if (vis[j]) continue;//         if (dist[j] > w[min][j] + dist[min]) {//             dist[j] = w[min][j] + dist[min];//         }//     }// }System.out.println(dist[N] >= INF / 2 ? -1 : dist[N]);}
}

94. 城市间货物运输 I

跳转: 94. 城市间货物运输 I

学习: 代码随想录公开讲解

问题:

某国为促进城市间经济交流，决定对货物运输提供补贴。共有 n 个编号为 1 到 n 的城市，通过道路网络连接，网络中的道路仅允许从某个城市单向通行到另一个城市，不能反向通行。

网络中的道路都有各自的运输成本和政府补贴，道路的权值计算方式为：运输成本 - 政府补贴。权值为正表示扣除了政府补贴后运输货物仍需支付的费用；权值为负则表示政府的补贴超过了支出的运输成本，实际表现为运输过程中还能赚取一定的收益。

请找出从城市 1 到城市 n 的所有可能路径中，综合政府补贴后的最低运输成本。如果最低运输成本是一个负数，它表示在遵循最优路径的情况下，运输过程中反而能够实现盈利。

城市 1 到城市 n 之间可能会出现没有路径的情况，同时保证道路网络中不存在任何负权回路。

思路:

遍历所有边 n-1次,题目中没有负环,所以无需额外判断,如果有就再遍历n-1次把所有更新过的全部都更新成负无穷.
为什么是n-1次?
因为遍历所有路径,如果都无法更新,就说明前节点都更新到最短路了,所以每次至少更新1个节点.
n-1次能更新n-1层,不算起点所有节点刚好n-1个,就是n-1层.极端情况就是逆序链,每次遍历在结尾更新.

复杂度:

时间复杂度: $O (M)$
空间复杂度: $O (NM)$

代码:

import java.util.*;class Edge{int u,v,w;Edge(int _u,int _v,int _w){u = _u;v = _v;w = _w;}
}public class Main{public static void main(String[] args){int INF = 0x3f3f3f3f;Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int m = scanner.nextInt();// int[][] w = new int[n + 1][n + 1];// for(int i = 1; i <= n;i++)//     for(int j = 1;j <= n;j++){//         w[i][j] = i == j ? 0 : INF;//     }List<Edge> edges = new ArrayList<>();for(int i = 0;i < m;i++){int u = scanner.nextInt();int v = scanner.nextInt();int weight = scanner.nextInt();edges.add(new Edge(u,v,weight));}int[] dist = new int[n + 1];Arrays.fill(dist,INF);dist[1] = 0;for(int i = 0;i < n;i++){for(Edge e : edges){int tmpDist = e.w + dist[e.u];if(dist[e.v] > tmpDist) dist[e.v] = tmpDist;}}System.out.println(dist[n] >= INF / 2 ?"unconnected":dist[n]);}
}