Prim算法:经过图中所有节点的最短路径
题目链接:53. 寻宝(第七期模拟笔试)
#include<bits/stdc++.h>
using namespace std;// v为节点数量,e为边数量
int v, e;// 最小生成树
void prim(vector<vector<int>>& adj) {vector<int> dist(v+1, INT_MAX); // 节点到生成树的距离,初始化为最大距离vector<int> used(v+1, 0); // 是否已经加入到生成树中,0表示没加入,1表示加入vector<int> pre_node(v+1, 0); // 生成树中节点i的前驱节点,0表示没有前驱// 把序号为1的节点加入生成树,在生成树中的节点到生成树的距离为0dist[1] = 0; for (int i = 1; i <= v; ++i) {// 找到生成树距离最小的节点加入生成树int closest_node_idx = -1;for (int j = 1; j <= v; ++j) {if (!used[j] && (closest_node_idx == -1 || dist[j] < dist[closest_node_idx]) ) {closest_node_idx = j;}}used[closest_node_idx] = 1;// 更新节点到生成树的距离并保存其前驱节点,方便最后计算最短路径for (int k = 1; k <= v; ++k) {if (!used[k] && dist[k] > adj[closest_node_idx][k] ) {dist[k] = adj[closest_node_idx][k];pre_node[k] = closest_node_idx;}}}int res = 0;// 从编号为2的节点开始算最短路径,因为第1个节点没有前驱节点(没有向前的边)for (int i = 2; i <= v; ++i) {res += adj[i][pre_node[i]];}printf("%d\n", res);}int main() {while (cin>>v>>e) {int v1, v2, val;std::vector<vector<int>> adj(v+1, vector<int>(v+1, INT_MAX));for (int i = 0; i < e; i++) {scanf("%d%d%d", &v1, &v2, &val);adj[v1][v2] = val;adj[v2][v1] = val;}prim(adj);}return 0;
}相关文章:
Prim算法:经过图中所有节点的最短路径
题目链接:53. 寻宝(第七期模拟笔试) #include<bits/stdc.h> using namespace std;// v为节点数量,e为边数量 int v, e;// 最小生成树 void prim(vector<vector<int>>& adj) {vector<int> dist(v1, I…...
Linux 信号捕捉函数 signal sigaction
signal函数 #include <signal.h> typedef void (*sighandler_t)(int); sighandler_t signal(int signum, sighandler_t handler); 功能:设置某个信号的捕捉行为 参数: -signum:要捕捉的信号 handler:对捕捉到的信号怎么处理…...
StarRocks操作笔记
最近在使用starRocks,记录一些临时的操作技巧,防止遗忘。 1. 创建表 CREATE TABLE IF NOT EXISTS ODS.T_TEST( pk_day date, pool_address string, code string comment 唯一主键, test1 string, test2 string, test3 string, pk_year varchar(4), pk_m…...
Linux的ls -ld命令产生的信息怎么看
2023年9月24日,周日上午 目录 ls -ld列出的目录或文件的信息含义文件硬链接什么是文件硬链接为什么新建目录的文件硬链接为2举例说明例一例二例三 ls -ld列出的目录或文件的信息含义 第一个字符表示文件类型: d: 目录 -: 普通文件 l: 软链接 b: 块设备文件 c:…...
Linux- 内存映射文件(Memory-Mapped File)
内存映射文件(Memory-Mapped File)是⼀种将文件内容映射到内存中的机制,允许程序直接访问文件数据,就好像这些数据已经被加载到了内存⼀样。这个机制允许文件的内容被映射到⼀个进程的地址空间,从而允许程序以⼀种更高…...
李航老师《统计学习方法》第五章阅读笔记
决策树(decision tree)是一种基本的分类与回归方法。本章主要讨论用于分类的决策树。决策树模型呈树形结构,在分类问题中,表示基于特征对实例进行分类的过程。 以下是关于分类决策树的一些基本概念和特点: 树形结构&am…...
iOS16新特性:实时活动-在锁屏界面实时更新APP消息 | 京东云技术团队
简介 之前在 《iOS16新特性:灵动岛适配开发与到家业务场景结合的探索实践》 里介绍了iOS16新的特性:实时更新(Live Activity)中灵动岛的适配流程,但其实除了灵动岛的展示样式,Live Activity还有一种非常实用的应用场景…...
使用 Elasticsearch、OpenAI 和 LangChain 进行语义搜索
在本教程中,我将引导您使用 Elasticsearch、OpenAI、LangChain 和 FastAPI 构建语义搜索服务。 LangChain 是这个领域的新酷孩子。 它是一个旨在帮助你与大型语言模型 (LLM) 交互的库。 LangChain 简化了与 LLMs 相关的许多日常任务,例如从文档中提取文本…...
NIFI集群_队列Queue中数据无法清空_清除队列数据报错_无法删除queue_解决_集群中机器交替重启删除---大数据之Nifi工作笔记0061
今天发现,有两个处理器,启动以后,数据流不过去,后来,锁定问题在,queue队列上面,因为别的队列都可以通过,右键,empty queue清空,就是 这个队列不行,这个队列无法被删除,至于为什么导致这样的, 猜测是因为之前,流程设计好以后,队列没有设置背压,也没有设置队列中的内容大小和fl…...
leetcode20. 有效的括号 [简单题]
题目 给定一个只包括 (,),{,},[,] 的字符串 s ,判断字符串是否有效。 有效字符串需满足: 左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型…...
ubuntu20.04下源码编译colmap
由于稠密重建需要CUDA,因此先安装CUDA,我使用的是3050GPU,nvidia-smi显示最高支持CUDA11.4。 不要用sudo apt安装,版本较低,30系显卡建议安装CUDA11.0以上,这里安装了11.1版本。 下载: cuda_1…...
Jumpserver堡垒机
一、堡垒机概述 1、堡垒机的基本概念 堡垒机也是一台服务器,在一个特定的网络环境下,为了保障网络和数据不受来自外部和内部用户的入侵和破坏,而运用各种技术手段实时收集、监控网络环境中每一个组成部分(服务器)的系…...
第一百五十三回 如何实现滑动窗口
文章目录 概念介绍实现方法示例代码 我们在上一章回中介绍了自定义组件实现游戏摇杆相关的内容,本章回中将介绍 如何实现滑动窗口.闲话休提,让我们一起Talk Flutter吧。 概念介绍 我们在本章回中介绍的滑动窗口表示在屏幕底部向上滑动时弹出一个窗口&a…...
Oracle 12c自动化管理特性的新进展:自动备份、自动恢复和自动维护功能的优势|oracle 12c相对oralce 11g的新特性(3)
一、前言: 前面几期讲解了oracle 12c多租户的使用、In-Memory列存储来提高查询性能以及数据库的克隆、全局数据字典和共享数据库资源的使用 今天我们讲讲oracle 12c的另外的一个自动化管理功能新特性:自动备份、自动恢复、自动维护的功能 二、自动备份、自动恢复、自动维护…...
Redis——Jedis中hash类型使用
hset 和 hget hset可以逐一添加key和value,也可以通过map类型来直接添加多组fields 而hget则返回string类型,如果元素不存在则返回null private static void hsetAndHget(Jedis jedis) {jedis.flushAll();jedis.hset("key", "f1"…...
肖sir__项目实战讲解__004
项目实战讲解 一、项目的类型 金融类: 保险(健康险理财险)、证券、基金(股票型基金、混合型基金、指数型基金、债券型基金、 天天基金网(ETF基金、货币型基金、量化基金)、银行、贷款、信用卡、外汇、二元期权、期货原油、blockchain、 数字货币、黄金白…...
数据库数据恢复-ORACLE常见故障有哪些?恢复数据的可能性高吗?
ORACLE数据库常见故障: 1、ORACLE数据库无法启动或无法正常工作。 2、ORACLE数据库ASM存储破坏。 3、ORACLE数据库数据文件丢失。 4、ORACLE数据库数据文件部分损坏。 5、ORACLE数据库DUMP文件损坏。 ORACLE数据库数据恢复可能性分析: 1、ORACLE数据库无…...
合规性管理如何帮助产品团队按时交付?
成功的产品和产品发布背后通常需要经过一个涉及多个监督机构、多功能团队和利益相关者的复杂流程。在组织的治理、风险管理和合规性(GRC)框架下,产品团队不仅需要追求市场创新,还需要确保符合所有适用的法规、标准和合同要求。由于…...
从平均数到排名算法
平均数用更少的数字,概括一组数字。属于概述统计量、集中趋势测度、位置测度。中位数是第二常见的概述统计量。许多情况下比均值更合适。算术平均数是3中毕达哥拉斯平均数之一,另外两种毕达哥拉斯平均数是几何平均数和调和平均数。 算术平均 A M 1 n ∑…...
如何使用ESP8266微控制器和Nextion显示器为Home Assistant展示温度传感器和互联网天气预报
第一部分:引言与项目概述 在智能家居领域,实时监控和显示环境数据已经成为了一个热门的话题。无论是室内温度、室外温度,还是游泳池的温度,都可以通过各种传感器轻松获取。但如何将这些数据以直观、美观的方式展现出来呢…...
SciencePlots——绘制论文中的图片
文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了:一行…...
mongodb源码分析session执行handleRequest命令find过程
mongo/transport/service_state_machine.cpp已经分析startSession创建ASIOSession过程,并且验证connection是否超过限制ASIOSession和connection是循环接受客户端命令,把数据流转换成Message,状态转变流程是:State::Created 》 St…...
Java - Mysql数据类型对应
Mysql数据类型java数据类型备注整型INT/INTEGERint / java.lang.Integer–BIGINTlong/java.lang.Long–––浮点型FLOATfloat/java.lang.FloatDOUBLEdouble/java.lang.Double–DECIMAL/NUMERICjava.math.BigDecimal字符串型CHARjava.lang.String固定长度字符串VARCHARjava.lang…...
Python实现prophet 理论及参数优化
文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候,写过一篇简单实现,后期随着对该模型的深入研究,本次记录涉及到prophet 的公式以及参数调优,从公式可以更直观…...
Spring Boot面试题精选汇总
🤟致敬读者 🟩感谢阅读🟦笑口常开🟪生日快乐⬛早点睡觉 📘博主相关 🟧博主信息🟨博客首页🟫专栏推荐🟥活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...
大模型多显卡多服务器并行计算方法与实践指南
一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...
css3笔记 (1) 自用
outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size:0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格ÿ…...
CSS设置元素的宽度根据其内容自动调整
width: fit-content 是 CSS 中的一个属性值,用于设置元素的宽度根据其内容自动调整,确保宽度刚好容纳内容而不会超出。 效果对比 默认情况(width: auto): 块级元素(如 <div>)会占满父容器…...
《C++ 模板》
目录 函数模板 类模板 非类型模板参数 模板特化 函数模板特化 类模板的特化 模板,就像一个模具,里面可以将不同类型的材料做成一个形状,其分为函数模板和类模板。 函数模板 函数模板可以简化函数重载的代码。格式:templa…...
Vue ③-生命周期 || 脚手架
生命周期 思考:什么时候可以发送初始化渲染请求?(越早越好) 什么时候可以开始操作dom?(至少dom得渲染出来) Vue生命周期: 一个Vue实例从 创建 到 销毁 的整个过程。 生命周期四个…...
