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

【华为OD题库-064】最小传输时延I-java

题目

某通信网络中有N个网络结点,用1到N进行标识。网络通过一个有向无环图.表示,其中图的边的值表示结点之间的消息传递时延。
现给定相连节点之间的时延列表times[]={u,v, w),其中u表示源结点,v表示目的结点,w表示u和v之间的消息传递的时延。请计算给定源结点到目的结点的最小传输时延,如果目的结点不可达,返回-1。
注:N的取值范围为[1,100];
时延列表times的长度不超过6000,且1<= u,v<= N,0<=w <= 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),查看当前专栏更新的所有题目。

相关文章:

【华为OD题库-064】最小传输时延I-java

题目 某通信网络中有N个网络结点&#xff0c;用1到N进行标识。网络通过一个有向无环图.表示,其中图的边的值表示结点之间的消息传递时延。 现给定相连节点之间的时延列表times[]{u&#xff0c;v&#xff0c; w)&#xff0c;其中u表示源结点&#xff0c;v表示目的结点&#xff0…...

全文检索[ES系列] - 第495篇

历史文章&#xff08;文章累计490&#xff09; 《国内最全的Spring Boot系列之一》 《国内最全的Spring Boot系列之二》 《国内最全的Spring Boot系列之三》 《国内最全的Spring Boot系列之四》 《国内最全的Spring Boot系列之五》 《国内最全的Spring Boot系列之六》 M…...

【预计IEEE出版|EI征稿通知】第六届下一代数据驱动网络国际学术会议 (NGDN 2024)

第六届下一代数据驱动网络国际学术会议 (NGDN 2024) The Sixth International Conference on Next Generation Data-driven Networks 2024年4月26-28日 | 中国沈阳 基于前几届在英国埃克塞特 (ISPA 2020) 、中国沈阳 (TrustCom 2021) 和中国武汉 (IEEETrustCom-2022) 成功举…...

C++软件在Win平台运行总结

Windows平台&#xff1a; 1.需要安装运行库&#xff1a;无论是exe还是动态库用的哪种平台工具集(visual2010-visual2019)进行编译&#xff0c;需要安装对应的运行时库vc_redist.x64.exe/vc_redist.x86.exe。比如Exe用的是VisualStdio2010工具集编译&#xff0c;其中链接的一个…...

【数电笔记】16-卡诺图绘制(逻辑函数的卡诺图化简)

目录 说明&#xff1a; 最小项卡诺图的组成 1. 相邻最小项 2. 卡诺图的组成 2.1 二变量卡诺图 2.2 三表变量卡诺图 2.3 四变量卡诺图 3. 卡诺图中的相邻项&#xff08;几何相邻&#xff09; 说明&#xff1a; 笔记配套视频来源&#xff1a;B站&#xff1b;本系列笔记并…...

前端面试灵魂提问(1)

1.自我介绍 2.在实习中&#xff0c;你负责那一模块 3.any与unknow的异同 相同点&#xff1a;any和unkonwn 可以接受任何值 不同点&#xff1a;any会丢掉类型限制&#xff0c;可以用any 类型的变量随意做任何事情。unknown 变量会强制执行类型检查&#xff0c;所以在使用一个…...

Linux中项目部署步骤

安装jdk&#xff0c;tomcat 安装步骤 1&#xff0c;将压缩包&#xff0c;拷贝到虚拟机中。 通过工具&#xff0c;将文件直接拖到虚拟机的/home下 2&#xff0c;回到虚拟机中&#xff0c;查看/home下&#xff0c;有两个压缩文件 3&#xff0c;给压缩文件做解压缩操作 tar -z…...

cmd下查看python命令的用法

在cmd下&#xff0c;可以运行python --help或者py --help来查看python命令的用法。例如&#xff1a;...

大型语言模型在实体关系提取中的应用探索(二)

上一篇文章我们探讨了如何使用大语言模型进行实体关系的抽取。本篇文章我们将进一步探索这个话题。比较一下国内外几款知名大模型在相同的实体关系提取任务下的表现。由于精力有限&#xff0c;我们无法全面测试各模型的实体关系抽取能力&#xff0c;因此&#xff0c;看到的效果…...

Easy Excel设置表格样式

1. 设置通用样式 import com.alibaba.excel.annotation.ExcelProperty; import com.alibaba.excel.annotation.write.style.*; import com.fasterxml.jackson.annotation.JsonFormat; import com.xxx.npi.config.easypoi.EasyExcelDateConverter; import lombok.Data; import …...

HarmonyOS/OpenHarmony应用开发

OpenHarmony是由开放原子开源基金会(OpenAtom Foundation)孵化及运营的开源项目, 目标是面向全场景、全连接、全智能时代, 搭建一个智能终端设备操作系统的框架和平台, 促进万物互联产业的繁荣发展。 了解OpenHarmony HarmonyOS是华为通过OpenHarmony项目&#xff0c;结合商业…...

孩子都能学会的FPGA:第二十一课——用线性反馈移位寄存器实现伪随机序列

&#xff08;原创声明&#xff1a;该文是作者的原创&#xff0c;面向对象是FPGA入门者&#xff0c;后续会有进阶的高级教程。宗旨是让每个想做FPGA的人轻松入门&#xff0c;作者不光让大家知其然&#xff0c;还要让大家知其所以然&#xff01;每个工程作者都搭建了全自动化的仿…...

国内 AI 成图第一案!你来你会怎么判?

我国目前并未出台专门针对网络爬虫技术的法律规范&#xff0c;但在司法实践中&#xff0c;相关判决已屡见不鲜&#xff0c;K 哥特设了“K哥爬虫普法”专栏&#xff0c;本栏目通过对真实案例的分析&#xff0c;旨在提高广大爬虫工程师的法律意识&#xff0c;知晓如何合法合规利用…...

快速登录界面关于如何登录以及多账号列表解析以及config配置文件是如何读取(1)

快速登录界面关于如何登录以及多账号列表解析以及config配置文件是如何读取 1、快速登录界面关于如何登录以及快速登录界面账号如何显示 如图所示:根据按下按钮一键登录中途会发生什么。 关于一键登录按钮皮肤skin的设置: <Button name"QuickLoginOkBtn" text&q…...

finebi 新手入门案例

finebi 新手入门案例 连锁超市销售数据分析 步骤&#xff1a; 准备公共数据新建分析主题处理数据在数据中分析在图形中分析数据大屏 准备公共数据 点击公共数据 点击新建文件夹 修改文件夹名称 上传数据 鼠标悬停在文件夹上&#xff0c;右侧出现 鼠标悬停在文件夹上&#x…...

1. 小游戏(贪心)

题干&#xff1a; 谷同学很喜欢玩计算机游戏&#xff0c;特别是战略游戏&#xff0c;但是有时他不能尽快找到解所以常常感到很沮丧。现在面临如下问题&#xff1a;他必须在一个中世纪的城堡里设防&#xff0c;城堡里的道路形成一棵无向树。要在结点上安排最少的士兵使得他们可以…...

记录 | c++打印变量类型

c打印变量类型: 使用 typeid(变量名).name() int main(){std::cout << "type of ss : " << typeid(ss).name() << std::endl; }...

nodejs_vue+vscode美容理发店会员管理系统un1dm

按照设计开发一个系统的常用流程来描述系统&#xff0c;可以把系统分成分析阶段&#xff0c;设计阶段&#xff0c;实现阶段&#xff0c;测试阶段。所以在编写系统的说明文档时&#xff0c;根据系统所处的阶段来描述系统的内容。 绪论&#xff1a;这是对选题的背景&#xff0c;意…...

C语言 操作符详解

C语言学习 目录 文章目录 前言 一、算术操作符 二、移位操作符 2.1 左移操作符 2.2 右移操作符 三、位操作符 3.1 按位与操作符 & 3.2 按位或操作符 | 3.3 按位异或操作符 ^ 四、赋值操作符 五、单目操作符 5.1 逻辑反操作符&#xff01; 5.2 正值、负值-操作符 5.3 取地址…...

成为AI产品经理——回归模型评估(MSE、RMSE、MAE、R方)

分类问题的评估是看实际类别和预测类别是否一致&#xff0c;它的评估指标主要有混淆矩阵、AUC、KS。回归问题的评估是看实际值和预测值是否一致&#xff0c;它的评估指标包括MAE、MSE、RMSE、R方。 如果我们预测第二天某支股票的价格&#xff0c;给一个模型 y1.5x&#xff0c;…...

7.4.分块查找

一.分块查找的算法思想&#xff1a; 1.实例&#xff1a; 以上述图片的顺序表为例&#xff0c; 该顺序表的数据元素从整体来看是乱序的&#xff0c;但如果把这些数据元素分成一块一块的小区间&#xff0c; 第一个区间[0,1]索引上的数据元素都是小于等于10的&#xff0c; 第二…...

synchronized 学习

学习源&#xff1a; https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖&#xff0c;也要考虑性能问题&#xff08;场景&#xff09; 2.常见面试问题&#xff1a; sync出…...

3.3.1_1 检错编码(奇偶校验码)

从这节课开始&#xff0c;我们会探讨数据链路层的差错控制功能&#xff0c;差错控制功能的主要目标是要发现并且解决一个帧内部的位错误&#xff0c;我们需要使用特殊的编码技术去发现帧内部的位错误&#xff0c;当我们发现位错误之后&#xff0c;通常来说有两种解决方案。第一…...

多场景 OkHttpClient 管理器 - Android 网络通信解决方案

下面是一个完整的 Android 实现&#xff0c;展示如何创建和管理多个 OkHttpClient 实例&#xff0c;分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...

学校招生小程序源码介绍

基于ThinkPHPFastAdminUniApp开发的学校招生小程序源码&#xff0c;专为学校招生场景量身打造&#xff0c;功能实用且操作便捷。 从技术架构来看&#xff0c;ThinkPHP提供稳定可靠的后台服务&#xff0c;FastAdmin加速开发流程&#xff0c;UniApp则保障小程序在多端有良好的兼…...

ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放

简介 前面两期文章我们介绍了I2S的读取和写入&#xff0c;一个是通过INMP441麦克风模块采集音频&#xff0c;一个是通过PCM5102A模块播放音频&#xff0c;那如果我们将两者结合起来&#xff0c;将麦克风采集到的音频通过PCM5102A播放&#xff0c;是不是就可以做一个扩音器了呢…...

微服务商城-商品微服务

数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...

从零实现STL哈希容器:unordered_map/unordered_set封装详解

本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说&#xff0c;直接开始吧&#xff01; 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...

【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具

第2章 虚拟机性能监控&#xff0c;故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令&#xff1a;jps [options] [hostid] 功能&#xff1a;本地虚拟机进程显示进程ID&#xff08;与ps相同&#xff09;&#xff0c;可同时显示主类&#x…...

python执行测试用例,allure报乱码且未成功生成报告

allure执行测试用例时显示乱码&#xff1a;‘allure’ &#xfffd;&#xfffd;&#xfffd;&#xfffd;&#xfffd;ڲ&#xfffd;&#xfffd;&#xfffd;&#xfffd;ⲿ&#xfffd;&#xfffd;&#xfffd;Ҳ&#xfffd;&#xfffd;&#xfffd;ǿ&#xfffd;&am…...