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

浏览器访问 AWS ECS 上部署的 Docker 容器(监听 80 端口)

✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义&#xff08;Task Definition&…...

vscode里如何用git

打开vs终端执行如下&#xff1a; 1 初始化 Git 仓库&#xff08;如果尚未初始化&#xff09; git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...

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

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

在Ubuntu中设置开机自动运行(sudo)指令的指南

在Ubuntu系统中&#xff0c;有时需要在系统启动时自动执行某些命令&#xff0c;特别是需要 sudo权限的指令。为了实现这一功能&#xff0c;可以使用多种方法&#xff0c;包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法&#xff0c;并提供…...

UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)

UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中&#xff0c;UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化&#xf…...

#Uniapp篇:chrome调试unapp适配

chrome调试设备----使用Android模拟机开发调试移动端页面 Chrome://inspect/#devices MuMu模拟器Edge浏览器&#xff1a;Android原生APP嵌入的H5页面元素定位 chrome://inspect/#devices uniapp单位适配 根路径下 postcss.config.js 需要装这些插件 “postcss”: “^8.5.…...

基于 TAPD 进行项目管理

起因 自己写了个小工具&#xff0c;仓库用的Github。之前在用markdown进行需求管理&#xff0c;现在随着功能的增加&#xff0c;感觉有点难以管理了&#xff0c;所以用TAPD这个工具进行需求、Bug管理。 操作流程 注册 TAPD&#xff0c;需要提供一个企业名新建一个项目&#…...

Python+ZeroMQ实战:智能车辆状态监控与模拟模式自动切换

目录 关键点 技术实现1 技术实现2 摘要&#xff1a; 本文将介绍如何利用Python和ZeroMQ消息队列构建一个智能车辆状态监控系统。系统能够根据时间策略自动切换驾驶模式&#xff08;自动驾驶、人工驾驶、远程驾驶、主动安全&#xff09;&#xff0c;并通过实时消息推送更新车…...

从“安全密码”到测试体系:Gitee Test 赋能关键领域软件质量保障

关键领域软件测试的"安全密码"&#xff1a;Gitee Test如何破解行业痛点 在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的"神经中枢"。从国防军工到能源电力&#xff0c;从金融交易到交通管控&#xff0c;这些关乎国计民生的关键领域…...

人工智能 - 在Dify、Coze、n8n、FastGPT和RAGFlow之间做出技术选型

在Dify、Coze、n8n、FastGPT和RAGFlow之间做出技术选型。这些平台各有侧重&#xff0c;适用场景差异显著。下面我将从核心功能定位、典型应用场景、真实体验痛点、选型决策关键点进行拆解&#xff0c;并提供具体场景下的推荐方案。 一、核心功能定位速览 平台核心定位技术栈亮…...