信息学奥赛一本通 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 …...
观成科技:隐蔽隧道工具Ligolo-ng加密流量分析
1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具,该工具基于TUN接口实现其功能,利用反向TCP/TLS连接建立一条隐蔽的通信信道,支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式,适应复杂网…...
HTML 语义化
目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案: 语义化标签: <header>:页头<nav>:导航<main>:主要内容<article>&#x…...
Vue记事本应用实现教程
文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展:显示创建时间8. 功能扩展:记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...
AI Agent与Agentic AI:原理、应用、挑战与未来展望
文章目录 一、引言二、AI Agent与Agentic AI的兴起2.1 技术契机与生态成熟2.2 Agent的定义与特征2.3 Agent的发展历程 三、AI Agent的核心技术栈解密3.1 感知模块代码示例:使用Python和OpenCV进行图像识别 3.2 认知与决策模块代码示例:使用OpenAI GPT-3进…...
以下是对华为 HarmonyOS NETX 5属性动画(ArkTS)文档的结构化整理,通过层级标题、表格和代码块提升可读性:
一、属性动画概述NETX 作用:实现组件通用属性的渐变过渡效果,提升用户体验。支持属性:width、height、backgroundColor、opacity、scale、rotate、translate等。注意事项: 布局类属性(如宽高)变化时&#…...
前端倒计时误差!
提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...
macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用
文章目录 问题现象问题原因解决办法 问题现象 macOS启动台(Launchpad)多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显,都是Google家的办公全家桶。这些应用并不是通过独立安装的…...
CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云
目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...
破解路内监管盲区:免布线低位视频桩重塑停车管理新标准
城市路内停车管理常因行道树遮挡、高位设备盲区等问题,导致车牌识别率低、逃费率高,传统模式在复杂路段束手无策。免布线低位视频桩凭借超低视角部署与智能算法,正成为破局关键。该设备安装于车位侧方0.5-0.7米高度,直接规避树枝遮…...
comfyui 工作流中 图生视频 如何增加视频的长度到5秒
comfyUI 工作流怎么可以生成更长的视频。除了硬件显存要求之外还有别的方法吗? 在ComfyUI中实现图生视频并延长到5秒,需要结合多个扩展和技巧。以下是完整解决方案: 核心工作流配置(24fps下5秒120帧) #mermaid-svg-yP…...
