【问题描述】

在有向图 G 中，每条边的长度均为 1，现给定起点和终点，请你在图中找一条从起点到 终点的路径，该路径满足以下条件：

1. 路径上的所有点的出边所指向的点都直接或间接与终点连通。
2. 在满足条件 1 的情况下使路径最短。

注意：图 G 中可能存在重边和自环，题目保证终点没有出边。 请你输出符合条件的路径的长度。

【样例输入1】

    3 2

    1 2

    2 1

    1 3

【样例输出1】

    -1

【样例输入2】

    6 6

    1 2

    1 3

    2 6

    2 5

    4 5

    3 4

    1 5

【样例输出2】

    3

【解题思路】

     又是要用邻接表的题，我又华丽丽地用了邻接矩阵，加上当初SB一般的用广搜+深搜去搜能到的顶点，用了两个布尔型数组，求最短路的时候用了floyed（其实这个都没什么了，之前的就足够MLE了……），再次爆零……

    OK，吐槽完之后，继续来说正解。

    邻接表，不多说了，以后看到需要存储边的题目都去用邻接表！管你有没有权。由于这题需要判断能否到达终点，于是我们需要反向存储。一遍DFS找到所有不能直接或间接到达的点，将它们的所有的入边的点全部删掉，如果起点无法到达的话，就输出-1，否则就是求最短路了。

【代码实现】

1 type rec=record 2      c,next:longint; 3 end; 4 var e:array[1..200000] of rec; 5     g:array[1..10000] of longint; 6     efree,i,n,m,k,x,y,s,t,j:longint; 7     a:array[1..10000] of longint; 8     f,flag:array[1..10000] of boolean; 9 procedure add;10 begin11  e[efree].c:=x;12  e[efree].next:=g[y];13  g[y]:=efree;14  inc(efree);15 end;16 procedure dfs(x:longint);17 var j:longint;18 begin19  f[x]:=true;20  j:=g[x];21  while j<>0 do22   begin23    if not f[e[j].c] then24     dfs(e[j].c);25    j:=e[j].next;26   end;27 end;28 procedure dijkstra;29 var i,j,min,pos:longint;30 begin31  fillchar(f,sizeof(f),false);32  f[t]:=true;33  a[t]:=0;34  for j:=1 to n do35   begin36    pos:=t;37    min:=maxint;38    for i:=1 to n do39     if (not f[i])and(a[i]
     
      0 do47     begin48      if flag[e[i].c] then49       if a[e[i].c]>a[pos]+1 then50        a[e[i].c]:=a[pos]+1;51      i:=e[i].next;52     end;53   end;54 end;55 begin56  readln(n,m);57  efree:=1;58  for i:=1 to m do59   begin60    readln(x,y);61    add;62   end;63  readln(s,t);64  dfs(t);65  flag:=f;66  for i:=1 to n do67   if not f[i] then68    begin69     j:=g[i];70     while j<>0 do71      begin72       flag[e[j].c]:=false;73       j:=e[j].next;74      end;75    end;76  if not flag[s] then77   begin78    writeln(-1);79    halt;80   end;81  for i:=1 to n do82   a[i]:=maxint;83  dijkstra;84  writeln(a[s]);85 end.