【洛谷 2296】寻找道路

问题描述

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

1 ．路径上的所有点的出边所指向的点都直接或间接与终点连通。

2 ．在满足条件1 的情况下使路径最短。

注意：图G 中可能存在重边和自环，题目保证终点没有出边。

请你输出符合条件的路径的长度。

输入

第一行有两个用一个空格隔开的整数n 和m ，表示图有n 个点和m 条边。

接下来的m 行每行2 个整数x 、y ，之间用一个空格隔开，表示有一条边从点x 指向点y 。

最后一行有两个用一个空格隔开的整数s 、t ，表示起点为s ，终点为t 。

输出

输出只有一行，包含一个整数，表示满足题目᧿述的最短路径的长度。如果这样的路径不存在，输出- 1 。

样例输入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

样例输出1

-1

样例输出2

算法讨论

这道题乍一看就是道裸SPFA，实则不然，他有路径上的所有点的出边所指向的点都直接或间接与终点连通这一条件，所以我们需要进行一个预处理：先从终点开始，将所有直接或间接连接的点打上标记，再做SPFA。做的时候如果当前点的所有连边上有不能到达终点的点，则此点不能更新。

constmaxn=10000;maxm=200000;
varx,y,x1,y1,next,next1:array[1..maxm] of longint;d,v,ls,ls1,list:array[1..maxn] of longint;f:array[1..maxn] of boolean;i,j,n,m,s,t,p:longint;procedure search(xx:longint);
vari:longint;
begini:=ls1[xx];f[xx]:=true;while i>0 dobeginif f[y1[i]]=falsethen search(y1[i]);i:=next1[i]end;
end;function check(xx:longint):boolean;
vari:longint;
begini:=ls[xx];if f[xx]=falsethen exit(false);while i>0 dobeginif f[y[i]]=falsethen exit(false);i:=next[i]end;exit(true)
end;procedure spfa;
vari,hd,tl,t:longint;
beginhd:=0; tl:=1;list[1]:=s;v[s]:=1;for i:=1 to n dod[i]:=maxlongint;d[s]:=0;while hd<>tl dobegininc(hd);t:=ls[list[hd]];while t>0 dobeginif (d[x[t]]+1and (check(y[t]))then begind[y[t]]:=d[x[t]]+1;if v[y[t]]=0then begininc(tl);v[y[t]]:=1;list[tl]:=y[t]end;end;t:=next[t]end;v[list[hd]]:=0end;
end;beginread(n,m);for i:=1 to m dobeginread(x[i],y[i]);next[i]:=ls[x[i]];ls[x[i]]:=i;x1[i]:=y[i]; y1[i]:=x[i];next1[i]:=ls1[x1[i]];ls1[x1[i]]:=iend;read(s,t);search(t);spfa;if d[t]<>maxlongintthen write(d[t])else write(-1)
end.

Pixiv ID：