【Day50 LeetCode】图论问题 Ⅷ
一、图论问题 Ⅷ
1、dijkstra算法 堆优化
采用堆来优化,适合节点多的稀疏图。代码如下:
# include<iostream>
# include<vector>
# include<list>
# include<queue>
# include<climits>using namespace std;class mycomparison {
public:bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {return lhs.second > rhs.second;}
};int main(){int n, m;cin >> n >> m;int s, e, v;vector<list<pair<int, int>>> grid(n+1);for(int i=0; i<m; ++i){cin >> s >> e >> v;grid[s].push_back(pair<int, int>(e, v));}vector<int> minDist(n+1, INT_MAX);vector<bool> visited(n+1, false);int start = 1, end = n;minDist[start] = 0;priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pq;pq.push(pair<int, int>(start, 0));while(!pq.empty()){// 1、选取源点到未被访问过且距离最近的节点; auto cur = pq.top(); pq.pop();if(visited[cur.first])continue;// 2、将最近节点标记为访问过 visited[cur.first] = true;// 3、更新非访问节点到源点的距离for(auto edge : grid[cur.first]){if(!visited[edge.first] && minDist[edge.first] > minDist[cur.first] + edge.second )minDist[edge.first] = minDist[cur.first] + edge.second;pq.push(pair<int, int>(edge.first, minDist[edge.first]));}}if(minDist[end] < INT_MAX)cout << minDist[end] << endl;elsecout << -1 << endl;return 0;
}
2、Bellman_ford 算法
权值有负值的图无法采用dijdijkstra算法,这时需要使用Bellman_ford 算法来解决最短路问题。
#include <iostream>
#include <vector>
#include <list>
#include <climits>using namespace std;int main() {int n, m, p1, p2, val;cin >> n >> m;vector<vector<int>> grid;for(int i = 0; i < m; i++){cin >> p1 >> p2 >> val;grid.push_back({p1, p2, val});}int start = 1, end = n; vector<int> minDist(n + 1 , INT_MAX);minDist[start] = 0;for (int i = 1; i < n; i++) { // 对所有边 松弛 n-1 次for (vector<int> &side : grid) { // 每一次松弛,都是对所有边进行松弛int from = side[0]; // 边的出发点int to = side[1]; // 边的到达点int price = side[2]; // 边的权值// 松弛操作 // minDist[from] != INT_MAX 防止从未计算过的节点出发if (minDist[from] != INT_MAX && minDist[to] > minDist[from] + price) { minDist[to] = minDist[from] + price; }}}if (minDist[end] == INT_MAX)cout << "unconnected" << endl; // 不能到达终点elsecout << minDist[end] << endl; // 到达终点最短路径return 0;
}
参考资料
代码随想录
相关文章:
【Day50 LeetCode】图论问题 Ⅷ
一、图论问题 Ⅷ 1、dijkstra算法 堆优化 采用堆来优化,适合节点多的稀疏图。代码如下: # include<iostream> # include<vector> # include<list> # include<queue> # include<climits>using namespace std;class myco…...
结构体介绍及内存大小分配问题
结构体 一.结构体的介绍1.1结构体的声明1.2匿名结构体1.3结构的自引用1.4使用 typedef 简化结构体类型名 二.结构体内存对齐2.1内存对齐规则2.2结构体内存对齐原因2.3修改默认对齐数 在 C 语言中,结构体(struct)是一种用户自定义的数据类型&a…...
halcon 条形码、二维码识别、opencv识别
一、条形码 函数介绍 create_bar_code_model * 1.创建条码读取器的模板 * 参数一:通用参数的名称,针对条形码模型进行调整。默认值为空 * 参数二:针对条形码模型进行调整 * 参数三:条形码模型的句柄。 create_bar_code_model (…...
Vue框架的使用 搭建打包 Vue的安全问题(Xss,源码泄露)
前言 什么是Vue? Vue是轻量级的js框架 可以帮助我们一键构造网站,打包app程序等 Vue的基本使用 1、构造框架并启用 新建一个 目录 使用终端切换到当前的目录 创建vue项目 第一个弹出使用语法我们选择是 剩下的全选择否 发现创建好了 接着进行…...
Java+SpringBoot+Vue+数据可视化的音乐推荐与可视化平台(程序+论文+讲解+安装+调试+售后)
感兴趣的可以先收藏起来,还有大家在毕设选题,项目以及论文编写等相关问题都可以给我留言咨询,我会一一回复,希望帮助更多的人。 系统介绍 在互联网技术以日新月异之势迅猛发展的浪潮下,5G 通信技术的普及、云计算能力…...
day2 - SpringBoot框架开发技术
主要内容 1. SpringBoot简介 2. 构建springboot工程 3. springboot接口返回json 4. springboot热部署 5. springboot资源属性配置 6. springboot整合模板引擎 7. springboot异常处理 8. springboot整合MyBatis 9. springboot整合redis 10. springboot整合定时任务 11. springbo…...
Flash-03
1-问题:Flash软件画两个图形,若有部分重合则变为一个整体 解决方法1:两个图形分属于不同的图层 解决方法2:将每个图形都转化为【元件】 问题2:元件是什么? 在 Adobe Flash(现在称为 Adobe Anim…...
新建菜单项的创建之CmpGetValueListFromCache函数分析
第一部分: PCELL_DATA CmpGetValueListFromCache( IN PHHIVE Hive, IN PCACHED_CHILD_LIST ChildList, OUT BOOLEAN *IndexCached, OUT PHCELL_INDEX ValueListToRelease ) 0: kd> dv KeyControlBlock 0xe1…...
【Word2Vec】Skip-gram 的直观理解(深入浅出)
01 什么是skip-gram 一句话来说就是,给定中心词,然后预测其周围的词: 02 模型结构 对于skip-gram来说,输入是一个[1 x V]维的ont-hot向量,其中V为词表大小,值为1的那一项就表示我们的中心词。经过一个[V x…...
在MacOS上打造本地部署的大模型知识库(一)
一、在MacOS上安装Ollama docker run -d -p 3000:8080 --add-hosthost.docker.internal:host-gateway -v open-webui:/app/backend/data --name open-webui --restart always ghcr.io/open-webui/open-webui:main 最后停掉Docker的ollama,就能在webui中加载llama模…...
(21)从strerror到strtok:解码C语言字符函数的“生存指南2”
❤个人主页:折枝寄北的博客 ❤专栏位置:简单入手C语言专栏 目录 前言1. 错误信息报告1.1 strerror 2. 字符操作2.1 字符分类函数2.2 字符转换函数 3. 内存操作函数3.1 memcpy3.2 memmove3.2memset3.3 memcmp 感谢您的阅读 前言 当你写下strcpy(dest, s…...
DeepSeek推出DeepEP:首个开源EP通信库,让MoE模型训练与推理起飞!
今天,DeepSeek 在继 FlashMLA 之后,推出了第二个 OpenSourceWeek 开源项目——DeepEP。 作为首个专为MoE(Mixture-of-Experts)训练与推理设计的开源 EP 通信库,DeepEP 在EP(Expert Parallelism)…...
1.2 Kaggle大白话:Eedi竞赛Transformer框架解决方案02-GPT_4o生成训练集缺失数据
目录 0. 本栏目竞赛汇总表1. 本文主旨2. AI工程架构3. 数据预处理模块3.1 配置数据路径和处理参数3.2 配置API参数3.3 配置输出路径 4. AI并行处理模块4.1 定义LLM客户端类4.2 定义数据处理函数4.3 定义JSON保存函数4.4 定义数据分片函数4.5 定义分片处理函数4.5 定义文件名排序…...
数据结构-顺序表专题
大家好!这里是摆子,今天给大家带来的是C语言数据结构开端-顺序表专题,主要介绍了数据结构和动态顺序表的实现,快来看看吧!记得一键三连哦! 1.数据结构的概念 1.1什么是数据结构? 数据结构是计…...
docker和containerd从TLS harbor拉取镜像
私有镜像仓库配置了自签名证书,https访问,好处是不需要处理免费证书和付费证书带来的证书文件变更,证书文件变更后需要重启服务,自签名证书需要将一套客户端证书存放在/etc/docker/cert.d目录下,或者/etc/containerd/c…...
kafka-关于ISR-概述
一. 什么是ISR ? Kafka 中通常每个分区都有多个副本,其中一个副本被选举为 Leader,其他副本为 Follower。ISR 是指与 Leader 副本保持同步的 Follower 副本集合。ISR 机制的核心是确保数据在多个副本之间的一致性和可靠性,同时在 …...
el-input实现金额输入
需求:想要实现一个输入金额的el-input,限制只能输入数字和一个小数点。失焦数字转千分位,聚焦转为数字,超过最大值,红字提示 效果图 失焦 聚焦 报错效果 // 组件limitDialog <template><el-dialog:visible.s…...
C++11智能指针
一、指针管理的困境 资源释放了,但指针没有置空(野指针、指针悬挂、踩内存) 没有释放资源,产生内存泄漏问题;重复释放资源,引发coredump 二、智能指针...
安装Git(小白也会装)
一、官网下载:Git 1.依次点击(红框) 不要安装在C盘了,要炸了!!! 后面都 使用默认就好了,不用改,直接Next! 直到这里,选第一个 这两种选项的区别如…...
驭势科技9周年:怀揣理想,踏浪前行
2025年的2月,驭势科技迎来9岁生日。位于国内外不同工作地的Uiseeker齐聚线上线下,共同庆祝驭势走过的璀璨九年。 驭势科技联合创始人、董事长兼CEO吴甘沙现场分享了驭势9年的奔赴之路,每一段故事都包含着坚持与拼搏。 左右滑动查看更多 Part.…...
生成 Git SSH 证书
🔑 1. 生成 SSH 密钥对 在终端(Windows 使用 Git Bash,Mac/Linux 使用 Terminal)执行命令: ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" 参数说明: -t rsa&#x…...
2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面
代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口(适配服务端返回 Token) export const login async (code, avatar) > {const res await http…...
【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)
🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...
C# SqlSugar:依赖注入与仓储模式实践
C# SqlSugar:依赖注入与仓储模式实践 在 C# 的应用开发中,数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护,许多开发者会选择成熟的 ORM(对象关系映射)框架,SqlSugar 就是其中备受…...
C++使用 new 来创建动态数组
问题: 不能使用变量定义数组大小 原因: 这是因为数组在内存中是连续存储的,编译器需要在编译阶段就确定数组的大小,以便正确地分配内存空间。如果允许使用变量来定义数组的大小,那么编译器就无法在编译时确定数组的大…...
零知开源——STM32F103RBT6驱动 ICM20948 九轴传感器及 vofa + 上位机可视化教程
STM32F1 本教程使用零知标准板(STM32F103RBT6)通过I2C驱动ICM20948九轴传感器,实现姿态解算,并通过串口将数据实时发送至VOFA上位机进行3D可视化。代码基于开源库修改优化,适合嵌入式及物联网开发者。在基础驱动上新增…...
Linux部署私有文件管理系统MinIO
最近需要用到一个文件管理服务,但是又不想花钱,所以就想着自己搭建一个,刚好我们用的一个开源框架已经集成了MinIO,所以就选了这个 我这边对文件服务性能要求不是太高,单机版就可以 安装非常简单,几个命令就…...
【HarmonyOS 5】鸿蒙中Stage模型与FA模型详解
一、前言 在HarmonyOS 5的应用开发模型中,featureAbility是旧版FA模型(Feature Ability)的用法,Stage模型已采用全新的应用架构,推荐使用组件化的上下文获取方式,而非依赖featureAbility。 FA大概是API7之…...
WEB3全栈开发——面试专业技能点P4数据库
一、mysql2 原生驱动及其连接机制 概念介绍 mysql2 是 Node.js 环境中广泛使用的 MySQL 客户端库,基于 mysql 库改进而来,具有更好的性能、Promise 支持、流式查询、二进制数据处理能力等。 主要特点: 支持 Promise / async-await…...
【版本控制】GitHub Desktop 入门教程与开源协作全流程解析
目录 0 引言1 GitHub Desktop 入门教程1.1 安装与基础配置1.2 核心功能使用指南仓库管理日常开发流程分支管理 2 GitHub 开源协作流程详解2.1 Fork & Pull Request 模型2.2 完整协作流程步骤步骤 1: Fork(创建个人副本)步骤 2: Clone(克隆…...
