当前位置: 首页 > 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;数据分析工作都是进行决策之前的 重要环节。 山东省应用统计学会是在省民政厅注册的学术类社会组织&…...

Go 语言接口详解

Go 语言接口详解 核心概念 接口定义 在 Go 语言中&#xff0c;接口是一种抽象类型&#xff0c;它定义了一组方法的集合&#xff1a; // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的&#xff1a; // 矩形结构体…...

【磁盘】每天掌握一个Linux命令 - iostat

目录 【磁盘】每天掌握一个Linux命令 - iostat工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景 注意事项 【磁盘】每天掌握一个Linux命令 - iostat 工具概述 iostat&#xff08;I/O Statistics&#xff09;是Linux系统下用于监视系统输入输出设备和CPU使…...

跨链模式:多链互操作架构与性能扩展方案

跨链模式&#xff1a;多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈&#xff1a;模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展&#xff08;H2Cross架构&#xff09;&#xff1a; 适配层&#xf…...

leetcodeSQL解题:3564. 季节性销售分析

leetcodeSQL解题&#xff1a;3564. 季节性销售分析 题目&#xff1a; 表&#xff1a;sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...

pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)

目录 一、SQL注入 二、insert注入 三、报错型注入 四、updatexml函数 五、源码审计 六、insert渗透实战 1、渗透准备 2、获取数据库名database 3、获取表名table 4、获取列名column 5、获取字段 本系列为通过《pikachu靶场通关笔记》的SQL注入关卡(共10关&#xff0…...

ABAP设计模式之---“简单设计原则(Simple Design)”

“Simple Design”&#xff08;简单设计&#xff09;是软件开发中的一个重要理念&#xff0c;倡导以最简单的方式实现软件功能&#xff0c;以确保代码清晰易懂、易维护&#xff0c;并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计&#xff0c;遵循“让事情保…...

算法岗面试经验分享-大模型篇

文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer &#xff08;1&#xff09;资源 论文&a…...

Yolov8 目标检测蒸馏学习记录

yolov8系列模型蒸馏基本流程&#xff0c;代码下载&#xff1a;这里本人提交了一个demo:djdll/Yolov8_Distillation: Yolov8轻量化_蒸馏代码实现 在轻量化模型设计中&#xff0c;**知识蒸馏&#xff08;Knowledge Distillation&#xff09;**被广泛应用&#xff0c;作为提升模型…...

MySQL 知识小结(一)

一、my.cnf配置详解 我们知道安装MySQL有两种方式来安装咱们的MySQL数据库&#xff0c;分别是二进制安装编译数据库或者使用三方yum来进行安装,第三方yum的安装相对于二进制压缩包的安装更快捷&#xff0c;但是文件存放起来数据比较冗余&#xff0c;用二进制能够更好管理咱们M…...

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的“no matching...“系列算法协商失败问题

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的"no matching..."系列算法协商失败问题 摘要&#xff1a; 近期&#xff0c;在使用较新版本的OpenSSH客户端连接老旧SSH服务器时&#xff0c;会遇到 "no matching key exchange method found"​, "n…...