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

超短脉冲激光自聚焦效应

前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应&#xff0c;这是一种非线性光学现象&#xff0c;主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场&#xff0c;对材料产生非线性响应&#xff0c;可能…...

基于FPGA的PID算法学习———实现PID比例控制算法

基于FPGA的PID算法学习 前言一、PID算法分析二、PID仿真分析1. PID代码2.PI代码3.P代码4.顶层5.测试文件6.仿真波形 总结 前言 学习内容&#xff1a;参考网站&#xff1a; PID算法控制 PID即&#xff1a;Proportional&#xff08;比例&#xff09;、Integral&#xff08;积分&…...

DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径

目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...

Java 8 Stream API 入门到实践详解

一、告别 for 循环&#xff01; 传统痛点&#xff1a; Java 8 之前&#xff0c;集合操作离不开冗长的 for 循环和匿名类。例如&#xff0c;过滤列表中的偶数&#xff1a; List<Integer> list Arrays.asList(1, 2, 3, 4, 5); List<Integer> evens new ArrayList…...

前端倒计时误差!

提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...

java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别

UnsatisfiedLinkError 在对接硬件设备中&#xff0c;我们会遇到使用 java 调用 dll文件 的情况&#xff0c;此时大概率出现UnsatisfiedLinkError链接错误&#xff0c;原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用&#xff0c;结果 dll 未实现 JNI 协…...

linux 下常用变更-8

1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行&#xff0c;YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID&#xff1a; YW3…...

【配置 YOLOX 用于按目录分类的图片数据集】

现在的图标点选越来越多&#xff0c;如何一步解决&#xff0c;采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集&#xff08;每个目录代表一个类别&#xff0c;目录下是该类别的所有图片&#xff09;&#xff0c;你需要进行以下配置步骤&#x…...

【决胜公务员考试】求职OMG——见面课测验1

2025最新版&#xff01;&#xff01;&#xff01;6.8截至答题&#xff0c;大家注意呀&#xff01; 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:&#xff08; B &#xff09; A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...

【python异步多线程】异步多线程爬虫代码示例

claude生成的python多线程、异步代码示例&#xff0c;模拟20个网页的爬取&#xff0c;每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程&#xff1a;允许程序同时执行多个任务&#xff0c;提高IO密集型任务&#xff08;如网络请求&#xff09;的效率…...