[NOIP2014提高组]寻找道路

题目：洛谷P2296、Vijos P1909、codevs3731、UOJ#19。

题目大意：给你一张有向图，边权为1，让你找一条s到t的最短路径，但这条路径上所有点的出边所指向的点都与终点连通。如果没有这样的路径，输出-1。

解题思路：由于有限制条件，我们可以建反向图，从t开始跑一遍dfs，找出所有不能到达t的点。然后bfs求无权图最短路。对于每一个点，先判断其是否连通着不与终点连通的点，如果有则跳过该点。最后判断从s到t的最短路是否为inf即可。

C++ Code：

#include<cstdio>
#include<cctype>
#include<cstring>
#include<queue>
using namespace std;
struct edge{
int from,to,nxt;
}e[2][200005];
int head[2][200005],cnt,n,m,s,t;
bool b[10005],vis[10005];
int dis[10005];
queue<int>q;
template <typename T>inline void read(T& x){
x=0;
char c=getchar();
for(;!isdigit(c);c=getchar());
for(;isdigit(c);c=getchar())x=(x<<3)+(x<<1)+(c^'0');
}
inline void addedge(int x,int y){
e[0][++cnt]=(edge){x,y,head[0][x]};
e[1][cnt]=(edge){y,x,head[1][y]};
head[0][x]=head[1][y]=cnt;
}
void dfs(int now){
b[now]=true;
for(int i=head[1][now];i;i=e[1][i].nxt){
if(!b[e[1][i].to])dfs(e[1][i].to);
}
}
void bfs(int s){
memset(vis,0,sizeof vis);
memset(dis,0x3f,sizeof dis);
vis[s]=true;
dis[s]=0;
q.push(s);
while(!q.empty()){
int u=q.front();
q.pop();
if(!b[u])continue;
bool flag=true;
for(int i=head[0][u];i;i=e[0][i].nxt)
if(!b[e[0][i].to]){
flag=false;
break;
}
if(flag)
for(int i=head[0][u];i;i=e[0][i].nxt){
int v=e[0][i].to;
if(!vis[v]){
vis[v]=true;
dis[v]=dis[u]+1;
q.push(v);
}
}
}
}
int main(){
cnt=0;
read(n);
for(read(m);m--;){
int x,y;
read(x),read(y);
addedge(x,y);
}
read(s),read(t);
memset(b,0,sizeof b);
dfs(t);
bfs(s);
printf("%d\n",(dis[t]<0x3f3f3f3f)?(dis[t]):(-1));
return 0;
}