[NOIP 2014] 寻找道路
2024-08-30 23:31:14
[题目链接]
[算法]
首先,在反向图上从终点广搜,求出每个点是否可以在答案路径中
然后在正向图中求出源点至终点的最短路,同样可以使用广搜
时间复杂度 : O(N)
[代码]
#include<bits/stdc++.h>
using namespace std;
#define MAXN 10010
#define MAXM 200010 struct edge
{
int to,nxt;
} e[MAXM << ]; int i,n,m,u,v,s,t,tot;
int head[MAXN],rhead[MAXN],deg[MAXN];
bool flag[MAXN]; namespace IO
{
template <typename T> inline void read(T &x)
{
int f = ; x = ;
char c = getchar();
for (; !isdigit(c); c = getchar())
{
if (c == '-') f = -f;
}
for (; isdigit(c); c = getchar()) x = (x << ) + (x << ) + c - '';
x *= f;
}
template <typename T> inline void write(T x)
{
if (x < )
{
putchar('-');
x = -x;
}
if (x > ) write(x / );
putchar(x % + '');
}
template <typename T> inline void writeln(T x)
{
write(x);
puts("");
}
} ;
inline void addedge(int u,int v)
{
tot++;
e[tot] = (edge){v,head[u]};
head[u] = tot;
}
inline void addredge(int u,int v)
{
tot++;
e[tot] = (edge){v,rhead[u]};
rhead[u] = tot;
}
inline void bfs1(int s)
{
int i,u,v,l,r;
static int q[MAXN],cnt[MAXN];
static bool visited[MAXN];
for (i = ; i <= n; i++) cnt[i] = ;
q[l = r = ] = s;
flag[s] = true;
while (l <= r)
{
u = q[l];
l++;
for (i = rhead[u]; i; i = e[i].nxt)
{
v = e[i].to;
if (!visited[v])
{
visited[v] = true;
q[++r] = v;
}
cnt[v]++;
}
}
for (i = ; i <= n; i++) flag[i] = (cnt[i] == deg[i]);
}
inline int bfs2(int s)
{
int i,u,v,l,r;
static int q[MAXN],dist[MAXN];
static bool visited[MAXN];
if (!flag[s]) return -;
for (i = ; i <= n; i++) visited[i] = false;
q[l = r = ] = s;
dist[s] = ;
visited[s] = true;
while (l <= r)
{
u = q[l];
l++;
for (i = head[u]; i; i = e[i].nxt)
{
v = e[i].to;
if (!visited[v] && flag[v])
{
visited[v] = true;
dist[v] = dist[u] + ;
q[++r] = v;
}
}
}
return dist[t] > ? dist[t] : -;
} int main()
{ IO :: read(n); IO :: read(m);
for (i = ; i <= m; i++)
{
IO :: read(u); IO :: read(v);
addedge(u,v);
addredge(v,u);
deg[u]++;
}
IO :: read(s); IO :: read(t);
bfs1(t);
IO :: writeln(bfs2(s)); return ; }
最新文章
- Summary of Critical and Exploitable iOS Vulnerabilities in 2016
- android setDestinationInExternalPublicDir 下载到SD卡根目录
- C++静态成员和静态成员函数
- 【转】CSRF攻击的应对之道
- Backbone之旅——Model篇
- 如何使用Promise
- Leetcode:Repeated DNA Sequences详细题解
- CentOS搭建PHP服务器环境(LAMP)
- ASP.NET Zero--12.一个例子(5)商品分类管理-编辑分类
- bootstrap模态框总结
- Number()和new Number()的区别以及一种简单实现
- [c++项目]迷宫 控制台游戏
- UnicodeDecodeError: &#39;ascii&#39; codec can&#39;t decode byte
- 查看oracle 用户执行的sql语句历史记录
- java设计模式学习
- Windows查看端口被什么进程占用的简单方法----菜鸟养成
- 多进程vs多线程
- Java 常见面试题(一)
- oralce表空间使用情况查询
- 从底层谈WebGIS 原理设计与实现(五):WebGIS中通过行列号来换算出多种瓦片的URL 之在线地图