C++ 树与图的广度优先遍历 || 模版题 :图中点的层次
给定一个 n
个点 m
条边的有向图,图中可能存在重边和自环。
所有边的长度都是 1
,点的编号为 1∼n
。
请你求出 1
号点到 n
号点的最短距离,如果从 1
号点无法走到 n
号点,输出 −1
。
输入格式
第一行包含两个整数 n
和 m
。
接下来 m
行,每行包含两个整数 a
和 b
,表示存在一条从 a
走到 b
的长度为 1
的边。
输出格式
输出一个整数,表示 1
号点到 n
号点的最短距离。
数据范围
1≤n,m≤105
输入样例:
4 5
1 2
2 3
3 4
1 3
1 4
输出样例:
1
#include <iostream>
#include <cstring>
using namespace std;const int N = 10010;int n, m;
int h[N], e[N], ne[N], idx; //邻接表
int d[N], q[N]; //d是距离,q是队列void add(int a, int b)
{e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}int bfs()
{int hh = 0, tt = 0;q[0] = 1; //第一个元素是起点1memset(d, -1, sizeof d);d[1] = 0;while(hh <= tt){int t = q[hh ++ ];for(int i = h[t]; i != -1; i = ne[i]){int j = e[i];if(d[j] == -1){d[j] = d[t] + 1;q[ ++ tt] = j;}}}return d[n];
}int main ()
{cin>>n>>m;memset(h, -1, sizeof h);for(int i = 0; i < m; i ++ ){int a, b;cin>>a>>b;add(a, b);}cout<<bfs()<<endl;return 0;}
相关文章:
C++ 树与图的广度优先遍历 || 模版题 :图中点的层次
给定一个 n 个点 m 条边的有向图,图中可能存在重边和自环。 所有边的长度都是 1 ,点的编号为 1∼n 。 请你求出 1 号点到 n 号点的最短距离,如果从 1 号点无法走到 n 号点,输出 −1 。 输入格式 第一行包含两个整数 n 和 m 。 …...
k8s---pod控制器
pod控制器发的概念: 工作负载,workload用于管理pod的中间层,确保pod资源符合预期的状态。 预期状态: 1、副本数 2、容器重启策略 3、镜像拉取策略 pod出故障的出去等等 pod控制器的类型: 1、replicaset…...
2024.1.11力扣每日一题——构造有效字符串的最少插入数
2024.1.11 题目来源我的题解方法一 暴力模拟方法二 动态规划方法三 直接拼接方法四 计算组数 题目来源 力扣每日一题;题序:2645 我的题解 方法一 暴力模拟 直接模拟,根据题意可知 若是abc则不用插入,若是ab,ac,bc这需要 插入一…...
软件测试|如何使用Selenium处理隐藏元素
简介 我们在使用selenium进行web自动化测试时,有时候会遇到元素被隐藏,从而无法对元素进行操作,导致我们的用例报错的情况。当我们遇到元素被隐藏的情况时,需要先对隐藏的元素进行处理,才能继续进行我们的操作&#x…...
第三次面试总结 - 吉云集团 - 全栈开发
🧸欢迎来到dream_ready的博客,📜相信您对专栏 “本人真实面经” 很感兴趣o (ˉ▽ˉ;) 专栏 —— 本人真实面经,更多真实面试经验,中大厂面试总结等您挖掘 目录 总结(非详细) 面试内…...
buuctf-Misc 题目解答分解118-120
118.[INSHack2017]sanity 打开压缩包就是一个md 文件 typora 打开 发现flag INSA{Youre_sane_Good_for_you} 119.粽子的来历 解压压缩包 ,得到文件夹如下 用010 editor 打开 我是A.doc 这个有些可以 都改成FF 保存 然后再次打开 docx 文件就发现了屈原的诗 其他b…...
Hive数据定义(1)
hive数据定义是hive的基础知识,所包含的知识点有:数据仓库的创建、数据仓库的查询、数据仓库的修改、数据仓库的删除、表的创建、表的删除、内部表、外部表、分区表、桶表、表的修改、视图。本篇文章先介绍:数据仓库的创建、数据仓库的查询、…...
golang 反序列化出现json: cannot unmarshal string into Go value of type model.Phone
项目场景: 今天在项目公关的过程中,需要对interface{}类型进行转换为具体结构体 问题描述 很自然的用到了resultBytes, _ : json.Marshal(result),然后对resultBytes进行反序列化转换为对应的结构体err : json.Unmarshal(resultBytes, &…...
【闯关练习】—— 1400分(构造)
🌏博客主页:PH_modest的博客主页 🚩当前专栏:cf闯关练习 💌其他专栏: 🔴每日一题 🟡 C跬步积累 🟢 C语言跬步积累 🌈座右铭:广积粮,缓…...
Qt QProgressBar进度条控件
文章目录 1 属性和方法1.1 值1.2 方向1.3 外观1.4 信号和槽 2 实例2.1 布局2.2 代码实现 QProgressBar是进度条控件,进度条用来指示任务的完成情况 1 属性和方法 QProgressBar有很多属性,完整的可查看帮助文档。这里以QProgressBar为例,列出…...
【新】Unity Meta Quest MR 开发(一):Passthrough 透视配置
文章目录 📕教程说明📕配置透视的串流调试功能📕第一步:设置 OVRManager📕第二步:添加 OVRPassthroughLayer 脚本📕第三步:在场景中添加虚拟物体📕第四步:设置…...
快速排序【hoare版本】【挖坑法】【双指针法】(数据结构)
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法,其基本思想为:任取待排序元素序列中 的某元素作为基准值,按照该排序码将待排序集合分割成两子序列,左子序列中所有元素均小于基准值,右子序列中所有元素均…...
class_5:在c++中一个类包含另一个类的对象叫做组合
#include <iostream> using namespace std;class Wheel{ public://成员数据string brand; //品牌int year; //年限//真正的成员函数void printWheelInfo(); //声明成员函数 };void Wheel::printWheelInfo() {cout<<"我的轮胎品牌是:"<…...
Linux - No space left on device
问题描述 No space left on device 原因分析 说明在服务器设备上的存储空间已经满了,不能再上传或者新建文件夹或者文件等。 解决方案 确认查看服务器系统的磁盘使用情况是否是真的已经没有剩余空间,复制下面命令在服务器上运行,然后发现如果…...
STC8H8K蓝牙智能巡线小车——2. 点亮左右转弯灯与危险报警灯
任务调用示例 RTX 51 TNY 可做多任务调度,API较为简单。 /* 接口API */// 创建任务 extern unsigned char os_create_task (unsigned char task_id); // 结束任务 extern unsigned char os_delete_task (unsigned char task_id);// 等待 extern unsig…...
【微信小程序独立开发 3】个人资料页面编写
这一节完成用户个人信息昵称的填写和获取 上节编写完成后的页面如下所示: 首先进行用户昵称编辑功能的编写,铲屎官昵称采用了navigator标签,当点击昵称时会自动跳转到昵称编辑页面。 首先输入昵称编辑界面的导航栏名称 {"usingCompone…...
Linux笔记:Linux中的文件系统权限
在Red Hat Enterprise Linux 或其他类似的Linux发行版中,全局umask设置通常在几个不同的系统级配置文件中定义。以下是一些可能设置umask的地方: (1)/etc/profile: 这是为系统上的所有用户设置全局环境变量和启动程序的地方。通…...
Android基于Matrix绘制PaintDrawable设置BitmapShader,以手指触点为中心显示原图的圆切图,Kotlin(4)
Android基于Matrix绘制PaintDrawable设置BitmapShader,以手指触点为中心显示原图的圆切图,Kotlin(4) 这篇 Android基于Matrix绘制PaintDrawable设置BitmapShader,以手指触点为中心显示原图像圆图,Kotlin&am…...
WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED!
问题背景 当我们尝试通过SSH(Secure Shell)连接到远程服务器时,有时会遇到一个警告信息:“WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED!”。这个消息表明SSH客户端检测到远程主机的身份(即其SSH密钥)…...
深入理解JVM虚拟机第三十九篇:JVM中新生代和老年代相关参数设置
😉😉 欢迎加入我们的学习交流群呀! ✅✅1:这是孙哥suns给大家的福利! ✨✨2:我们免费分享Netty、Dubbo、k8s、Mybatis、Spring、Security、Docker、Grpc、消息中间件、Rpc、SpringCloud等等很多应用和源码级别高质量视频和笔记资料,你想学的我们这里都有! 🥭🥭3:…...
给汽车ECU做“体检报告”:手把手解读Basetech OCC计数器里的5个关键指标
给汽车ECU做“体检报告”:手把手解读Basetech OCC计数器里的5个关键指标 当一辆车亮起故障灯开进维修车间,维修技师的第一反应往往是连接诊断仪读取数据。但面对屏幕上密密麻麻的OCC计数器数值,很多新手会感到无从下手——这些数字到底在说什…...
避坑指南:Pyannote3.1+Whisper本地部署的5个常见报错解决方案
避坑指南:Pyannote3.1Whisper本地部署的5个常见报错解决方案 语音处理技术正在重塑教育、会议记录和客服质检等场景的交互方式。当开发者尝试将Whisper的精准语音识别与Pyannote的说话人分离能力结合时,常会在环境配置环节遭遇"拦路虎"。本文…...
手把手教你用ESP8266 AT指令连接华为云IoT(附固件烧录与MQTT避坑指南)
从零玩转ESP8266:华为云IoT连接实战与深度排错指南 当你第一次拿到那块拇指大小的ESP8266模块时,可能不会想到这个售价不到20元的Wi-Fi芯片能成为物联网世界的通行证。作为全球使用量最大的IoT连接方案之一,ESP8266配合华为云物联网平台&…...
GD32F4开发板GD-LINK驱动安装与Keil配置全攻略(附常见问题解决)
GD32F4开发板GD-LINK驱动安装与Keil配置全攻略(附常见问题解决) 第一次拿到GD32F4开发板时,很多开发者都会遇到驱动安装失败、Keil识别不到芯片的问题。这些问题看似简单,却可能让新手折腾好几个小时。本文将用最直白的方式&#…...
Leather Dress Collection惊艳效果:Leather_Romper皮连体衣+户外场景自然光渲染
Leather Dress Collection惊艳效果:Leather_Romper皮连体衣户外场景自然光渲染 1. 项目介绍 Leather Dress Collection 是一个基于Stable Diffusion 1.5的LoRA模型集合,专门用于生成各种皮革服装风格的图像。这个系列由Stable Yogi开发,包含…...
告别单打独斗!Apipost 8协作版数据迁移保姆级教程(含团队项目处理)
Apipost 8协作版数据迁移实战:从个人到团队的无缝衔接 第一次打开Apipost 8协作版时,我盯着那个"迁入项目"按钮犹豫了整整十分钟——作为独立开发者,我的旧版本里积累了237个接口文档和56个测试集合,它们就像我精心搭建…...
信捷XD/XL系列PLC与C#通信实战:Modbus-RTU协议详解(附完整代码)
信捷XD/XL系列PLC与C#深度通信指南:从Modbus-RTU协议到工业级代码实现 在工业自动化领域,PLC与上位机的稳定通信是系统集成的核心环节。信捷XD/XL系列PLC凭借其出色的性价比和丰富的功能接口,已成为中小型自动化项目的热门选择。而C#作为.NET…...
DOL-CHS-MODS实战指南:从入门到精通的5个关键步骤
DOL-CHS-MODS实战指南:从入门到精通的5个关键步骤 【免费下载链接】DOL-CHS-MODS Degrees of Lewdity 整合 项目地址: https://gitcode.com/gh_mirrors/do/DOL-CHS-MODS 副标题:一站式解决Degrees of Lewdity汉化与Mod整合难题,让你轻…...
OpCore Simplify:零基础黑苹果配置的智能助手
OpCore Simplify:零基础黑苹果配置的智能助手 【免费下载链接】OpCore-Simplify A tool designed to simplify the creation of OpenCore EFI 项目地址: https://gitcode.com/GitHub_Trending/op/OpCore-Simplify 对于许多电脑爱好者来说,安装黑苹…...
腾讯混元翻译模型实战:跨境电商多语言商品描述生成案例
腾讯混元翻译模型实战:跨境电商多语言商品描述生成案例 1. 项目背景与价值 跨境电商企业面临一个共同挑战:如何高效地将商品信息翻译成多种语言。传统人工翻译成本高、周期长,而通用翻译工具又难以满足电商场景的专业需求。 腾讯混元翻译模…...
