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

信息学奥赛一本通 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&#xff1a;【14NOIP提高组】寻找道路 【题目考点】 1. 图论&#xff1a;广搜 2. 图论&#xff1a;反图 【解题思路】 设path数组&#xff0c;path[i]表示顶点i出发到终点t是否有路径。 先求path数组&#…...

JVM 基础、GC 算法与 JProfiler 监控工具详解

目录 1、引言 1.1 JVM内存与本地内存 1.2 JVM与JDK的关系 2、JVM基础 2.1 JVM&#xff08;Java Virtual Machine&#xff09; 2.2 Java与JVM的关系 2.3 JVM的内存结构 2.3.1 堆内存 2.3.2 栈内存 2.3.3 方法区 2.3.4 本地方法栈 2.3.5 程序计数器&#xff08;PC寄存…...

nodejs安装及环境配置

一、下载 进入官网https://nodejs.org/en/download/prebuilt-installer下载node.js安装包&#xff0c;选择对应版本的node&#xff0c;这里我选择的是14.21.3版本 二、安装 1、下载完成后&#xff0c;双击“node-v14.21.3-x64.msi”&#xff0c;开始安装Node.js 2、勾选复…...

无人机电力巡检:点亮电力巡检新视野!

一、无人机电力巡查的优势 提高巡检效率&#xff1a;无人机可以搭载高清摄像头、红外热像仪等先进设备&#xff0c;实时拍摄和传输图像&#xff0c;帮助巡检人员快速发现潜在问题&#xff0c;如电线破损、绝缘子污损、设备过热等&#xff0c;从而大大缩短了巡检周期。 降低人…...

详细介绍: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. 加载和调…...

【面向对象】设计模式概念和分类

零.前提提要 本文章是我考中级软件设计师时的笔记&#xff0c;基本都是一些自己的思路和见解&#xff0c;现记录一下&#xff0c;希望可以帮助到即将考证的同学。 一.面向对象设计模式的概念 二.面向对象的设计模式分类 设计模式确定了所包含的类和实例、他们的角色和写作方式以…...

APK安装包arm64-v8a、armeabi-v7a、x86、x86_64如何区别?(2024年10月1日)

其实就是安卓CPU的进步史 安卓CPU类型: arm64-v8a: 第8代、64位ARM处理器&#xff0c;目前手机大多数是此架构(新手机&#xff0c;可以无脑选择)armeabiv-v7a: 第七代及以上的 ARM 处理器。2011年5月以后生产的大部分安卓设备都使用它armeabi: 第5代、第6代的ARM处理器&#…...

【DataLoom】智能问数 - 自然语言与数据库交互

探索DataLoom的智能问数功能&#xff1a;简化数据库查询 在数据驱动的决策制定中&#xff0c;数据库查询是获取洞察的关键步骤。但是&#xff0c;传统的数据库查询方法往往复杂且技术性强&#xff0c;这限制了非技术用户的使用。DataLoom的智能问数功能正是为了解决这一问题而…...

【Linux】进程地址空间(初步了解)

文章目录 1. 奇怪的现象2. 虚拟地址空间3. 关于页表4. 为什么要有虚拟地址 1. 奇怪的现象 我们先看一个现象&#xff1a; 为什么父子进程从“同一块地址中”读取到的值不一样呢&#xff1f; 因为这个地址不是物理内存的地址 &#xff0c;如果是物理内存的地址是绝对不可能出…...

hdu-6024

hdu-6024 struct node {int x, c;bool operator<(const node &a) const{return x < a.x;} }; // dp[i][0]为到第i个教室且第i个教室不建糖果店的花费前缀和&#xff0c;dp[i][1]为到第i个教室且第i个教室建糖果店的花费前缀和 int dp[N][2]; void solve() {int n;wh…...

jmeter操作数据库

jmeter操作数据库 一、打开数据库 二、jmeter下载驱动&#xff0c;安装jdbc驱动 1、下载好的驱动包 2、将驱动包复制粘贴 存放在包的路径下 &#xff08;1&#xff09;jdk下面 a、路径&#xff1a;jdk1\jre\lib b、jdk1\jre\lib\ext &#xff08;2&#xff09;jmeter下 a、…...

Stable Diffusion绘画 | 如何做到不同动作表情,人物角色保持一致性(上篇)

由于 SD 具有强大的可控性&#xff0c;在固定人物角色方面&#xff0c;SD 是远超 MJ 的&#xff0c; 其中最好用&#xff0c;也是最优先的方法就是训练一个自己专属的角色模型&#xff0c;例如之前使用秋叶训练器得到的 LoRA模型。 另外&#xff0c;如果不想自己训练模型的话…...

中国计量大学《2023年801+2023年819自动控制原理真题》 (完整版)

本文内容&#xff0c;全部选自自动化考研联盟的&#xff1a;《中国计量大学801819自控考研资料》的真题篇。后续会持续更新更多学校&#xff0c;更多年份的真题&#xff0c;记得关注哦~ 目录 2023年801真题 2023年819真题 Part1&#xff1a;2023年完整版真题 2023年801真题…...

本地运行LLama 3.2的三种方法

大型语言模型&#xff08;LLMs&#xff09;已经彻底改变了AI领域&#xff0c;小型模型也在崛起。因此&#xff0c;即使是在旧的PC和智能手机上运行先进的LLMs也成为了可能。为了给大家一个起点&#xff0c;我们将探索三种不同的方法来本地与LLama 3.2进行交互。 先决条件 在我…...

基于单片机的温度和烟雾检测

目录 一、主要功能 二、硬件资源 三、程序编程 四、实现现象 一、主要功能 基于51单片机&#xff0c;采用DS18B20读取温度&#xff0c;滑动变阻器链接ADC0832数模转换模拟烟雾&#xff0c; 通过lcd1602显示屏显示&#xff0c; 超过阈值则对应的led灯亮起&#xff0c;蜂鸣器…...

利士策分享,探寻中华民族的精神纽带

利士策分享&#xff0c;探寻中华民族的精神纽带 在历史的长河中&#xff0c;中华民族以其独特的文化魅力和坚韧不拔的民族精神&#xff0c;屹立于世界民族之林。 这份力量&#xff0c;源自何处&#xff1f;或许&#xff0c;正是那份纯真的情&#xff0c;如同纽带一般&#xff…...

JAVA思维提升案例3

需求&#xff1a; 某系统的数字密码是一个四位数&#xff0c;如1983&#xff0c;为了安全&#xff0c;需要加密后再传输&#xff0c;加密规则是&#xff1a;对密码中的每位数&#xff0c;都加5 ,再对10求余&#xff0c;最后将所有数字顺序反转&#xff0c;得到一串加密后的新数…...

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、总结题外话关于使用序列化实现深拷贝 设计模式概述 创建型模式&#xff1a;工厂方法、抽象方法、建造者、原型、单例。 结构型模式有&#xff1a;适配器、桥接、组合、装饰器、…...

Study-Oracle-10-ORALCE19C-RAC集群维护

一路走来&#xff0c;所有遇到的人&#xff0c;帮助过我的、伤害过我的都是朋友&#xff0c;没有一个是敌人。 一、RAC的逻辑架构与进程 1、RAC 与单实例进程的对比 2、RAC相关进程功能 3、在主机查看RAC进程 其他的不列举了 4、RAC集群启停命令 检查集群状态 ORACLE 19C …...

MediaPipe农业智能化:10个精准农业与作物监测的创新应用

MediaPipe农业智能化&#xff1a;10个精准农业与作物监测的创新应用 【免费下载链接】mediapipe Cross-platform, customizable ML solutions for live and streaming media. 项目地址: https://gitcode.com/GitHub_Trending/med/mediapipe MediaPipe作为谷歌开源的跨平…...

新手入门DetectionLab:10个步骤掌握企业网络安全检测基础

新手入门DetectionLab&#xff1a;10个步骤掌握企业网络安全检测基础 【免费下载链接】DetectionLab clong/DetectionLab: DetectionLab是一个开源项目&#xff0c;旨在建立一个高度可配置的虚拟环境以模拟企业网络&#xff0c;用于检测恶意活动、演练入侵检测系统&#xff08;…...

springboot+vue基于web的校园招聘求职系统

目录同行可拿货,招校园代理 ,本人源头供货商系统功能模块划分关键技术实现数据安全设计扩展性考虑项目技术支持源码获取详细视频演示 &#xff1a;文章底部获取博主联系方式&#xff01;同行可合作同行可拿货,招校园代理 ,本人源头供货商 系统功能模块划分 后端&#xff08;S…...

桌面高颜值时钟工具,支持置顶鼠标穿透

软件介绍 今天要说的这款工具叫WithClock&#xff0c;它是一个时钟工具。这款工具的设计特别简洁&#xff0c;看着很舒服&#xff0c;没什么多余的东西&#xff0c;颜值也挺高。 功能操作 它支持鼠标穿透&#xff0c;你只需要在时钟上点右键&#xff0c;选择“置顶”&#xf…...

告别重复造轮子:用快马AI一键生成高复用性imToken集成代码模块

告别重复造轮子&#xff1a;用快马AI一键生成高复用性imToken集成代码模块 开发涉及钱包集成的DApp时&#xff0c;最让人头疼的就是那些重复性的基础代码。每次新项目都要重新写一遍连接钱包、处理授权、监听网络切换的逻辑&#xff0c;不仅浪费时间&#xff0c;还容易引入安全…...

从原理到实战:位运算巧解最小码距(附完整代码)

1. 什么是码距&#xff1f;从生活场景理解概念 第一次听到"码距"这个词时&#xff0c;我脑海里浮现的是超市货架上相似商品间的距离。后来才发现&#xff0c;在计算机世界里&#xff0c;它描述的是两个编码之间的差异程度。举个生活中的例子&#xff1a;假设我们用5…...

云容笔谈在自媒体内容生产中的提效实践:日更国风配图效率提升300%

云容笔谈在自媒体内容生产中的提效实践&#xff1a;日更国风配图效率提升300% 1. 自媒体内容创作的痛点与挑战 作为自媒体创作者&#xff0c;每天最头疼的就是配图问题。特别是做国风内容的账号&#xff0c;既要保持东方美学韵味&#xff0c;又要保证日更频率&#xff0c;传统…...

ai辅助硬件设计:让快马智能解析并生成db9接口与mcu连接的完整原理图与代码

在硬件开发中&#xff0c;DB9接口的设计与连接是个常见但容易出错的环节。最近我在一个嵌入式项目里需要实现STM32与DB9接口的RS-232通信&#xff0c;发现传统设计流程存在几个痛点&#xff1a; 引脚定义容易混淆 DB9公头和母头的引脚定义是相反的&#xff0c;比如母头的2号引脚…...

深入解析cufftPlanMany:从参数配置到高效FFT实现

1. 为什么需要cufftPlanMany&#xff1f; 第一次接触CUDA FFT时&#xff0c;很多人都是从cufftPlan1d、cufftPlan2d这些基础接口开始的。但当你真正处理实际工程问题时&#xff0c;会发现这些简单接口远远不够用。比如要处理批量信号、非连续内存数据、子区域FFT计算等场景时&a…...

ROS2开发避坑:用CycloneDDS配置文件解决本地回环通信中断问题(附完整XML)

ROS2通信稳定性实战&#xff1a;CycloneDDS深度配置指南 当你在机器人开发过程中遭遇节点间通信时断时续的问题&#xff0c;那种感觉就像在暴雨天试图用对讲机协调团队——关键指令总在最重要时刻丢失。本文将揭示如何通过CycloneDDS的精细配置&#xff0c;在硬件网络不稳定的…...