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

A - 最短路径

给出一张包含 n 个节点、 m 条边的无向图,请你求出图上两点 s,t 间的最短路径长度。

(请大家自行处理重边和自环)

Input

第一行两个数 n,m ,分别表示节点数和边数,以空格隔开,其中1≤n≤500,1≤m≤50000 ;
之后 m 行,每行 3 个数 u,v,w[i] ,表示点 u 和 v 间有一条权值为 w[i] 的边,
其中1≤u,v≤n ,1≤w[i]≤500000 ;最后一行,两个数 s,t 表示选择的两个点,以空格隔开。

Output

输出一个数,表示 s,t 间最短路径的长度。

Data Description

对于 27% 的数 n≤10 , m≤50 ;
对于 70% 的数据, n≤100 ,m≤5000 ;
对于 100% 的数据,n≤500 ,m≤50000 ,1≤w[i]≤500000 ;

Sample 1

InputcopyOutputcopy
4 3
1 2 6
1 3 4
2 4 2
3 4
12
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 510;
const int INF = 0x3f3f3f3f;
int a[N][N];int n, m;void floyd()
{for (int k = 1; k <= n; k++)for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)a[i][j] = min(a[i][j], a[i][k] + a[k][j]);
}int main()
{memset(a, INF, sizeof a);cin >> n >> m;for (int i = 1; i <= m; i++){int num1, num2, num3;cin >> num1 >> num2 >> num3;a[num1][num2] = a[num2][num1] = min(a[num1][num2],num3);}floyd();for(int i=1;i<=n;i++) a[i][i] = 0;int num3, num4;cin >> num3 >> num4;cout << a[num3][num4] << endl;
}

 

相关文章:

A - 最短路径

给出一张包含 n 个节点、 m 条边的无向图&#xff0c;请你求出图上两点 s,t 间的最短路径长度。 (请大家自行处理重边和自环) Input 第一行两个数 n,m &#xff0c;分别表示节点数和边数&#xff0c;以空格隔开&#xff0c;其中1≤n≤500,1≤m≤50000 &#xff1b; 之后 m 行…...

自然语言处理(三):基于跳元模型的word2vec实现

跳元模型 回顾一下第一节讲过的跳元模型 跳元模型&#xff08;Skip-gram Model&#xff09;是一种用于学习词向量的模型&#xff0c;属于Word2Vec算法中的一种。它的目标是通过给定一个中心词语来预测其周围的上下文词语。 这节我们以跳元模型为例&#xff0c;讲解word2vec的…...

1.1 数据库系统简介

思维导图&#xff1a; 1.1.数据库系统简介 前言&#xff1a; 数据库系统是一个软件系统&#xff0c;用于管理和操作数据库。它提供了一个组织良好、高效并能够方便存取的数据存储机制&#xff0c;并且能够支持各种数据操作、事务管理、并发控制和恢复功能。以下是数据库系统的…...

WebGL 绘制圆点

前言 这篇文章不说WebGL相关概念了&#xff0c;初学者先到网上看看WebGL相关概念。这里着重写一下在vue3前端框架下&#xff0c;如何通过webGL绘制圆点。 着色器代码(画点) 画点相关的着色器代码有顶点着色器和片元着色器&#xff0c;代码如下&#xff1a; 顶点着色器&…...

迅为RK3588开发板Android12 设置系统默认不锁屏

修改 frameworks/base/packages/SettingsProvider/res/values/defaults.xml 文件&#xff0c;修改为如下 所示&#xff1a; - <bool name"def_lockscreen_disabled">false</bool> <bool name"def_lockscreen_disabled">true</bool&…...

香港服务器速度快的原因

1. 传统域名解析过程 了解CDN系统先从域名解析说起。通常&#xff0c;我们在浏览器中输入域名&#xff0c;敲回车后&#xff0c;进入网站进行信息的获取。您分析过输入域名后浏览是如何请求到服务器上的信息&#xff0c;您了解域名解析的过程么&#xff1f; 1.1. 主机解析域…...

过滤器,监听器与拦截器的区别

过滤器&#xff0c;监听器与拦截器的区别 ​ 过滤器和监听器不是Spring MVC中的组件&#xff0c;而是Servlet的组件&#xff0c;由Servlet容器来管理。拦截器是Spring MVC中的组件&#xff0c;由Spring容器来管理 ​ Servlet过滤器与Spring MVC 拦截器在Web应用中所处的层次如…...

clickhouse ssb-dbgen数据构造 及 clickhouse-benchmark简单压测

一、 测试数据构造 1. 数据样例 官方文档有给出一批数据样例。优点是比较真实&#xff0c;缺点是太大了&#xff0c;动辄上百G不适合简单小测试 Anonymized Yandex.Metrica DatasetStar Schema BenchmarkWikiStatTerabyte of Click Logs from CriteoAMPLab Big Data Benchma…...

【数据分析】统计量

1. 均值、众数描述数据的集中趋势度量&#xff0c;四分位差、极差描述数据的离散程度。 2. 标准差、四分位差、异众比率度量离散程度&#xff0c;协方差是度量相关性。 期望值分别为E[X]与E[Y]的两个实随机变量X与Y之间的协方差Cov(X,Y)定义为&#xff1a; 从直观上来看&…...

【通用消息通知服务】0x4 - 目前进展 阶段复盘

【通用消息通知服务】0x4 - 阶段复盘 达成 基本的API已经写完✍️了(消息查看发送, 模板crud,终端crud,发送渠道crud,计划crud,计划执行查看)拆分server, executor, planner三个入口, 方便针对性水平扩展整体架构初步形成&#xff0c;通过队列实现了事件驱动模型和消息订阅发…...

vue若依导出word文件,简单的实现

首先前端导包,注意exportDocx的导包位置要修改成你自己的 import {exportDocx} from /utils/docUtil/docutil.js; import {addDays} from date-fns; import {listGongyi} from "/api/system/detail";然后新建一个测试按钮 <el-col :span"1.5"><…...

【LeetCode75】第四十题 最大层内元素和

目录 题目&#xff1a; 示例&#xff1a; 分析&#xff1a; 代码&#xff1a; 题目&#xff1a; 示例&#xff1a; 分析&#xff1a; 这道题和LeetCode75的上一题大同小异&#xff0c;都是要我们对二叉树进行层序遍历。 那具体如何层序遍历我再上一题也详细介绍过了&#…...

脱离束缚:数字化工厂中ARM控制器的革命性应用!

近年来&#xff0c;中国数字经济体系已进入高速增长阶段。制造业作为中国经济高质量发展的重要支撑力量&#xff0c;在面临生产成本不断上涨、关键装备和核心零部件“受制于人”等挑战时&#xff0c;建设数字化工厂已成必然。 数字化工厂数据采集出现的问题 在数字工厂的建设…...

queue ide is not exists in YARN

报错内容: 2023-08-17 17:30:31.342 [ERROR] [BaseTaskScheduler-Thread-7 ] o.a.l.o.s.a.AsyncExecTaskRunnerImpl (79) [run] - Failed to execute task astJob_1_codeExec_1 org.apache.linkis.orchestrator.ecm.exception.ECMPluginErrorException: errCode:…...

【C++】UDP通信:客户端向服务端发送消息并接收服务端回应的消息

目录 1 UDP简介 2 通信 3 实践 4 运行结果 1 UDP简介 (1)UDP通信是无连接的,因此不需要connect操作。 (2)UDP通信过程需要指定数据接收端的IP和端口。 (3)UDP不对收到的数据进行排序。 (4)UDP对接收到的数据报不回复确认信息。 (5)如果发生了数据丢失,不会丢一…...

RabbitMq深度学习

什么是RabbitMq? RabbitMQ是一个开源的消息队列中间件&#xff0c;它实现了高级消息队列协议&#xff08;AMQP&#xff09;。它被广泛用于分布式系统中的消息传递和异步通信。RabbitMQ提供了一种可靠的、可扩展的机制来传递消息&#xff0c;使不同的应用程序能够相互之间进行…...

EasyExcel自定义字段对象转换器支持转换实体和集合实体

文章目录 1. 实现ObjectConverter2. 使用3. 测试3.1 导出excel3.2 导入excel 1. 实现ObjectConverter package com.tophant.cloud.common.excel.converters;import cn.hutool.json.JSONUtil; import com.alibaba.excel.converters.Converter; import com.alibaba.excel.enums.…...

Linux重置ROOT密码(CentOS)

解释说明 在CentOS中重置root密码通常需要进入单用户模式&#xff0c;这是一个没有密码限制的特殊模式&#xff0c;允许您以root权限登录系统并更改密码。 重启系统 如果您无法登录到系统&#xff0c;可以通过重启系统来开始这个过程。您可以使用虚拟机控制台、物理服务器控制台…...

【Spring】一文带你彻底搞懂IOC、AOP

目录 首先简单了解一下什么是spring框架 什么是IOC&#xff1f; 什么是依赖注入&#xff08;DI&#xff09;&#xff1f; 控制反转和依赖注入又有什么关系&#xff1f; AOP是什么&#xff1f; SpringAOP的实现 说了这么多抽象概念&#xff0c;举个实例方便理解 首先简单…...

国际旅游网络的大数据分析(数学建模练习题)

题目&#xff1a;国际旅游网络的大数据分析 伴随着大数据时代的到来,数据分析已经深入到现代社会生活中的各个方面。 无论是国家政府部门、企事业单位还是个人&#xff0c;数据分析工作都是进行决策之前的 重要环节。 山东省应用统计学会是在省民政厅注册的学术类社会组织&…...

如何在看板中体现优先级变化

在看板中有效体现优先级变化的关键措施包括&#xff1a;采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中&#xff0c;设置任务排序规则尤其重要&#xff0c;因为它让看板视觉上直观地体…...

五年级数学知识边界总结思考-下册

目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解&#xff1a;由来、作用与意义**一、知识点核心内容****二、知识点的由来&#xff1a;从生活实践到数学抽象****三、知识的作用&#xff1a;解决实际问题的工具****四、学习的意义&#xff1a;培养核心素养…...

selenium学习实战【Python爬虫】

selenium学习实战【Python爬虫】 文章目录 selenium学习实战【Python爬虫】一、声明二、学习目标三、安装依赖3.1 安装selenium库3.2 安装浏览器驱动3.2.1 查看Edge版本3.2.2 驱动安装 四、代码讲解4.1 配置浏览器4.2 加载更多4.3 寻找内容4.4 完整代码 五、报告文件爬取5.1 提…...

【无标题】路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论

路径问题的革命性重构&#xff1a;基于二维拓扑收缩色动力学模型的零点隧穿理论 一、传统路径模型的根本缺陷 在经典正方形路径问题中&#xff08;图1&#xff09;&#xff1a; mermaid graph LR A((A)) --- B((B)) B --- C((C)) C --- D((D)) D --- A A -.- C[无直接路径] B -…...

Golang——6、指针和结构体

指针和结构体 1、指针1.1、指针地址和指针类型1.2、指针取值1.3、new和make 2、结构体2.1、type关键字的使用2.2、结构体的定义和初始化2.3、结构体方法和接收者2.4、给任意类型添加方法2.5、结构体的匿名字段2.6、嵌套结构体2.7、嵌套匿名结构体2.8、结构体的继承 3、结构体与…...

深入理解Optional:处理空指针异常

1. 使用Optional处理可能为空的集合 在Java开发中&#xff0c;集合判空是一个常见但容易出错的场景。传统方式虽然可行&#xff0c;但存在一些潜在问题&#xff1a; // 传统判空方式 if (!CollectionUtils.isEmpty(userInfoList)) {for (UserInfo userInfo : userInfoList) {…...

微服务通信安全:深入解析mTLS的原理与实践

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、引言&#xff1a;微服务时代的通信安全挑战 随着云原生和微服务架构的普及&#xff0c;服务间的通信安全成为系统设计的核心议题。传统的单体架构中&…...

【实施指南】Android客户端HTTPS双向认证实施指南

&#x1f510; 一、所需准备材料 证书文件&#xff08;6类核心文件&#xff09; 类型 格式 作用 Android端要求 CA根证书 .crt/.pem 验证服务器/客户端证书合法性 需预置到Android信任库 服务器证书 .crt 服务器身份证明 客户端需持有以验证服务器 客户端证书 .crt 客户端身份…...

【java】【服务器】线程上下文丢失 是指什么

目录 ■前言 ■正文开始 线程上下文的核心组成部分 为什么会出现上下文丢失&#xff1f; 直观示例说明 为什么上下文如此重要&#xff1f; 解决上下文丢失的关键 总结 ■如果我想在servlet中使用线程&#xff0c;代码应该如何实现 推荐方案&#xff1a;使用 ManagedE…...

02-性能方案设计

需求分析与测试设计 根据具体的性能测试需求&#xff0c;确定测试类型&#xff0c;以及压测的模块(web/mysql/redis/系统整体)前期要与相关人员充分沟通&#xff0c;初步确定压测方案及具体的性能指标QA完成性能测试设计后&#xff0c;需产出测试方案文档发送邮件到项目组&…...