题目描述
在有向图G中,每条边的长度均为1,现给定起点和终点,请你在图中找一条从起点到终点的路径,该路径满足以下条件:
1.路径上的所有点的出边所指向的点都直接或间接与终点连通。
2.在满足条件1的情况下使路径最短。
注意:图G中可能存在重边和自环,题目保证终点没有出边。
请你输出符合条件的路径的长度。
输入格式
第一行有两个用一个空格隔开的整数n和m,表示图有n个点和m条边。
接下来的m行每行2个整数x、y,之间用一个空格隔开,表示有一条边从点x指向点y。
最后一行有两个用一个空格隔开的整数s、t,表示起点为s,终点为t。
输出格式
输出只有一行,包含一个整数,表示满足题目描述的最短路径的长度。
如果这样的路径不存在,输出-1。
数据范围
0<n≤10000,
0<m≤200000,
0<x,y,s,t≤n,s≠t
样例
输入样例:
6 6
1 2
1 3
2 6
2 5
4 5
3 4
1 5
输出样例:
3
我们可以先检验出每一个点是否能到终点。可以从终点出发,按照反向边走一遍,然后把走不到的点以及它的入边连的点都删掉
O((m+n)logn)
C++ 代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N=10010,M=200010;
int h1[N],e1[M],ne1[M],idx1;//邻接表(原图)
int h2[N],e2[M],ne2[M],idx2;//邻接表(反向图)
int n,m;
int s,t;
bool v[N];
int d[N];
inline void add(int a,int b)//邻接表存图
{
e1[idx1]=b,ne1[idx1]=h1[a],h1[a]=idx1++;//原图
e2[idx2]=a;ne2[idx2]=h2[b],h2[b]=idx2++;//反向建图
}
inline void bfs1(int cur)
{
queue<int>q;
q.push(cur);
v[cur]=1;
while(!q.empty())
{
int x=q.front();
q.pop();
for(int i=h2[x];~i;i=ne2[i])//遍历每一个点
{
int y=e2[i];
if(!v[y])
{
v[y]=1;
q.push(y);
}
}
}
}
inline bool check(int cur) //判断是否能到达终点
{
for(int i=h1[cur];~i;i=ne1[i])
if(!v[e1[i]]) return 0;
return 1;
}
inline bool bfs2(int cur)
{
queue<int>q;
q.push(cur);
while(!q.empty())
{
int x=q.front();
q.pop();
if(!check(x)) continue;
for(int i=h1[x];~i;i=ne1[i])//遍历每一个点
{
int y=e1[i];
if(d[y]==-1)
{
d[y]=d[x]+1;
q.push(y);
if(y==t)
{
printf("%d\n",d[t]+1);
return 1;
}
}
}
}
return 0;
}
int main()
{
cin>>n>>m;
memset(h1,-1,sizeof h1);
memset(h2,-1,sizeof h2);
for(int i=1;i<=m;i++)
{
int a,b;
scanf("%d%d",&a,&b);
add(a,b);//建图
}
cin>>s>>t;
bfs1(t);//求出终点能到的点
memset(d,-1,sizeof d);
if(!bfs2(s)) printf("-1\n");
return 0;
}
懂了懂了,感谢大佬