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

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 条边的有向图&#xff0c;图中可能存在重边和自环。 所有边的长度都是 1 &#xff0c;点的编号为 1∼n 。 请你求出 1 号点到 n 号点的最短距离&#xff0c;如果从 1 号点无法走到 n 号点&#xff0c;输出 −1 。 输入格式 第一行包含两个整数 n 和 m 。 …...

k8s---pod控制器

pod控制器发的概念&#xff1a; 工作负载&#xff0c;workload用于管理pod的中间层&#xff0c;确保pod资源符合预期的状态。 预期状态&#xff1a; 1、副本数 2、容器重启策略 3、镜像拉取策略 pod出故障的出去等等 pod控制器的类型&#xff1a; 1、replicaset&#xf…...

2024.1.11力扣每日一题——构造有效字符串的最少插入数

2024.1.11 题目来源我的题解方法一 暴力模拟方法二 动态规划方法三 直接拼接方法四 计算组数 题目来源 力扣每日一题&#xff1b;题序&#xff1a;2645 我的题解 方法一 暴力模拟 直接模拟&#xff0c;根据题意可知 若是abc则不用插入&#xff0c;若是ab,ac,bc这需要 插入一…...

软件测试|如何使用Selenium处理隐藏元素

简介 我们在使用selenium进行web自动化测试时&#xff0c;有时候会遇到元素被隐藏&#xff0c;从而无法对元素进行操作&#xff0c;导致我们的用例报错的情况。当我们遇到元素被隐藏的情况时&#xff0c;需要先对隐藏的元素进行处理&#xff0c;才能继续进行我们的操作&#x…...

第三次面试总结 - 吉云集团 - 全栈开发

&#x1f9f8;欢迎来到dream_ready的博客&#xff0c;&#x1f4dc;相信您对专栏 “本人真实面经” 很感兴趣o (ˉ▽ˉ&#xff1b;) 专栏 —— 本人真实面经&#xff0c;更多真实面试经验&#xff0c;中大厂面试总结等您挖掘 目录 总结&#xff08;非详细&#xff09; 面试内…...

buuctf-Misc 题目解答分解118-120

118.[INSHack2017]sanity 打开压缩包就是一个md 文件 typora 打开 发现flag INSA{Youre_sane_Good_for_you} 119.粽子的来历 解压压缩包 &#xff0c;得到文件夹如下 用010 editor 打开 我是A.doc 这个有些可以 都改成FF 保存 然后再次打开 docx 文件就发现了屈原的诗 其他b…...

Hive数据定义(1)

hive数据定义是hive的基础知识&#xff0c;所包含的知识点有&#xff1a;数据仓库的创建、数据仓库的查询、数据仓库的修改、数据仓库的删除、表的创建、表的删除、内部表、外部表、分区表、桶表、表的修改、视图。本篇文章先介绍&#xff1a;数据仓库的创建、数据仓库的查询、…...

golang 反序列化出现json: cannot unmarshal string into Go value of type model.Phone

项目场景&#xff1a; 今天在项目公关的过程中&#xff0c;需要对interface{}类型进行转换为具体结构体 问题描述 很自然的用到了resultBytes, _ : json.Marshal(result)&#xff0c;然后对resultBytes进行反序列化转换为对应的结构体err : json.Unmarshal(resultBytes, &…...

【闯关练习】—— 1400分(构造)

&#x1f30f;博客主页&#xff1a;PH_modest的博客主页 &#x1f6a9;当前专栏&#xff1a;cf闯关练习 &#x1f48c;其他专栏&#xff1a; &#x1f534;每日一题 &#x1f7e1; C跬步积累 &#x1f7e2; C语言跬步积累 &#x1f308;座右铭&#xff1a;广积粮&#xff0c;缓…...

Qt QProgressBar进度条控件

文章目录 1 属性和方法1.1 值1.2 方向1.3 外观1.4 信号和槽 2 实例2.1 布局2.2 代码实现 QProgressBar是进度条控件&#xff0c;进度条用来指示任务的完成情况 1 属性和方法 QProgressBar有很多属性&#xff0c;完整的可查看帮助文档。这里以QProgressBar为例&#xff0c;列出…...

【新】Unity Meta Quest MR 开发(一):Passthrough 透视配置

文章目录 &#x1f4d5;教程说明&#x1f4d5;配置透视的串流调试功能&#x1f4d5;第一步&#xff1a;设置 OVRManager&#x1f4d5;第二步&#xff1a;添加 OVRPassthroughLayer 脚本&#x1f4d5;第三步&#xff1a;在场景中添加虚拟物体&#x1f4d5;第四步&#xff1a;设置…...

快速排序【hoare版本】【挖坑法】【双指针法】(数据结构)

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法&#xff0c;其基本思想为&#xff1a;任取待排序元素序列中 的某元素作为基准值&#xff0c;按照该排序码将待排序集合分割成两子序列&#xff0c;左子序列中所有元素均小于基准值&#xff0c;右子序列中所有元素均…...

class_5:在c++中一个类包含另一个类的对象叫做组合

#include <iostream> using namespace std;class Wheel{ public://成员数据string brand; //品牌int year; //年限//真正的成员函数void printWheelInfo(); //声明成员函数 };void Wheel::printWheelInfo() {cout<<"我的轮胎品牌是&#xff1a;"<…...

Linux - No space left on device

问题描述 No space left on device 原因分析 说明在服务器设备上的存储空间已经满了&#xff0c;不能再上传或者新建文件夹或者文件等。 解决方案 确认查看服务器系统的磁盘使用情况是否是真的已经没有剩余空间&#xff0c;复制下面命令在服务器上运行&#xff0c;然后发现如果…...

STC8H8K蓝牙智能巡线小车——2. 点亮左右转弯灯与危险报警灯

任务调用示例 RTX 51 TNY 可做多任务调度&#xff0c;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】个人资料页面编写

这一节完成用户个人信息昵称的填写和获取 上节编写完成后的页面如下所示&#xff1a; 首先进行用户昵称编辑功能的编写&#xff0c;铲屎官昵称采用了navigator标签&#xff0c;当点击昵称时会自动跳转到昵称编辑页面。 首先输入昵称编辑界面的导航栏名称 {"usingCompone…...

Linux笔记:Linux中的文件系统权限

在Red Hat Enterprise Linux 或其他类似的Linux发行版中&#xff0c;全局umask设置通常在几个不同的系统级配置文件中定义。以下是一些可能设置umask的地方&#xff1a; &#xff08;1&#xff09;/etc/profile: 这是为系统上的所有用户设置全局环境变量和启动程序的地方。通…...

Android基于Matrix绘制PaintDrawable设置BitmapShader,以手指触点为中心显示原图的圆切图,Kotlin(4)

Android基于Matrix绘制PaintDrawable设置BitmapShader&#xff0c;以手指触点为中心显示原图的圆切图&#xff0c;Kotlin&#xff08;4&#xff09; 这篇 Android基于Matrix绘制PaintDrawable设置BitmapShader&#xff0c;以手指触点为中心显示原图像圆图&#xff0c;Kotlin&am…...

WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED!

问题背景 当我们尝试通过SSH&#xff08;Secure Shell&#xff09;连接到远程服务器时&#xff0c;有时会遇到一个警告信息&#xff1a;“WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED!”。这个消息表明SSH客户端检测到远程主机的身份&#xff08;即其SSH密钥&#xff09…...

深入理解JVM虚拟机第三十九篇:JVM中新生代和老年代相关参数设置

😉😉 欢迎加入我们的学习交流群呀! ✅✅1:这是孙哥suns给大家的福利! ✨✨2:我们免费分享Netty、Dubbo、k8s、Mybatis、Spring、Security、Docker、Grpc、消息中间件、Rpc、SpringCloud等等很多应用和源码级别高质量视频和笔记资料,你想学的我们这里都有! 🥭🥭3:…...

eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)

说明&#xff1a; 想象一下&#xff0c;你正在用eNSP搭建一个虚拟的网络世界&#xff0c;里面有虚拟的路由器、交换机、电脑&#xff08;PC&#xff09;等等。这些设备都在你的电脑里面“运行”&#xff0c;它们之间可以互相通信&#xff0c;就像一个封闭的小王国。 但是&#…...

Appium+python自动化(十六)- ADB命令

简介 Android 调试桥(adb)是多种用途的工具&#xff0c;该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具&#xff0c;其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利&#xff0c;如安装和调试…...

Admin.Net中的消息通信SignalR解释

定义集线器接口 IOnlineUserHub public interface IOnlineUserHub {/// 在线用户列表Task OnlineUserList(OnlineUserList context);/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...

在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:

在 HarmonyOS 应用开发中&#xff0c;手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力&#xff0c;既支持点击、长按、拖拽等基础单一手势的精细控制&#xff0c;也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档&#xff0c…...

(二)原型模式

原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...

使用 SymPy 进行向量和矩阵的高级操作

在科学计算和工程领域&#xff0c;向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能&#xff0c;能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作&#xff0c;并通过具体…...

2023赣州旅游投资集团

单选题 1.“不登高山&#xff0c;不知天之高也&#xff1b;不临深溪&#xff0c;不知地之厚也。”这句话说明_____。 A、人的意识具有创造性 B、人的认识是独立于实践之外的 C、实践在认识过程中具有决定作用 D、人的一切知识都是从直接经验中获得的 参考答案: C 本题解…...

HDFS分布式存储 zookeeper

hadoop介绍 狭义上hadoop是指apache的一款开源软件 用java语言实现开源框架&#xff0c;允许使用简单的变成模型跨计算机对大型集群进行分布式处理&#xff08;1.海量的数据存储 2.海量数据的计算&#xff09;Hadoop核心组件 hdfs&#xff08;分布式文件存储系统&#xff09;&a…...

安宝特方案丨船舶智造的“AR+AI+作业标准化管理解决方案”(装配)

船舶制造装配管理现状&#xff1a;装配工作依赖人工经验&#xff0c;装配工人凭借长期实践积累的操作技巧完成零部件组装。企业通常制定了装配作业指导书&#xff0c;但在实际执行中&#xff0c;工人对指导书的理解和遵循程度参差不齐。 船舶装配过程中的挑战与需求 挑战 (1…...

LangChain知识库管理后端接口:数据库操作详解—— 构建本地知识库系统的基础《二》

这段 Python 代码是一个完整的 知识库数据库操作模块&#xff0c;用于对本地知识库系统中的知识库进行增删改查&#xff08;CRUD&#xff09;操作。它基于 SQLAlchemy ORM 框架 和一个自定义的装饰器 with_session 实现数据库会话管理。 &#x1f4d8; 一、整体功能概述 该模块…...