链接
描述
在有向图 G中，每条边的长度均为 1，现给定起点和终点，请你在图中找一条从起点到终点的路径，该路径满足以下条件：
路径上的所有点的出边所指向的点都直接或间接与终点连通。 在满足条件 1 的情况下使路径最短。 注意：图 G 中可能存在重边和自环，题目保证终点没有出边。
请你输出符合条件的路径的长度。
输入格式 第一行有两个用一个空格隔开的整数 n 和 m，表示图有 n 个点和 m 条边。
接下来的 m 行每行 2 个整数 x,y，之间用一个空格隔开，表示有一条边从点 x 指向点y。
最后一行有两个用一个空格隔开的整数 s,t，表示起点为 s，终点为 t。
输出格式 输出只有一行，包含一个整数，表示满足题目描述的最短路径的长度。如果这样的路径不存在，输出−1。
样例一 input
3 2 1 2 2 1 1 3
output
-1
explanation
起点1与终点3不连通，所以满足题目描述的路径不存在，故输出−1−1。
样例二 input
6 6 1 2 1 3 2 6 2 5 4 5 3 4 1 5
output
3
explanation
注意点2不能在答案路径中，因为点2连了一条边到点6，而点6不与终点5连通。
限制与约定 对于30%的数据，0<n≤100<n≤10，0<m≤200<*m≤20;
对于60%的数据，0<n≤1000<n≤100，0<m≤20000<m≤2000;
对于100%的数据，0<n≤100000<n≤10000，0<m≤2000000<m≤200000，0<x,y,s,t≤n0<*x,y,s,t≤n，x,s≠tx,s≠t。
时间限制：1s 内存限制：128MB
NOIP 2014 DAY 2 T2 这是个无权图，我们可以用bfs求出最短路径，关键是条件一我们该怎么处理。不难想到，我们应该反向建图，从终点开始跑，记录一下可以到的点。路径上所有的点都应该与终点相连，所以只要找到一个点不符合条件，就判断下一个点。如果这个到终点的距离没有被更新，就说明不存在这样的路径，就输出-1。 注意建边的顺序，这里弄了好久…再次建边的时候不要忘记初始化。不要忘记终点也与终点相连。我是用了一个函数，建了两次边。当然也可以用两个建图函数。两种first,next,还有edge结构体之类需要建图的东西，在输入的时候一起建图。我从终点跑的时候是用的dfs，当然也可以用bfs，各种姿势都可以过啦。
代码如下：
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int MAX_V=10000+10; const int MAX_E=200000+10; int first[MAX_V],nxt[MAX_E<<1],d[MAX_V]; int f[MAX_E],t[MAX_E]; struct edge{ int from,to; }es[MAX_E<<1]; int tot; bool used[MAX_V],vis[MAX_V]; void init() { memset(first,-1,sizeof(first)); tot=0; } void build(int ff,int tt) { es[++tot]=(edge){ff,tt}; nxt[tot]=first[ff]; first[ff]=tot; } bool canto[MAX_V]; void dfs(int s) { //cout<<s<<endl; vis[s]=1; for(int i=first[s];i!=-1;i=nxt[i]) { int v=es[i].to; canto[v]=1; if(!vis[v]) dfs(v); } } bool judgeson(int s) { for(int i=first[s];i!=-1;i=nxt[i]) { int v=es[i].to; if(!canto[v]) return false; } return true; } queue<int>q; void bfs(int s) { d[s]=0; used[s]=1; q.push(s); while(!q.empty()) { int u=q.front(); q.pop(); used[u]=0; if(!judgeson(u)) continue; for(int i=first[u];i!=-1;i=nxt[i]) { int v=es[i].to; if(d[v]==-1) { d[v]=d[u]+1; if(!used[v]) { used[v]=1; q.push(v); } } } } } int main() { int n,m; int S,E; scanf("%d%d",&n,&m); init(); memset(d,-1,sizeof(d)); for(int i=1;i<=m;i++) scanf("%d%d",&f[i],&t[i]); scanf("%d%d",&S,&E); for(int i=1;i<=m;i++) build(t[i],f[i]); dfs(E); canto[E]=1; init(); for(int i=1;i<=m;i++) build(f[i],t[i]); bfs(S); printf("%d\n",d[E]); return 0; } /* 6 6 1 2 1 3 2 6 2 5 4 5 3 4 1 5 */