【最短路】P2296 寻找道路

 

题目要求路径上的点都能直接或者间接的经过ed，所以我们建反图，搜索一次能经过的点，然后去计算一下能经过的点

然后再原图上跑一下最短路即可

 

注意：计算能经过的点的时候要用原图啊！！调了好久

 

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+5;
const int maxm=2e5+5;
int n,m,st,tot,ed,dis[maxn],flag[maxn],able[maxn],head[maxn],h[maxn],cnt;
struct edge
{
	int to,nxt;
}e[maxm],G[maxm];
void add(int x,int y)
{
	e[++cnt].to=y;
	e[cnt].nxt=head[x];
	head[x]=cnt;
}
void adde(int x,int y)
{
	G[++tot].to=y;
	G[tot].nxt=h[x];
	h[x]=cnt;
}
void bfs()
{
	queue <int> s;
	s.push(ed); flag[ed]=1;
	while(!s.empty())
	{
		int u=s.front();
		s.pop();
		for(int i=h[u];i;i=G[i].nxt)
		{
			int to=G[i].to;
			if(!flag[to])
			{
				s.push(to);
				flag[to]=1;
			}
		}
	}
}
void judge()
{
	int fl;
	for(int i=1;i<=n;i++)
	{
		fl=0;
		if(!flag[i]) continue;
		for(int j=head[i];j;j=e[j].nxt)
		{
			int to=e[j].to;
			if(!flag[to])
			{
				fl=1;
				break;
			}
		}	
		if(fl) continue;
		able[i]=1;
	}	
}
void bfs1()
{
	queue <int> q;
	q.push(st); dis[st]=1;
	while(!q.empty())
	{
		int u=q.front();
		q.pop(); 
		if(u==ed)
		{
			printf("%d",dis[u]-1);
			return;
		}
		for(int i=head[u];i;i=e[i].nxt)
		{
			int to=e[i].to;
			if(!dis[to] && able[to])
			{
				dis[to]=dis[u]+1;
				q.push(to);
			}
		}
	}
}
int main()
{
	freopen("P2296_2.in","r",stdin);
	freopen("a.out","w",stdout);
	scanf("%d%d",&n,&m);
	int x,y;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		add(x,y); adde(y,x);
	}
	scanf("%d%d",&st,&ed);
	bfs();
	judge();
	if(!able[st])
	{
		printf("-1");
		return 0;
	}
	bfs1();
	return 0;
}