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

领略算法真谛: 多源bfs

news 来源：原创 2025/8/25 0:07:12

嘿，各位技术潮人！好久不见甚是想念。生活就像一场奇妙冒险，而编程就是那把超酷的万能钥匙。此刻，阳光洒在键盘上，灵感在指尖跳跃，让我们抛开一切束缚，给平淡日子加点料，注入满满的passion。准备好和我一起冲进代码的奇幻宇宙了吗？Let's go！

我的博客：yuanManGan

我的专栏：C++入门小馆 C言雅韵集数据结构漫游记闲言碎语小记坊题山采玉领略算法真谛

多源最短路问题思路：

我们来对比一下单源最短路问题和多源最短路问题，之前我们解决的单源最短路问题是只有一个起点那如果我们不只有一个起点呢？这时就是多源最短路问题了。

当我们多源最短路的边权都是1的时候，我们就可以使用多源bfs来解决。

我们可以将所有的起点看成一个“超级源点”。然后我们从这个源点开始当成单源最短路问题来处理问题了。比如下面的例子：

比如我们红色的节点是起点，我们要求到所有其他节点的最短路。

这时我们要将所有的红色的节点当成一个超级源点，可以将所有的起点放入一个队列，然后正常进行bfs操作即可。

多说无益我们来试试一道题目：

矩阵距离

题⽬来源：⽜客⽹

题⽬链接：矩阵距离

难度系数： ★★

这里补充一个知识，曼哈顿距离：

A和B的曼哈顿距离等于两点的横纵坐标相减再相加，其实就是两点只能走上下左右的最短距离。

题目有个小坑，输入矩阵时数字间没有空格，我们只能用字符数组来存储数据。题目的意思就是求数值不是1的点到数值是1的点的距离，我们将数值为1的点当作超级源点就解决掉了。

代码展示：

#include <iostream>
#include <queue>
#include <cstring>using namespace std;
const int N = 1010;
typedef pair<int, int> PII;
int n, m;
int dist[N][N];
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
char a[N][N];void bfs()
{memset(dist, -1, sizeof dist);queue<PII> q;for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){if(a[i][j] == '1') {dist[i][j] = 0;q.push({i, j});}}}while(q.size()){auto t = q.front(); q.pop();int i = t.first, j = t.second;for(int k = 0; k < 4; k++){int x = i + dx[k], y = j + dy[k];if(x >= 1 && x <= n && y >= 1 && y <= m && dist[x][y] == -1){dist[x][y] = dist[i][j] + 1;q.push({x,y});}}}}int main()
{cin >> n >> m;for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){cin >> a[i][j];}}bfs();for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){cout << dist[i][j] << " ";}cout << endl;}return 0;
}

领略算法真谛: 多源bfs

嘿，各位技术潮人！好久不见甚是想念。生活就像一场奇妙冒险，而编程就是那把超酷的万能钥匙。此刻，阳光洒在键盘上，灵感在指尖跳跃，让我们抛开一切束缚，给平淡日子加点料，注入满满的pa…...

编程日记 2025/8/25 0:07:12

Linux的web服务器的部署及优化

实验环境的配置我们依然是要配置本地软件仓库，之前已有详细介绍，然后再次基础上还有如下操作，首先是进入到以下文件进行编辑编辑内容为下，并且注意自身的网关有没有写错然后给予权限再进行下列操作后，就配置完成了…...

编程日记 2025/8/24 6:06:58

ASP.NET Core 请求限速的ActionFilter

文章目录前言一、实现步骤1）创建自定义Action Filter示例1：示例2： 2）注册服务3）使用二、实现说明总结前言以下是一个基于内存缓存实现的自定义限流Action Filter。一、实现步骤 1）创建自定义Action…...

编程日记 2025/8/25 0:00:21

本地化语音转换工具推荐与使用

软件介绍 Buzz是一款基于OpenAI Whisper技术开发的开源语音转文字工具，支持离线运行和实时语音转换，能够高效完成会议记录、音频转文字等任务。安装注意事项在使用Buzz之前需要注意软件的安装设置，由于程序自带较大的模型文件&…...

编程日记 2025/8/24 0:26:16

【心海资源】telegram换U地址完整源码

【心海资源】telegram换U地址完整源码未测,需要的下载完整的下载地址：下载地址.txt - 蓝奏云...

编程日记 2025/8/25 0:01:33

神经网络开发实战：从零基础到企业级应用（含CNN、RNN、BP网络代码详解）

简介神经网络作为深度学习的核心，正在成为现代AI应用的基石。从基础的感知机到复杂的Transformer架构，从图像识别到自然语言处理，神经网络技术的演进推动了人工智能的快速发展。本文将系统介绍神经网络的核心概念、主流模型及其实现原理，并通过三个企业级实战案例（医学图…...

编程日记 2025/8/24 19:50:11

C# 0、WPF 布局 1、ON/OFF按钮 2、textBox 3、ComboBox 4、TabControl 5、Button <Window x:Class"WpfApp5.MainWindow"xmlns"http://schemas.microsoft.com/winfx/2006/xaml/presentation"xmlns:x"http://schemas.microsoft.com/winfx/20…...

编程日记 2025/8/25 0:03:15

【PaaS与AI融合】MLOps平台的架构设计

PaaS与AI融合：MLOps平台的架构设计一、技术背景与发展趋势二、技术架构核心特征1. 全生命周期管理闭环2. 混合编排引擎3. 智能资源调度三、关键技术实现细节1. 持续集成流水线2. 异构资源管理3. 安全治理体系四、行业实践与未来演进典型案例分析发展趋势展望五、架构设计建议…...

编程日记 2025/8/25 0:00:56

硬件工程师面试常见问题（15）

第七十一问：运放增益带宽积解读（有待改进） 增益带宽积顾名思义：增益（就是开环增益）与带宽的乘积； 第七十二问：运放输出摆幅定义：输出摆幅是指输出信号在最大值和最小值…...

编程日记 2025/8/24 1:57:03

SpringMVC——第6章：RESTFul编程风格

一、RESTFul编程风格 1.RESTFul是什么 RESTFul是WEB服务接口的一种设计风格。 RESTFul定义了一组约束条件和规范，可以让WEB服务接口更加简洁、易于理解、易于扩展、安全可靠。 RESTFul对一个WEB服务接口都规定了哪些东西？ 对请求的URL格式有约束和规范…...

编程日记 2025/8/24 23:59:06

深度解析：从 GPT-4o“谄媚”到 Deepseek“物理腔”，透视大模型行为模式的底层逻辑与挑战

深度解析：从 GPT-4o“谄媚”到 AI“物理腔”，透视大模型行为模式的底层逻辑与挑战标签：人工智能, GPT-4o, 大语言模型, AI伦理, 人机交互, 技术思考大家好！最近AI圈最火的“瓜”之一，莫过于OpenAI的GPT-4o模型在一…...

编程日记 2025/8/25 0:01:33

2025 年最新树莓派 Pico 连接 OLED 显示字模汉字详细教程

OLED 概述 OLED（Organic Light-Emitting Diode，有机发光二极管）是一种基于有机材料的发光技术，通过电流驱动有机薄膜发光，具有自发光、高对比度、柔性可弯曲等特点。 4 针脚 OLED 硬件电路如图所示，GND 接…...

编程日记 2025/8/24 23:58:26

【Ubuntu 安装Docker CE-Jenkins】

安装Docker CE(Ubuntu) Install | Docker Docs官网使用apt仓库安装 DNS配置(可选) #手动替换 sudo vim /etc/systemd/resolved.conf #典型配置如下 [Resolve] DNS8.8.8.8 DNS114.114.114.114 FallbackDNS1.1.1.1 # 备用 DNS#sed替换 sudo sed -i /^#DNS/ {s/#DNS/DNS8.8.8…...

编程日记 2025/8/25 0:05:29

知识图谱 + 大语言模型：打造更聪明、更可靠的AI大脑 —— 探索 GraphRAG 中文优化与可视化实践

大语言模型（LLMs）无疑是近年来人工智能领域最耀眼的明星。它们强大的自然语言理解和生成能力，在文本创作、代码生成、对话交互等众多领域展现了惊人的潜力。然而，当前的 LLMs 并非完美无缺，它们常常面临着“幻觉”&…...

编程日记 2025/8/25 0:00:21

三、【LLaMA-Factory实战】模型微调进阶：从LoRA到MoE的技术突破与工程实践

一、引言在大模型微调领域，选择合适的训练策略直接决定了效率与效果的平衡。LLaMA-Factory深度整合了参数高效微调（PEFT）、全量微调、混合专家模型（MoE）等12种训练策略，支持从消费级GPU到多卡集群的全场景…...

编程日记 2025/8/24 23:58:24

Photo-SLAM论文理解、环境搭建、代码理解与实测效果

前言：第一个解耦式Photo-SLAM，亮点和效果。参考：https://zhuanlan.zhihu.com/p/715311759 全网最细PhotoSLAM的conda环境配置教程，拒绝环境污染！！-CSDN博客 1. 环境搭建硬件：RTX 4090D wi…...

编程日记 2025/8/24 23:58:26

解决pycharm检测不到已经装好的conda的pytorch环境

问题 1.找装anaconda的位置（我装到了py-anacon下） 2.找到下图中的conda.bat 3.pycharm社区版右下角，添加新解释器 4.选conda环境，选择2.中conda.bat的位置，加载环境，使用现有环境，可以看到有选…...

编程日记 2025/8/25 0:03:14

【计算机视觉】3d人脸重建：3DDFA_V2：实时高精度3D人脸重建与密集对齐技术指南

3d人脸重建：3DDFA_V2：实时高精度3D人脸重建与密集对齐技术指南一、项目概述与技术背景1.1 3DDFA_V2核心价值1.2 技术演进路线1.3 核心技术指标二、环境配置与模型部署2.1 硬件要求2.2 软件安装基础环境搭建关键组件安装 2.3 模型下载三、核心算法原理…...

编程日记 2025/8/24 23:59:06

谈判模拟器 - Gemini 2.5 商业优化版

核心目标： 基于深厚的理论知识、丰富的实战经验和前沿的技术洞察，结合麦肯锡领先的谈判策略框架，为用户提供全面、深入、可操作的商业谈判策略指导和建议，助力其在复杂商业环境中达成最优谈判结果，并实现商业价值最大化…...

编程日记 2025/8/24 23:58:26

深度学习系统学习系列【4】之反向传播（BP)四个基本公式推导

文章目录补充知识：∇ 和 ⊙ 运算符详解∇ (nabla) 运算符⊙ (圆圈点) 运算符反向传播基本公式计算图和基本定义BP1：输出层误差推导BP1公式的重要性实际例子BP2第 l l l层误差推导BP3 ：损失函数关于偏置(b)偏导的推导BP4： 损失函…...

编程日记 2025/8/25 0:00:20

算法每日一题 | 入门-顺序结构-上学迟到

上学迟到题目描述学校和 yyy 的家之间的距离为 s 米，而 yyy 以 v 米每分钟的速度匀速走向学校。在上学的路上，yyy 还要额外花费 10 分钟的时间进行垃圾分类。学校要求必须在上午 8:00 到达，请计算在不迟到的前提下，yyy 最…...

编程日记 2025/8/25 0:00:57

开源库测试

yolov10 https://github.com/THU-MIG/yolov10 conda create -n yolov10 python3.9 conda activate yolov10 pip install -r requirements.txt pip install -e .报错找不到对应版本 Could not find a version that satisfies the requirement gradio4.31.5 (from versions:…...

编程日记 2025/8/23 18:20:02

因为gromacs必须安装cuda（系统自带的NVIDIA驱动不行），这里介绍下如何安装cuda

1. 安装步骤查看是否安装了cuda # 法1 cat /usr/local/cuda/version.txt # 法2 nvcc --version 若没有安装，则查看是否有N卡驱动，若无N卡驱动，则到软件与更新 -> 附加驱动中安装驱动查看N卡驱动支持的cuda版本 nvidia-smi 如下…...

编程日记 2025/8/24 5:28:11

ABC 404

1.C 题： 1.思路： NM&每个点读数为2，但图中有可能出现多环，需要判断所有点是否都在同一连通块上，有俩种解法：搜索，循环 2.代码（循环做法） #include<bits/stdc.h&g…...

编程日记 2025/8/23 3:20:05

机器学习朴素贝叶斯算法

1.朴素贝叶斯算法 1.1基本概念其分类原理是利用贝叶斯公式根据某特征的先验概率计算出其后验概率，然后选择具有最大后验概率作为该特征所属的类。之所以称之为“朴素”，是因为贝叶斯分类只做最原始、最简单的假设：所有的特征之间是相对独立…...

编程日记 2025/8/23 8:40:03

Linux：深入理解数据链路层

实际上一台主机中，报文并没有通过网络层直接发送出去，而是交给了自己的下一层协议——数据链路层！！ 一、理解数据链路层网络层交付给链路层之前，会先做决策再行动（会先查一下路由表，看看目标网…...

编程日记 2025/8/23 2:20:02

健康养生：从生活点滴启航

养生并非遥不可及的高深学问，只需把握生活中的细微之处，就能为健康保驾护航。清晨睁眼，先在床上做简单的搓脸动作，从下巴到额头轻柔按摩，促进面部血液循环，唤醒肌肤活力。随后空腹喝一杯温水，可…...

编程日记 2025/8/23 5:40:02

【向量数据库】用披萨点餐解释向量数据库：一个美味的技术类比

文章目录前言场景设定：披萨特征向量化顾客到来：生成查询向量相似度计算实战1. 欧氏距离计算（值越小越相似）2. 余弦相似度计算（值越大越相似） 关键发现：度量选择影响结果现实启示结语前言想象…...

编程日记 2025/8/23 1:40:03

CloudCompare 中 ccDrawableObject

CloudCompare 中 ccDrawableObject 类的主要内容与使用 1. ccDrawableObject 概述在 CloudCompare 中，ccDrawableObject 是一个基类，主要用于管理 3D 可绘制对象的显示属性，如颜色、可见性、LOD（层次细节）、光照等…...

编程日记 2025/8/23 18:40:15

【Linux】进程控制

🌟🌟作者主页：ephemerals__ 🌟🌟所属专栏：Linux 目录前言一、什么是进程控制二、进程创建三、进程终止（进程退出） 退出码 main函数返回 _exit() exit() 测试四、进…...

编程日记 2025/8/23 11:40:02

设计模式-基础概念学习总结（继承、多态、虚方法、方法重写）

概念使用例子的方式介绍（继承，多态，虚方法，方法重写），实现代码python 1. 继承（Inheritance） 概念：子类继承父类的属性和方法，可以直接复用父类的代码&#…...

编程日记 2025/8/23 11:20:03

分析rand()和srand()函数的功能

rand()和srand()函数原型： int rand(void) 返回一个范围在 0 到 RAND_MAX 之间的伪随机数。 void srand(unsigned int seed)用来给rand() 设置随机数发生器，随机数发生器输出不同的数值，rand() 就会生成不同的随机数 1)、在“D:\Keil_v5\AR…...

编程日记 2025/8/23 2:40:15

架构师如何构建个人IP：职业规划与业务战略的双重提升

在数字化时代，软件架构师的角色已从单纯的技术专家转变为兼具技术领导力和业务影响力的复合型人才。如何构建个人IP，提升行业影响力，成为架构师职业发展的关键课题。本文从个人认知、业务战略、架构决策、产品思维四个维度，探讨架…...

编程日记 2025/8/23 8:28:15

CSS知识总结

一、CSS核心概念解析 1.1 选择器体系（重点） 基础选择器： /* ID选择器 */ #header { background: #333; }/* 类选择器 */ .btn-primary { color: white; }/* 属性选择器 */ input[type"text"] { border: 1px solid #ccc; } 组合…...

编程日记 2025/8/23 16:00:48

CRS 16 slot 设备硬件架构

目录 1. 核心组件 1.1 线路卡与物理接口模块 1.2 交换结构与容量 1.3 控制与管理 1.4 风扇与散热 1.5 电源与告警 2. 插槽编号与机箱布局 2.1 前侧（PLIM 面） 2.2 后侧（MSC 面） 2.3 插槽配对 1. 核心组件 1.1 线路卡与物…...

编程日记 2025/8/23 21:40:01

人工智能浪潮中Python的核心作用与重要地位

在人工智能（Artificial Intelligence，AI）蓬勃发展的时代，Python已然成为推动这一技术进步的关键编程语言。从复杂的机器学习算法实现，到前沿的深度学习模型构建，再到智能系统的部署，Python无处不…...

编程日记 2025/8/23 21:20:14

【了解】数字孪生网络（Digital Twin Network，DTN）

目录一、为什么？二、是什么？三、什么架构？四、如何应用？参考一、为什么？ 一方面，网络负载不断增加,，网络规模持续扩大带来的网络复杂性，使得网络的运行和维护变得越来越复杂。另一…...

编程日记 2025/8/23 9:40:01

[C语言]第一章-初识

目录一.引言二.MinGW 下载与安装 1.什么是 MinGW 2.下载 MinGW 3.安装 MinGW 4.配置 MinGW 环境变量三.VS Code 下载与安装 1.什么是 VS Code 2.下载 VS Code 3.安装 VS Code 4.汉化 5.安装扩展插件 C/C 截图四.编写并运行 Hello World 程序代码解释运行…...

编程日记 2025/8/24 22:30:10

如何用git将项目上传到github

步骤 1.创建仓库 2.记下仓库的url 3.在本地初始化仓库路径要在项目下 cd /path/to/your/vue-project git init 4.创建touch .gitignore文件在项目根目录下创建 .gitignore 文件，用于指定 Git 忽略哪些文件或文件夹 5.添加和提交项目文件将文件提交到版本控…...

编程日记 2025/8/23 8:00:49

C++入门(上)--《Hello C++ World!》（1）(C/C++)

文章目录前言命名空间域命名空间的用法 C的输入和输出缺省参数函数重载auto关键字(C11)范围for 前言 C不是C# C兼容大部分C的东西，但不是完全(98%的样子，除非遇到了不兼容的，那就记一下，不然就认为自己在C里面写的那些可以写到C里…...

编程日记 2025/8/23 7:49:13

架构思维：构建高并发读服务_基于流量回放实现读服务的自动化测试回归方案

文章目录引言一、升级读服务架构，为什么需要自动化测试？二、自动化回归测试系统：整体架构概览三、日志收集1. 拦截方式2. 存储与优化策略3. 架构进化四、数据回放技术实现关键能力五、差异对比对比方式灵活配置六、三种回放模式详解1. 离…...

编程日记 2025/8/23 16:20:02

代码随想录第33天：动态规划6（完全背包基础）

一、完全平方数（Leetcode 279） 本题与“零钱兑换”基本一致。 1.确定dp数组以及下标的含义 dp[j]：和为j的完全平方数的最少数量为dp[j] 2.确定递推公式 dp[j] 可以由dp[j - i * i]推出， dp[j - i * i] 1 便可以凑成dp[j]。 …...

编程日记 2025/8/23 6:00:51

Android控件View、ImageView、WebView用法

一控件清单 View、ImageView、WebView 二控件UI代码 <?xml version="1.0" encoding="utf-8"?> <androidx.coordinatorlayout.widget.CoordinatorLayoutxmlns:android="http://schemas.android.com/apk/res/android"xmlns:app=&qu…...

编程日记 2025/8/23 1:00:06

关于浏览器页面自动化操作

Selenium 是一个用于自动化浏览器操作的强大框架，广泛应用于Web应用程序的测试自动化。它主要由以下几个核心组件组成： Selenium WebDriver： WebDriver 是 Selenium 的核心组件，它提供了一组API，允许开发者编写程序来…...

编程日记 2025/8/23 6:40:08

P5739 计算阶乘详解

此题目，对于会递归的很简单很简单，但作者是野人不会，只能是边刷边学，且题解比较有意思，所有我这次的重心不是题目，而是题解里面创作者展示的不一样的东西，先看题目题目要求不用for循环&#xf…...

编程日记 2025/8/23 6:20:02

把Android设备变成“国标摄像头”：GB28181移动终端实战接入指南

把Android设备变成“国标摄像头”：GB28181移动终端实战接入指南 ——执法记录仪、巡检终端、布控球，如何通过大牛直播SDK直接挂到GB28181平台？ 在过去，GB28181 通常用于固定摄像头、NVR等“设备端”。但在政务、安防、应急等行业…...

编程日记 2025/8/23 22:00:11

机器学习项目流程极简入门：从数据到部署的完整指南

前言本文将通过一个简单案例（根据水果外观特征判断是否为橘子），逐步拆解机器学习项目的完整流程，帮助读者掌握从数据收集到模型部署的全流程方法论。通常，一个完整的机器学习项目可以分为以下几个步骤： …...

编程日记 2025/8/23 10:20:01

PrivKV: Key-Value Data Collection with Local Differential Privacy论文阅读

文献阅读课需要制作ppt但是感觉选的这篇论文都是公式，决定做点动画直观展示一下。还没有完成会继续更新这个笔记 manim动画代码需要下载ffmpeg下载latex https://docs.manim.org.cn/getting_started/installation.html ffmpeg下载教程 texlive官网但是其实不需要…...

编程日记 2025/8/23 13:40:03

RViz（机器人可视化工具）的配置文件（moveitcpp）

1. Panels（面板设置） 面板是RViz界面中的各个功能区域，用于显示和操作不同的数据。 Displays（显示面板） Class: rviz_common/Displays 指定面板的类型，这里是显示面板。 Help Height: 78 帮助区域的高度…...

编程日记 2025/8/24 16:59:23

kotlin 01flow-StateFlow 完整教程

一 Android StateFlow 完整教程：从入门到实战 StateFlow 是 Kotlin 协程库中用于状态管理的响应式流，特别适合在 Android 应用开发中管理 UI 状态。本教程将带全面了解 StateFlow 的使用方法。 1. StateFlow 基础概念 1.1 什么是 StateFlow? StateF…...

编程日记 2025/8/23 20:40:03

多源最短路问题思路：

矩阵距离

相关文章：