当前位置: 首页 > 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;…...

ubuntu搭建nfs服务centos挂载访问

在Ubuntu上设置NFS服务器 在Ubuntu上&#xff0c;你可以使用apt包管理器来安装NFS服务器。打开终端并运行&#xff1a; sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享&#xff0c;例如/shared&#xff1a; sudo mkdir /shared sud…...

渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止

<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet&#xff1a; https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...

【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)

可以使用Sqliteviz这个网站免费编写sql语句&#xff0c;它能够让用户直接在浏览器内练习SQL的语法&#xff0c;不需要安装任何软件。 链接如下&#xff1a; sqliteviz 注意&#xff1a; 在转写SQL语法时&#xff0c;关键字之间有一个特定的顺序&#xff0c;这个顺序会影响到…...

今日科技热点速览

&#x1f525; 今日科技热点速览 &#x1f3ae; 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售&#xff0c;主打更强图形性能与沉浸式体验&#xff0c;支持多模态交互&#xff0c;受到全球玩家热捧 。 &#x1f916; 人工智能持续突破 DeepSeek-R1&…...

ios苹果系统,js 滑动屏幕、锚定无效

现象&#xff1a;window.addEventListener监听touch无效&#xff0c;划不动屏幕&#xff0c;但是代码逻辑都有执行到。 scrollIntoView也无效。 原因&#xff1a;这是因为 iOS 的触摸事件处理机制和 touch-action: none 的设置有关。ios有太多得交互动作&#xff0c;从而会影响…...

在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?

uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件&#xff0c;用于在原生应用中加载 HTML 页面&#xff1a; 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...

重启Eureka集群中的节点,对已经注册的服务有什么影响

先看答案&#xff0c;如果正确地操作&#xff0c;重启Eureka集群中的节点&#xff0c;对已经注册的服务影响非常小&#xff0c;甚至可以做到无感知。 但如果操作不当&#xff0c;可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...

人机融合智能 | “人智交互”跨学科新领域

本文系统地提出基于“以人为中心AI(HCAI)”理念的人-人工智能交互(人智交互)这一跨学科新领域及框架,定义人智交互领域的理念、基本理论和关键问题、方法、开发流程和参与团队等,阐述提出人智交互新领域的意义。然后,提出人智交互研究的三种新范式取向以及它们的意义。最后,总结…...

【Linux系统】Linux环境变量:系统配置的隐形指挥官

。# Linux系列 文章目录 前言一、环境变量的概念二、常见的环境变量三、环境变量特点及其相关指令3.1 环境变量的全局性3.2、环境变量的生命周期 四、环境变量的组织方式五、C语言对环境变量的操作5.1 设置环境变量&#xff1a;setenv5.2 删除环境变量:unsetenv5.3 遍历所有环境…...

如何应对敏捷转型中的团队阻力

应对敏捷转型中的团队阻力需要明确沟通敏捷转型目的、提升团队参与感、提供充分的培训与支持、逐步推进敏捷实践、建立清晰的奖励和反馈机制。其中&#xff0c;明确沟通敏捷转型目的尤为关键&#xff0c;团队成员只有清晰理解转型背后的原因和利益&#xff0c;才能降低对变化的…...