[FZYZOJ 2047] [NOIP2014 D2T2] 寻找道路
[NOIP2014_D2_T2]寻找道路
时间限制：1000MS
内存限制：131072KB
Description
在有向图 G 中，每条边的长度均为 1，现给定起点和终点，请你在图中找一条从起点到终点的路径，该路径满足以下条件：
1.路径上的所有点的出边所指向的点都直接或间接与终点连通。
2.在满足条件 1 的情况下使路径最短。
注意：图 G 中可能存在重边和自环，题目保证终点没有出边。
请你输出符合条件的路径的长度。
Input Format
第一行有两个用一个空格隔开的整数 n 和 m，表示图有 n 个点和 m 条边。
接下来的 m 行每行 2 个整数 x,y，之间用一个空格隔开，表示有一条边从点 x 指向点y。
最后一行有两个用一个空格隔开的整数 s,t，表示起点为 s，终点为 t。
Output Format
输出只有一行，包含一个整数，表示满足题目描述的最短路径的长度。如果这样的路径不存在，输出−1。
Sample Input
#1 3 2 1 2 2 1 1 3 #2 6 6 1 2 1 3 2 6 2 5 4 5 3 4 1 5
Sample Output
#1 -1 #2 3
Hint
注意点2不能在答案路径中，因为点2连了一条边到点6，而点6不与终点5连通。
对于30%的数据，0<n≤10，0<m≤20;
对于60%的数据，0<n≤100，0<m≤2000;
对于100%的数据，0<n≤10000，0<m≤200000，0<x,y,s,t≤n，x,s≠t。
【题解】
先反过来BFS一遍，处理所有不可能到达的点，bool标记为false
然后正着SPFA一遍即可。
1 #include<bits/stdc++.h> 2 using namespace std; 3 int n,m,s,t; 4 struct edge { 5 int to,next; 6 }e[200010],f[200010]; 7 int head[200010],head2[200010],d[200010]; 8 bool can[10010],vis[10010],ok[100010]; 9 char B[1<<15],*S=B,*T=B; 10 #define getc() (S==T&&(T=(S=B)+fread(B,1,1<<15,stdin),S==T)?0:*S++) 11 inline void add(int u,int v,int i) { 12 e[i].to=v; 13 e[i].next=head[u]; 14 head[u]=i; 15 f[i].to=u; 16 f[i].next=head2[v]; 17 head2[v]=i; 18 } 19 inline int read() { 20 int x=0,f=1;char ch; 21 ch=getc(); 22 while(ch>'9'||ch<'0') {if(ch=='-') f=-1; ch=getc();} 23 while(ch<='9'&&ch>='0') {x=(x<<1)+(x<<3)+ch-'0';ch=getc();} 24 return x*f; 25 } 26 int main() { 27 n=read();m=read(); 28 for (int i=1;i<=m;++i) { 29 int u,v; 30 u=read();v=read(); 31 add(u,v,i); 32 } 33 s=read();t=read(); 34 queue<int> q; 35 q.push(t); ok[t]=1; 36 while(!q.empty()) { 37 int top=q.front(); 38 q.pop(); 39 for (int i=head2[top];i;i=f[i].next) { 40 if (!ok[f[i].to]) { 41 ok[f[i].to]=1; 42 q.push(f[i].to); 43 } 44 } 45 } 46 memset(can,1,sizeof(can)); 47 for (int i=1;i<=n;++i) if(!ok[i]) can[i]=0; 48 for (int i=1;i<=m;++i) if(!ok[e[i].to]) can[f[i].to]=0; 49 if(can[s]==0) {printf("-1 ");return 0;} 50 //for (int i=1;i<=n;++i) cout<<can[i]<<' '; 51 memset(d,210000,sizeof(d)); 52 while(!q.empty()) q.pop(); 53 q.push(s); 54 d[s]=0;vis[s]=1; 55 while(!q.empty()) { 56 int top=q.front(); 57 q.pop(); 58 for (int i=head[top];i;i=e[i].next) { 59 if (can[e[i].to]&&d[top]+1<d[e[i].to]) { 60 d[e[i].to]=d[top]+1; 61 if(!vis[e[i].to]) { 62 vis[e[i].to]=1; 63 q.push(e[i].to); 64 } 65 } 66 } 67 } 68 if (d[t]>=210000) printf("-1 "); 69 else printf("%d ",d[t]); 70 return 0; 71 }