信息学奥赛一本通 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 …...
从HC-SR04老用户视角,实测2020新版:盲区更小、功耗更低,但这两点不注意容易翻车
HC-SR04新版深度评测:老用户必看的5个升级细节与3个隐藏陷阱 第一次拿到2020版HC-SR04时,我差点以为发错了货——外观几乎和老版本一模一样,连螺丝孔位都分毫不差。但当我用示波器捕捉到仅2.1mA的工作电流时,才确信这确实是用上了…...
路沿模板,乐山水泥路面模板,40公分路面钢模哪里有名
打路面模板:乐山水泥路面的优质之选在道路建设中,打路面模板起着至关重要的作用。它不仅关系到路面的成型质量,还影响着整个工程的效率和成本。乐山地区对于道路建设的需求不断增加,尤其是在水泥路面的铺设方面,40公分…...
不只是安装:深入理解TI毫米波雷达开发套件(MMWCAS-RF-EVM)的软件生态与数据流
不只是安装:深入理解TI毫米波雷达开发套件(MMWCAS-RF-EVM)的软件生态与数据流 毫米波雷达技术正在重塑自动驾驶、工业检测和智能安防等领域,而TI的MMWCAS-RF-EVM评估板作为行业标杆工具,其真正的价值往往被简化为"…...
C语言结构体定义与自增运算符a++详解
有一个结构体名是stu,它当中包含着5个成员,其中一个成员是name,还有一个成员是num,另外一个成员是age,再有一个成员是group,最后一个成员是score。 除了不能初始化这一点外,结构体成员的定义方式…...
Galaxy UI组件库深度解析:3000+开源UI元素的完整实践手册
Galaxy UI组件库深度解析:3000开源UI元素的完整实践手册 【免费下载链接】galaxy The largest Open-Source UI Library! Community-made and free to use. Made with either CSS or Tailwind. 项目地址: https://gitcode.com/gh_mirrors/gal/galaxy 在当今快…...
Cursor Pro破解工具:如何通过开源技术方案实现AI编程助手无限制使用?
Cursor Pro破解工具:如何通过开源技术方案实现AI编程助手无限制使用? 【免费下载链接】cursor-free-vip [Support 0.45](Multi Language 多语言)自动注册 Cursor Ai ,自动重置机器ID , 免费升级使用Pro 功能…...
避坑指南:通达信DLL加密常见的5大误区与替代方案
通达信指标加密实战:5种DLL开发陷阱与零代码解决方案 在量化交易领域,指标公式的保护一直是开发者面临的棘手问题。最近三个月内,某金融开发者社区关于"通达信DLL加密失败"的求助帖增长了47%,暴露出传统加密方案存在显…...
避坑指南:lidar_align标定IMU外参时,loader.cpp源码修改与运动轨迹设计的那些关键细节
避坑指南:lidar_align标定IMU外参的核心细节与实战优化 在自动驾驶和机器人定位领域,激光雷达与IMU的联合标定是系统搭建的关键环节。许多开发者在初次使用lidar_align工具时会遇到各种问题——从源码适配的困惑到标定结果的不可靠。本文将深入剖析两个最…...
从安防摄像头到直播:手把手教你用ZLMediaKit搭建GB28181视频监控平台
从安防摄像头到直播:手把手教你用ZLMediaKit搭建GB28181视频监控平台 在智能安防和物联网快速发展的今天,视频监控系统的网络化和智能化已成为行业标配。GB28181作为国内视频监控领域的国家标准协议,实现了不同厂商设备间的互联互通。而ZLMed…...
别再写死代码了!用MCP Tool模块5分钟搞定AI与数据库的安全对话
别再写死代码了!用MCP Tool模块5分钟搞定AI与数据库的安全对话 当AI模型需要与数据库交互时,开发者常面临两难选择:要么直接暴露数据库连接信息,要么编写大量胶水代码。这两种方案都存在明显缺陷——前者带来安全隐患,…...
