当前位置: 首页 > 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;
} 
http://www.lryc.cn/news/453344.html

相关文章:

  • JVM 基础、GC 算法与 JProfiler 监控工具详解
  • nodejs安装及环境配置
  • 无人机电力巡检:点亮电力巡检新视野!
  • 详细介绍:API 和 SPI 的区别
  • 【面向对象】设计模式概念和分类
  • APK安装包arm64-v8a、armeabi-v7a、x86、x86_64如何区别?(2024年10月1日)
  • 【DataLoom】智能问数 - 自然语言与数据库交互
  • 【Linux】进程地址空间(初步了解)
  • hdu-6024
  • jmeter操作数据库
  • Stable Diffusion绘画 | 如何做到不同动作表情,人物角色保持一致性(上篇)
  • 中国计量大学《2023年801+2023年819自动控制原理真题》 (完整版)
  • 本地运行LLama 3.2的三种方法
  • 基于单片机的温度和烟雾检测
  • 利士策分享,探寻中华民族的精神纽带
  • JAVA思维提升案例3
  • vscode配置golang
  • 设计模式之原型模式(通俗易懂--代码辅助理解【Java版】)
  • Study-Oracle-10-ORALCE19C-RAC集群维护
  • 【无题】夜入伊人笑愉,泪湿心夜难眠。
  • docker下载mysql时出现Unable to pull mysql:latest (HTTP code 500) server error 问题
  • 厦门网站设计的用户体验优化策略
  • Fastjson反序列化
  • Python Linux解压安装脚本
  • numpy 逻辑运算方法介绍
  • 怎么查看网站是否被谷歌收录,查看网站是否被谷歌收录的简便方法
  • 【前端开发入门】前端开发环境配置
  • Windows驱动开发(二)
  • Hotspot是什么?
  • k8s-集群部署1