题解 | 寻找道路-NOIP2014提高组复赛B题
寻找道路
https://ac.nowcoder.com/acm/contest/262/B
题目描述
在有向图G中，每条边的长度均为1，现给定起点和终点，请你在图中找一条从起点到终点的路径，该路径满足以下条件：
1．路径上的所有点的出边所指向的点都直接或间接与终点连通。
2．在满足条件1的情况下使路径最短。
注意：图G中可能存在重边和自环，题目保证终点没有出边。
请你输出符合条件的路径的长度。输入描述:
第一行有两个用一个空格隔开的整数n和m，表示图有n个点和m条边。
接下来的m行每行2个整数x、y，之间用一个空格隔开，表示有一条边从点x指向点y。
最后一行有两个用一个空格隔开的整数s、t，表示起点为s，终点为t。
输出描述:
输出只有一行，包含一个整数，表示满足题目描述的最短路径的长度。如果这样的路径不存在，输出-1。
示例1
输入
3 2
1 2
2 1
1 3
输出
-1
说明
如上图所示，箭头表示有向道路，圆点表示城市。起点1与终点3不连通，所以满足题目描述的路径不存在，故输出-1。
示例2
输入
6 6
1 2
1 3
2 6
2 5
4 5
3 4
1 5
输出
3
说明
如上图所示，满足条件的路径为1->3->4->5。注意点2不能在答案路径中，因为点2连了一条边到点6，而点6不与终点5连通。
备注
对于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。
解答
首先，预处理，把每条边反向。
从终点开始bfs，标记从终点开始可以走到的点。
第二步，枚举每一个点，如果这个点没有被标记，则枚举它的每一条出边（反向后的），如果它指向的点被标记，则说明这个被标记的点不合法，删除。
第三步，在合法点上bfs，单源最短路。找到答案。详见代码：
#include<bits/stdc++.h>
using namespace std;
int read()
{
int x=0,y=1;char c=getchar();
while(c>'9'||c<'0'){if(c=='0')y=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return x*y;
}
int n,m;
vector<int>v[10005];
bool cando[10005],er[10005];
queue<int>q;
int st,ed;
int ans[10005];
int main()
{
n=read(),m=read();
for(int i=1;i<=m;i++)
{
int a=read(),b=read();
if(a==b)continue;//去除自环
v[b].push_back(a);
}
st=read(),ed=read();
cando[ed]=1;//第一遍bfs
q.push(ed);
while(!q.empty())
{
int no=q.front();
q.pop();
for(int i=0,j=v[no].size();i<j;i++)
if(!cando[v[no][i]]){cando[v[no][i]]=1;q.push(v[no][i]);}//标记从终点可以到达的点
}
memcpy(er,cando,sizeof(cando));//准备第二次标记
//注意这里最好有第二个数组标记，在一个数组里删点有后效型，如果一个点开始被标记，它通过一个序号比它小的点删除了，
//那么访问到它的时候，就会被当成开始就没被标记的点，会通过它把合法点删除。
//这样做完之后，合法点都被标记了。
for(int i=1;i<=n;i++)
if(!cando[i])
for(int j=0,k=v[i].size();j<k;j++)
if(er[v[i][j]])
er[v[i][j]]=0;
//最后一遍bfs找答案。
q.push(ed);
while(!q.empty())
{
int no=q.front();
q.pop();
for(int i=0,j=v[no].size();i<j;i++)
if(er[v[no][i]])
{
q.push(v[no][i]);
er[v[no][i]]=0;
ans[v[no][i]]=ans[no]+1;
}
}
//题目要求输出。
if(ans[st]==0)printf("-1");
else printf("%d",ans[st]);
return 0;
} 来源：_空_
