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

01BFS最短距离的原理和C++实现

时间复杂度

O(n),n是边数。

使用前提

边的权只有两种:0,1。

典型场景

n个端点的无向图,编号范围[0,n)。Edges0表示{{n1,n2},...{n3,n4}}表示n1和n2,n3和n4之间有路联接。Edges1表示{{n1,n2},...{n3,n4}}表示n1和n2,n3和n4之间有损坏的路连接。要想让s和d之间至少有一条通道,最小需要维修多少条路。如果无法到达,请返回-1。可能有环,但无自环,重边,可能不联通。

解题思路

可以用类似上章的思路,没损害的路加到pre中,损坏的路加到que中。距离相等的点,谁先谁后无所谓。需要维修的路入队的时候不能计算最短距离,因为不一定是最短边。改在入队计算最短距离,第一层循环记录最短距离。

核心代码

class CBFS1
{
public:CBFS1(vector<vector<int>>& vNeiB0, vector<vector<int>>& vNeiB1, int s){m_vDis.assign(vNeiB0.size(), -1);//m_vDis[s] = 0;queue<int> pre;pre.emplace(s);for (int i = 0; pre.size(); i++){queue<int> dp;while (pre.size()){const int cur = pre.front();pre.pop();if (-1 != m_vDis[cur]){continue;}m_vDis[cur] = i;for (const auto next : vNeiB0[cur]){pre.emplace(next);}for (const auto next : vNeiB1[cur]){dp.emplace(next);}}dp.swap(pre);}}
public:vector<int> m_vDis;
};

测试样例

#define CBFS CBFS1 
class CDebugBFS : public CBFS
{
public:
    using CBFS::CBFS;
    void Assert(const vector<int>& vDis)
    {
        for (int i = 0; i < vDis.size(); i++)
        {
            assert(vDis[i] == m_vDis[i]);
        }
    }
};

struct CDebugParam
{
    int n;
    vector<vector<int>> edges0;
    vector<vector<int>> edges1;
    int s;
    vector<int> dis;//答案
};

int main()
{
    vector<CDebugParam> params = { {1,{},{},0,{0}},{2,{},{},0,{0,-1}},{2,{{0,1}},{},0,{0,0}},{2,{},{{0,1}},0,{0,1}},
    {6,{}, { {0,1},{1,2},{1,3},{2,4},{4,5},{3,5}},0,{0,1,2,2,3,3} },
    {6,{{3,5}}, { {0,1},{1,2},{1,3},{2,4},{4,5}},0,{0,1,2,2,3,2} }
    };
    for (const auto& par : params)
    {
        auto vNeiB0 = EdgeToNeiBo(par.n, par.edges0);
        auto vNeiB1 = EdgeToNeiBo(par.n, par.edges1);
        CDebugBFS bfs(vNeiB0, vNeiB1,par.s);
        bfs.Assert(par.dis);
    }
}


类似场景

魔塔经典问题,砸墙需要一个锄头,没墙的地方可以随便移动,如果用尽可能少的锄头到达目的地。许多游戏经过箭塔附件时,会遭到箭塔攻击。如何已最小的损坏通过箭塔。


用双向队列优化

当前状态

操作

新状态

处理结束

首尾入队

一种最短距离

一种最短距离

出队

状态不变或变为空

队首入队

一种最短距离或两种最短距离

队尾入队

一种最短距离或两种最短距离

二种最短距离

出队

状态不变或变为一种最短距离

队首入队

两种最短距

队尾入队

两种最短距

class C01BFSDis
{
public:C01BFSDis(vector<vector<int>>& vNeiB0, vector<vector<int>>& vNeiB1, int s){m_vDis.assign(vNeiB0.size(), -1);std::deque<std::pair<int,int>> que;que.emplace_back(s,0);while (que.size()){auto it = que.front();const int cur = it.first;const int dis = it.second;que.pop_front();if (-1 != m_vDis[cur]){continue;}m_vDis[cur] = it.second;for (const auto next : vNeiB0[cur]){if (-1 != m_vDis[next]){continue;} que.emplace_front(next,dis);}for (const auto next : vNeiB1[cur]){if (-1 != m_vDis[next]){continue;}que.emplace_back(next, dis+1);}}}
public:vector<int> m_vDis;
};

测试环境

Win10 VS2022 C++17

下载

doc文档下载(排版好):
https://download.csdn.net/download/he_zhidan/88348653
源码下载:
https://download.csdn.net/download/he_zhidan/88383828

相关文章:

01BFS最短距离的原理和C++实现

时间复杂度 O(n)&#xff0c;n是边数。 使用前提 边的权只有两种:0,1。 典型场景 n个端点的无向图&#xff0c;编号范围[0,n)。Edges0表示{{n1,n2},...{n3,n4}}表示n1和n2&#xff0c;n3和n4之间有路联接。Edges1表示{{n1,n2},...{n3,n4}}表示n1和n2&#xff0c;n3和n4之间…...

【洛谷 P5266】【深基17.例6】学籍管理 题解(映射+分支)

【深基17.例6】学籍管理 题目描述 您要设计一个学籍管理系统&#xff0c;最开始学籍数据是空的&#xff0c;然后该系统能够支持下面的操作&#xff08;不超过 1 0 5 10^5 105 条&#xff09;&#xff1a; 插入与修改&#xff0c;格式1 NAME SCORE&#xff1a;在系统中插入姓…...

10.03

代码 #include <iostream>using namespace std; class cz { private:int num1; //实部int num2; //虚部 public:cz(){}cz(int a,int b):num1(a),num2(b){}cz(const cz &other):num1(other.num1),num2(other.num2){}~cz(){}const cz operator(const cz &othe…...

链表单向链表跳跃链表

单向链表 link list t数组的局限&#xff1a;编译期就需要知道大小&#xff1b; 内存连续&#xff0c;插入困难 // 链表节点类 包含一个信息 和指向下一个 节点的指针clas IntLLNode{public:IntLLNode(){// 默认构造函数 没有info信息nextPtr_ 0;// 空指针}IntLLNode(int …...

博客无限滚动加载(html、css、js)实现

介绍 这是一个简单实现了类似博客瀑布流加载功能的页面&#xff0c;使用html、css、js实现。简单易懂&#xff0c;值得学习借鉴。&#x1f44d; 演示地址&#xff1a;https://i_dog.gitee.io/easy-web-projects/infinite_scroll_blog/index.html 代码 index.html <!DOCT…...

腾讯云南京服务器性能如何?南京服务器测速IP地址

腾讯云服务器南京地域怎么样&#xff1f;南京地域很不错&#xff0c;正好处于中间的位置&#xff0c;南方北方用户均可以选择&#xff0c;网络延迟更低速度更快&#xff0c;并且目前南京地域有活动&#xff0c;南京地域可用区可选南京一区、南京二区和南京三区&#xff0c;腾讯…...

MySQL和Oracle中,语法的不同点以及如何在xml中书写日期比较大小

众所周知mysql和oracle的语法有点相识&#xff0c;又有点不同。 在MySQL和Oracle中&#xff0c;语法的不同点有以下几个方面&#xff1a; 数据类型&#xff1a;MySQL和Oracle支持的数据类型有所不同&#xff0c;比如MySQL支持的数据类型包括&#xff1a;整型、浮点型、字符型、…...

谈谈Redis分布式锁

目录 一、回顾分布式锁 &#xff08;一&#xff09;理解分布式锁的定义 &#xff08;二&#xff09;分布式锁的约束条件 &#xff08;三&#xff09;分布式锁常见实现方式 基于数据库的分布式锁 基于缓存的分布式锁 基于分布式一致性算法的分布式锁 基于文件系统的分布…...

Redis的java客户端-RedisTemplate光速入门

一.创建springboot项目 二.引入2个依赖 <!-- redis依赖-->这个已经引入了&#xff0c;因为创建的时候勾选了<dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-data-redis</artifactId><…...

格点数据可视化(美国站点的日降雨数据)

获取美国站点的日降雨量的格点数据&#xff0c;并且可视化 导入模块 from datetime import datetime, timedelta from urllib.request import urlopenimport cartopy.crs as ccrs import cartopy.feature as cfeature import matplotlib.colors as mcolors import matplotli…...

YoloV8改进策略:LSKNet加入到YoloV8中,打造更适合小目标的YoloV8

文章目录 摘要论文:LSKNet:大选择核网络在遥感目标检测中的应用1、简介2、相关工作2.1、遥感目标检测框架2.2、大核网络2.3、注意力/选择机制3、方法3.1、LSKNet架构3.2、大核卷积3.3、空间核选择4、实验4.1、数据集4.2、实现细节4.3、消融实验4.4、主要结果4.5、分析5、结论…...

力扣-303.区域和检索-数组不可变

Idea 需计算数组nums在下标right 和 left-1 的前缀和&#xff0c;然后计算两个前缀和的差即可。 需要注意的是&#xff0c;当left为0的时候&#xff0c;如果还是left-1则会发生数组访问越界错误。 AC Code class NumArray { public:vector<int> sum;NumArray(vector<…...

web:[极客大挑战 2019]LoveSQL

题目 打开页面显示如下 查看源代码&#xff0c;查到一个check.php&#xff0c;还是get传参 尝试账号密码输入 题目名为sql&#xff0c;用万能密码 1or 11# 或 admin or 11 给了一段乱码&#xff0c;也不是flag 查看字段数 /check.php?usernameadmin order by 3%23&pass…...

数据结构—快速排序(续)

引言&#xff1a;在上一篇中我们详细介绍了快速排序和改进&#xff0c;并给出了其中的一种实现方式-挖坑法 但其实快速排序有多种实现方式&#xff0c;这篇文章再来介绍其中的另外两种-左右指针法和前后指针法。有了上一篇挖坑法的启示&#xff0c;下面的两种实现会容易许多。 …...

Snapdragon Profiler分析Android GPU

Snapdragon Profiler&#xff08;骁龙分析器&#xff09;是一款性能分析软件&#xff0c;在Windows、 Mac、和 Linux平台上都可以运行&#xff0c;主要是用来分析使用了高通骁龙处理器的Android设备。 Snapdragon Profiler通过USB连接这些Android设备&#xff0c;开发者可以用…...

Cannot download sources:IDEA源码无法下载

问题 Swagger的相关包&#xff0c;无法看到注释&#xff1b; 在class文件的页面&#xff0c;点击下载源码&#xff0c;源码下载不了&#xff0c;IDEA报下面的错误。 报错 Cannot download sources Sources not found for: io.swagger.core.v3:swagger-annotations:2.2.9 解决…...

从零开始学习 Java:简单易懂的入门指南之IO字符流(三十一)

IO流之字符流 1. 字符流1.1 字符输入流【Reader】1.2 FileReader类构造方法读取字符数据 1.3 字符输出流【Writer】1.4 FileWriter类构造方法基本写出数据关闭和刷新写出其他数据 2. IO异常的处理JDK7前处理JDK7的处理JDK9的改进 3. 综合练习练习1&#xff1a;拷贝文件夹练习2&…...

监狱工具管理系统-监狱劳动工具管理系统

监狱劳动工具管理系统(智工具DW-S308)是依托互3D技术、云计算、大数据、RFID技术、数据库技术、AI、视频分析技术对工具进行统一管理、分析的信息化、智能化、规范化的系统。 当前各级监狱工器具管理更多的是借助于传统的人工管理方法和手段&#xff0c;数据的采集和录入一直以…...

蓄水池算法

题目&#xff1a; 假设有一组数据流元素有 N 个&#xff08;事先不知道 N 具体值&#xff09;&#xff0c;我们希望选择 n 个样本&#xff08;N > n&#xff09;&#xff0c;使用怎样的策略进行抽样可以使得数据流中每个元素被选择的概率恰为 n / N 结论&#xff1a; 创建大…...

作业 day4

完成父子进程通信...

Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)

目录 1.TCP的连接管理机制&#xff08;1&#xff09;三次握手①握手过程②对握手过程的理解 &#xff08;2&#xff09;四次挥手&#xff08;3&#xff09;握手和挥手的触发&#xff08;4&#xff09;状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...

【机器视觉】单目测距——运动结构恢复

ps&#xff1a;图是随便找的&#xff0c;为了凑个封面 前言 在前面对光流法进行进一步改进&#xff0c;希望将2D光流推广至3D场景流时&#xff0c;发现2D转3D过程中存在尺度歧义问题&#xff0c;需要补全摄像头拍摄图像中缺失的深度信息&#xff0c;否则解空间不收敛&#xf…...

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

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

什么是Ansible Jinja2

理解 Ansible Jinja2 模板 Ansible 是一款功能强大的开源自动化工具&#xff0c;可让您无缝地管理和配置系统。Ansible 的一大亮点是它使用 Jinja2 模板&#xff0c;允许您根据变量数据动态生成文件、配置设置和脚本。本文将向您介绍 Ansible 中的 Jinja2 模板&#xff0c;并通…...

Web 架构之 CDN 加速原理与落地实践

文章目录 一、思维导图二、正文内容&#xff08;一&#xff09;CDN 基础概念1. 定义2. 组成部分 &#xff08;二&#xff09;CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 &#xff08;三&#xff09;CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 &#xf…...

【Java学习笔记】BigInteger 和 BigDecimal 类

BigInteger 和 BigDecimal 类 二者共有的常见方法 方法功能add加subtract减multiply乘divide除 注意点&#xff1a;传参类型必须是类对象 一、BigInteger 1. 作用&#xff1a;适合保存比较大的整型数 2. 使用说明 创建BigInteger对象 传入字符串 3. 代码示例 import j…...

基于 TAPD 进行项目管理

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

NPOI操作EXCEL文件 ——CAD C# 二次开发

缺点:dll.版本容易加载错误。CAD加载插件时&#xff0c;没有加载所有类库。插件运行过程中用到某个类库&#xff0c;会从CAD的安装目录找&#xff0c;找不到就报错了。 【方案2】让CAD在加载过程中把类库加载到内存 【方案3】是发现缺少了哪个库&#xff0c;就用插件程序加载进…...

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

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

MyBatis中关于缓存的理解

MyBatis缓存 MyBatis系统当中默认定义两级缓存&#xff1a;一级缓存、二级缓存 默认情况下&#xff0c;只有一级缓存开启&#xff08;sqlSession级别的缓存&#xff09;二级缓存需要手动开启配置&#xff0c;需要局域namespace级别的缓存 一级缓存&#xff08;本地缓存&#…...