信息学奥赛一本通 1885:【14NOIP提高组】寻找道路 | 洛谷 P2296 [NOIP2014 提高组] 寻找道路
【题目链接】
洛谷 P2296 [NOIP2014 提高组] 寻找道路
ybt 1885:【14NOIP提高组】寻找道路
【题目考点】
1. 图论:广搜
2. 图论:反图
【解题思路】
设path数组,path[i]表示顶点i出发到终点t是否有路径。
先求path数组,需要对原图建反图,而后从终点t开始进行广搜,广搜过程中访问到的顶点x,表示在反图中从t出发到顶点x有路径,也就是在正图中从顶点x到终点t存在路径。
设sel数组,sel[i]为真表示顶点i可以作为该题要选择的符合条件的路径上的点。
而后遍历所有顶点,对于顶点i,如果i到t有路径,且i的邻接点到t都有路径,那么顶点i可以作为符合条件的路径上的点。
最后从起点s出发进行广搜,求符合条件的路径的最短路径长度。求出从s出发到所有满足sel[i]为真的顶点i的最短路径长度dis[i]。最后dis[t]就是结果。
【题解代码】
解法1:广搜
#include <bits/stdc++.h>
using namespace std;
#define N 10005
bool vis[N], path[N], sel[N];//path[i]:i到t有路径 sel[i]:i以及i的邻接点都到t有路径
int n, m, s, t, dis[N];
vector<int> g[N], rg[N];//g:正图 rg:反图
void bfs1()
{queue<int> que;vis[t] = true;que.push(t);while(!que.empty()){int u = que.front();que.pop();path[u] = true;for(int v : rg[u]) if(!vis[v]){vis[v] = true;que.push(v);}}
}
int bfs2()
{if(sel[s] == false)return -1;queue<int> que;vis[s] = true;que.push(s);while(!que.empty()){int u = que.front();que.pop();if(u == t)return dis[u];for(int v : g[u]) if(!vis[v] && sel[v]){vis[v] = true;dis[v] = dis[u]+1; que.push(v);} }return -1;
}
bool check(int u)
{if(!path[u]) return false;for(int v : g[u]) if(!path[v])return false;return true;
}
int main()
{int x, y;cin >> n >> m;for(int i = 1; i <= m; ++i){cin >> x >> y;g[x].push_back(y);rg[y].push_back(x);}cin >> s >> t;bfs1();for(int i = 1; i <= n; ++i)sel[i] = check(i);memset(vis, 0, sizeof(vis));cout << bfs2(); return 0;
}
相关文章:
信息学奥赛一本通 1885:【14NOIP提高组】寻找道路 | 洛谷 P2296 [NOIP2014 提高组] 寻找道路
【题目链接】 洛谷 P2296 [NOIP2014 提高组] 寻找道路 ybt 1885:【14NOIP提高组】寻找道路 【题目考点】 1. 图论:广搜 2. 图论:反图 【解题思路】 设path数组,path[i]表示顶点i出发到终点t是否有路径。 先求path数组&#…...
JVM 基础、GC 算法与 JProfiler 监控工具详解
目录 1、引言 1.1 JVM内存与本地内存 1.2 JVM与JDK的关系 2、JVM基础 2.1 JVM(Java Virtual Machine) 2.2 Java与JVM的关系 2.3 JVM的内存结构 2.3.1 堆内存 2.3.2 栈内存 2.3.3 方法区 2.3.4 本地方法栈 2.3.5 程序计数器(PC寄存…...
nodejs安装及环境配置
一、下载 进入官网https://nodejs.org/en/download/prebuilt-installer下载node.js安装包,选择对应版本的node,这里我选择的是14.21.3版本 二、安装 1、下载完成后,双击“node-v14.21.3-x64.msi”,开始安装Node.js 2、勾选复…...
无人机电力巡检:点亮电力巡检新视野!
一、无人机电力巡查的优势 提高巡检效率:无人机可以搭载高清摄像头、红外热像仪等先进设备,实时拍摄和传输图像,帮助巡检人员快速发现潜在问题,如电线破损、绝缘子污损、设备过热等,从而大大缩短了巡检周期。 降低人…...
详细介绍:API 和 SPI 的区别
文章目录 Java SPI (Service Provider Interface) 和 API (Application Programming Interface) 的区别详解目录1. 定义和目的1.1 API (Application Programming Interface)1.2 SPI (Service Provider Interface) 2. 使用场景2.1 API 的应用场景2.2 SPI 的应用场景 3. 加载和调…...
【面向对象】设计模式概念和分类
零.前提提要 本文章是我考中级软件设计师时的笔记,基本都是一些自己的思路和见解,现记录一下,希望可以帮助到即将考证的同学。 一.面向对象设计模式的概念 二.面向对象的设计模式分类 设计模式确定了所包含的类和实例、他们的角色和写作方式以…...
APK安装包arm64-v8a、armeabi-v7a、x86、x86_64如何区别?(2024年10月1日)
其实就是安卓CPU的进步史 安卓CPU类型: arm64-v8a: 第8代、64位ARM处理器,目前手机大多数是此架构(新手机,可以无脑选择)armeabiv-v7a: 第七代及以上的 ARM 处理器。2011年5月以后生产的大部分安卓设备都使用它armeabi: 第5代、第6代的ARM处理器&#…...
【DataLoom】智能问数 - 自然语言与数据库交互
探索DataLoom的智能问数功能:简化数据库查询 在数据驱动的决策制定中,数据库查询是获取洞察的关键步骤。但是,传统的数据库查询方法往往复杂且技术性强,这限制了非技术用户的使用。DataLoom的智能问数功能正是为了解决这一问题而…...
【Linux】进程地址空间(初步了解)
文章目录 1. 奇怪的现象2. 虚拟地址空间3. 关于页表4. 为什么要有虚拟地址 1. 奇怪的现象 我们先看一个现象: 为什么父子进程从“同一块地址中”读取到的值不一样呢? 因为这个地址不是物理内存的地址 ,如果是物理内存的地址是绝对不可能出…...
hdu-6024
hdu-6024 struct node {int x, c;bool operator<(const node &a) const{return x < a.x;} }; // dp[i][0]为到第i个教室且第i个教室不建糖果店的花费前缀和,dp[i][1]为到第i个教室且第i个教室建糖果店的花费前缀和 int dp[N][2]; void solve() {int n;wh…...
jmeter操作数据库
jmeter操作数据库 一、打开数据库 二、jmeter下载驱动,安装jdbc驱动 1、下载好的驱动包 2、将驱动包复制粘贴 存放在包的路径下 (1)jdk下面 a、路径:jdk1\jre\lib b、jdk1\jre\lib\ext (2)jmeter下 a、…...
Stable Diffusion绘画 | 如何做到不同动作表情,人物角色保持一致性(上篇)
由于 SD 具有强大的可控性,在固定人物角色方面,SD 是远超 MJ 的, 其中最好用,也是最优先的方法就是训练一个自己专属的角色模型,例如之前使用秋叶训练器得到的 LoRA模型。 另外,如果不想自己训练模型的话…...
中国计量大学《2023年801+2023年819自动控制原理真题》 (完整版)
本文内容,全部选自自动化考研联盟的:《中国计量大学801819自控考研资料》的真题篇。后续会持续更新更多学校,更多年份的真题,记得关注哦~ 目录 2023年801真题 2023年819真题 Part1:2023年完整版真题 2023年801真题…...
本地运行LLama 3.2的三种方法
大型语言模型(LLMs)已经彻底改变了AI领域,小型模型也在崛起。因此,即使是在旧的PC和智能手机上运行先进的LLMs也成为了可能。为了给大家一个起点,我们将探索三种不同的方法来本地与LLama 3.2进行交互。 先决条件 在我…...
基于单片机的温度和烟雾检测
目录 一、主要功能 二、硬件资源 三、程序编程 四、实现现象 一、主要功能 基于51单片机,采用DS18B20读取温度,滑动变阻器链接ADC0832数模转换模拟烟雾, 通过lcd1602显示屏显示, 超过阈值则对应的led灯亮起,蜂鸣器…...
利士策分享,探寻中华民族的精神纽带
利士策分享,探寻中华民族的精神纽带 在历史的长河中,中华民族以其独特的文化魅力和坚韧不拔的民族精神,屹立于世界民族之林。 这份力量,源自何处?或许,正是那份纯真的情,如同纽带一般ÿ…...
JAVA思维提升案例3
需求: 某系统的数字密码是一个四位数,如1983,为了安全,需要加密后再传输,加密规则是:对密码中的每位数,都加5 ,再对10求余,最后将所有数字顺序反转,得到一串加密后的新数…...
vscode配置golang
1.安装golang解释器 从网址https://go.dev/dl/下载对应的golang解释器 2.配置环境 Extensions中搜索安装go 2.配置settings.json {"go.autocompleteUnimportedPackages": true,"go.gocodeAutoBuild": false,"explorer.confirmPasteNative"…...
设计模式之原型模式(通俗易懂--代码辅助理解【Java版】)
文章目录 设计模式概述1、原型模式2、原型模式的使用场景3、优点4、缺点5、主要角色6、代码示例7、总结题外话关于使用序列化实现深拷贝 设计模式概述 创建型模式:工厂方法、抽象方法、建造者、原型、单例。 结构型模式有:适配器、桥接、组合、装饰器、…...
Study-Oracle-10-ORALCE19C-RAC集群维护
一路走来,所有遇到的人,帮助过我的、伤害过我的都是朋友,没有一个是敌人。 一、RAC的逻辑架构与进程 1、RAC 与单实例进程的对比 2、RAC相关进程功能 3、在主机查看RAC进程 其他的不列举了 4、RAC集群启停命令 检查集群状态 ORACLE 19C …...
零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?
一、核心优势:专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发,是一款收费低廉但功能全面的Windows NAS工具,主打“无学习成本部署” 。与其他NAS软件相比,其优势在于: 无需硬件改造:将任意W…...
GC1808高性能24位立体声音频ADC芯片解析
1. 芯片概述 GC1808是一款24位立体声音频模数转换器(ADC),支持8kHz~96kHz采样率,集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器,适用于高保真音频采集场景。 2. 核心特性 高精度:24位分辨率,…...
听写流程自动化实践,轻量级教育辅助
随着智能教育工具的发展,越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式,也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建,…...
SiFli 52把Imagie图片,Font字体资源放在指定位置,编译成指定img.bin和font.bin的问题
分区配置 (ptab.json) img 属性介绍: img 属性指定分区存放的 image 名称,指定的 image 名称必须是当前工程生成的 binary 。 如果 binary 有多个文件,则以 proj_name:binary_name 格式指定文件名, proj_name 为工程 名&…...
VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP
编辑-虚拟网络编辑器-更改设置 选择桥接模式,然后找到相应的网卡(可以查看自己本机的网络连接) windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置,选择刚才配置的桥接模式 静态ip设置: 我用的ubuntu24桌…...
Java编程之桥接模式
定义 桥接模式(Bridge Pattern)属于结构型设计模式,它的核心意图是将抽象部分与实现部分分离,使它们可以独立地变化。这种模式通过组合关系来替代继承关系,从而降低了抽象和实现这两个可变维度之间的耦合度。 用例子…...
【C++特殊工具与技术】优化内存分配(一):C++中的内存分配
目录 一、C 内存的基本概念 1.1 内存的物理与逻辑结构 1.2 C 程序的内存区域划分 二、栈内存分配 2.1 栈内存的特点 2.2 栈内存分配示例 三、堆内存分配 3.1 new和delete操作符 4.2 内存泄漏与悬空指针问题 4.3 new和delete的重载 四、智能指针…...
C++ 设计模式 《小明的奶茶加料风波》
👨🎓 模式名称:装饰器模式(Decorator Pattern) 👦 小明最近上线了校园奶茶配送功能,业务火爆,大家都在加料: 有的同学要加波霸 🟤,有的要加椰果…...
jmeter聚合报告中参数详解
sample、average、min、max、90%line、95%line,99%line、Error错误率、吞吐量Thoughput、KB/sec每秒传输的数据量 sample(样本数) 表示测试中发送的请求数量,即测试执行了多少次请求。 单位,以个或者次数表示。 示例:…...
STM32---外部32.768K晶振(LSE)无法起振问题
晶振是否起振主要就检查两个1、晶振与MCU是否兼容;2、晶振的负载电容是否匹配 目录 一、判断晶振与MCU是否兼容 二、判断负载电容是否匹配 1. 晶振负载电容(CL)与匹配电容(CL1、CL2)的关系 2. 如何选择 CL1 和 CL…...
