3731 寻找道路
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 黄金 Gold
题目描述 Description
在有向图G中，每条边的长度均为1，现给定起点和终点，请你在图中找一条从起点到终点的路径，该路径满足以下条件：
1．路径上的所有点的出边所指向的点都直接或间接与终点连通。
2．在满足条件1的情况下使路径最短。
注意：图G中可能存在重边和自环，题目保证终点没有出边。
请你输出符合条件的路径的长度。
输入描述 Input Description
第一行有两个用一个空格隔开的整数n和m，表示图有n个点和m条边。
接下来的m行每行2个整数x、y，之间用一个空格隔开，表示有一条边从点x指向点y。
最后一行有两个用一个空格隔开的整数s、t，表示起点为s，终点为t。
输出描述 Output Description
输出文件名为road.out。
输出只有一行，包含一个整数，表示满足题目描述的最短路径的长度。如果这样的路径不存在，输出-1。
样例输入 Sample Input
road.in
3 2
1 2
2 1
1 3
road.out
－1
样例输出 Sample Output
road.in
6 6
1 2
1 3
2 6
2 5
4 5
3 4
1 5
road.out
3
数据范围及提示 Data Size & Hint
对于30%的数据，0< n ≤10，0< m ≤20；
对于60%的数据，0< n ≤100，0< m ≤2000；
对于100%的数据，0< n ≤10,000，0< m ≤200,000，0< x,y,s,t≤n，x≠t。
分类标签 Tags
NOIP全国联赛提高组 2014年
/*
这个题做的时候出了一点点小问题(是小问题吗！)
一开始不会怎么标记相邻点(10000^2数组会爆)
其实是可以用vector的orz.
我们只需要在spfa更新的时候判断这个点是否合法
(即这个点相连边的终点都合法)就可以了.
bfs的时候也出了点问题orz.
其实这题环和重边都能处理.
有向图不必判环.
还有别没扫完图就return
(如果要处理的东西以后还用的话).
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#define MAXM 200001
#define MAXN 10001
using namespace std;
int tot,n,m,x[MAXM],y[MAXM],head[MAXM],dis[MAXN],pre[MAXN];
bool b[MAXN<<1],vis[MAXN<<1];
struct data
{
int v;
int next;
}e[MAXM<<1];
int read()
{
int x=0;char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+(ch-48);
return x;
}
void add(int u,int v)
{
e[++tot].v=v;
e[tot].next=head[u];
head[u]=tot;
}
bool bfs(int x,int y)
{
int u,v,q[MAXN<<1]={0},cut[MAXN]={0},head1=0,tail=0;
q[++tail]=x;vis[x]=true;
while(head1<=tail)
{
head1++;
u=q[head1];
for(int i=head[u];i;i=e[i].next)
{
v=e[i].v;
if(!vis[v])
{
cut[v]++;
vis[v]=true;
q[++tail]=v;
}
}
}
if(vis[y]) return true;
return false;
}
bool check(int u)
{
if(!vis[u]) return false;
for(int i=head[u];i;i=e[i].next)
{
if(!vis[e[i].v]) return false;
}
return true;
}
void spfa(int x,int y)
{
memset(b,0,sizeof(b));
memset(dis,127/3,sizeof(dis));
int u,v,q[MAXN<<1]={0},head1=0,tail=0;
q[++tail]=x;b[x]=true;dis[x]=0;
while(head1<=tail)
{
head1++;
u=q[head1];
if(!check(u)) continue;
for(int i=head[u];i;i=e[i].next)
{
v=e[i].v;
if(dis[v]>dis[u]+1)
{
dis[v]=dis[u]+1;pre[v]=u;
if(!b[v])
{
b[v]=true;
q[++tail]=v;
}
}
}
}
if(dis[y]==dis[0]) printf("-1");
else printf("%d",dis[y]);
return ;
}
void slove(int u,int v)
{
tot=0;
memset(head,0,sizeof(head));
for(int i=1;i<=m;i++)
{
add(x[i],y[i]);
}
spfa(u,v);
return ;
}
int main()
{
int u,v;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x[i],&y[i]);
add(y[i],x[i]);
}
scanf("%d%d",&u,&v);
if(!bfs(v,u)) printf("-1");
else slove(u,v);
return 0;
}