郑州网站推广方案,凤山网站seo,极客学院 网站建设,网站建设发展题目 某通信网络中有N个网络结点#xff0c;用1到N进行标识。网络通过一个有向无环图.表示,其中图的边的值表示结点之间的消息传递时延。 现给定相连节点之间的时延列表times[]{u#xff0c;v#xff0c; w)#xff0c;其中u表示源结点#xff0c;v表示目的结点#xff0…题目 某通信网络中有N个网络结点用1到N进行标识。网络通过一个有向无环图.表示,其中图的边的值表示结点之间的消息传递时延。 现给定相连节点之间的时延列表times[]{uv w)其中u表示源结点v表示目的结点w表示u和v之间的消息传递的时延。请计算给定源结点到目的结点的最小传输时延如果目的结点不可达返回-1。 注:N的取值范围为[1100]; 时延列表times的长度不超过6000且1 u,v N0w 100; 输入描述: 输入的第一行为两个正整数分别表示网络结点的个数N以及时延列表的长度M用空格分隔; 接下来的M行为两个结点间的时延列表[u v w]; 输入的最后一行为两个正整数分别表示源结点和目的结点。 输出描述: 起点到终点得最小时延不可达则返回-1 示例1: 输入: 3 3 1 2 11 2 3 13 1 3 50 1 3 输出: 24
思路
Dijkstra 算法该算法B站视频讲解得较清楚 同leetcode 743. 网络延迟时间 每次从未标记的节点中选择距离起点最近的节点标记 计算刚加入节点A的邻近节点B的距离不包含标记的节点若节点A的距离节点A到节点B的边长节点B的距离就更新节点B的距离 题解
package hwod;import java.util.Arrays;
import java.util.Scanner;public class TheLeastDelayTime {public static void main(String[] args) {Scanner sc new Scanner(System.in);int n sc.nextInt(), m sc.nextInt();int[][] nums new int[m][3];for (int i 0; i m; i) {for (int j 0; j 3; j) {nums[i][j] sc.nextInt();}}int start sc.nextInt(), end sc.nextInt();System.out.println(theLeastDelayTime(nums, n, start, end));}private static int theLeastDelayTime(int[][] nums, int n, int start, int end) {int[][] g new int[n][n];final int INF Integer.MAX_VALUE / 2;//防止越界//g[i][j]代表节点i到节点j的距离for (int i 0; i n; i) {Arrays.fill(g[i], INF);}for (int[] t : nums) {int x t[0] - 1, y t[1] - 1;g[x][y] t[2];}int[] used new int[n];//判断某个节点是否被标记int[] dist new int[n];//每个节点到起点的距离Arrays.fill(dist, INF);dist[start - 1] 0;for (int i 0; i n; i) {//每次更新一个distint x -1;//找到未标记的距离起点最近的节点xfor (int y 0; y n; y) {if (used[y] 0 (x -1 || dist[y] dist[x])) {x y;}}used[x] 1;//更新标记节点邻近的节点距离for (int y 0; y n; y) {dist[y] Math.min(dist[y], dist[x] g[x][y]);}}return dist[end - 1] INF ? -1 : dist[end - 1];}
}
推荐
如果你对本系列的其他题目感兴趣可以参考华为OD机试真题及题解JAVA查看当前专栏更新的所有题目。
