在有向图G 中，每条边的长度均为1 ，现给定起点和终点，请你在图中找一条从起点到终点的路径，该路径满足以下条件：
1 ．路径上的所有点的出边所指向的点都直接或间接与终点连通。
2 ．在满足条件1 的情况下使路径最短。
注意：图G 中可能存在重边和自环，题目保证终点没有出边。
请你输出符合条件的路径的长度。
输入文件名为road .in。
第一行有两个用一个空格隔开的整数n 和m ，表示图有n 个点和m 条边。
接下来的m 行每行2 个整数x 、y ，之间用一个空格隔开，表示有一条边从点x 指向点y 。
最后一行有两个用一个空格隔开的整数s 、t ，表示起点为s ，终点为t 。
输出格式：
输出文件名为road .out 。
输出只有一行，包含一个整数，表示满足题目᧿述的最短路径的长度。如果这样的路径不存在，输出- 1 。
解释1：
如上图所示，箭头表示有向道路，圆点表示城市。起点1 与终点3 不连通，所以满足题
目᧿述的路径不存在，故输出- 1 。
解释2：
如上图所示，满足条件的路径为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。
分析：先从终点反向搜索一次，能从终点到达的点标记，做最短路的时候直接判断当前点的所有出度是否符合条件。
代码
const maxn=2000000; var x,y,x1,y1,ls,se,next,ls1,next1,d:array[0..maxn] of longint; f,fl,v:array[0..maxn] of boolean; i,j,n,m,s,t1:longint; procedure find(x:longint); var i:longint; begin i:=ls1[x]; f[x]:=true; fl[x]:=true; while i>0 do begin if not fl[y1[i]] then find(y1[i]); i:=next1[i]; end; end; function check(x:longint):boolean; var i:longint; begin i:=ls[x]; if not f[x] then exit(false); while i>0 do begin if not f[y[i]] then exit(false); i:=next[i]; end; exit(true); end; procedure spfa; var head,tail,t:longint; begin for i:=0 to n do d[i]:=maxlongint div 2; head:=0; tail:=1; v[s]:=true; se[1]:=s; d[s]:=0; while head<tail do begin inc(head); t:=ls[se[head]]; while t>0 do begin if (d[x[t]]+1<d[y[t]]) and (check(y[t])) then begin d[y[t]]:=d[x[t]]+1; if not v[y[t]] then begin v[y[t]]:=true; inc(tail); se[tail]:=y[t]; end; end; t:=next[t]; end; v[se[head]]:=false; end; end; procedure init(p,q,t:longint); begin x[t]:=p; y[t]:=q; x1[t]:=q; y1[t]:=p; next[t]:=ls[p]; ls[p]:=t; next1[t]:=ls1[q]; ls1[q]:=t; end; begin readln(n,m); for i:=1 to m do begin readln(s,t1); init(s,t1,i); end; readln(s,t1); f[t1]:=true; find(t1); spfa; if d[t1]=d[0] then writeln(-1) else writeln(d[t1]); end.
