题目题解代码

题目

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

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

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

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

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

题解

第一眼看题目——-懵逼1s 然后还是不会 看了一波洛谷题解，好像是： 先从终点出发bfs处理不能到终点的点，把直接和间接通向不与终点相连的点标记 然后spfa跑一遍 时间复杂度O(nm)

嗯，好像很简单 然而并不是这样。打了175行的代码，错了n次，超时n次。发生了什么？

再仔细翻一遍洛谷题解，“并不需要BFS。读题后发现，不能走的点为除终点以外出度为0的点，以及与这些点直接相连的点。那就删了就好了。。。。” 一语点醒梦中人！ 然后不停的删原代码，最后78行过了 发生了什么？

时间复杂度O(nm)

代码

type rec=record x,y,ne:longint; end; var n,m,s,t,i,j,c:longint; d:array[0..10000]of longint; f:array[1..200000]of rec; b,e:array[1..10000]of boolean; ls:array[1..10000]of longint; v,state:array[1..10000]of longint; procedure spfa; var i,j,l,x,y,h,ta:longint; begin fillchar(state,sizeof(state),0); state[1]:=t;v[t]:=1;d[t]:=0;b[t]:=true;b[s]:=true; h:=0;ta:=1; while h<ta do begin inc(h); l:=ls[state[h]]; while l>0 do begin x:=f[l].x;y:=f[l].y; if b[y] and(d[x]+1<d[y])then begin d[y]:=d[x]+1; if v[y]=0 then begin inc(ta); state[ta]:=y; v[y]:=1; end; end; l:=f[l].ne; end; end; end; procedure bfs(k:longint); var l,y:longint; begin l:=ls[k]; while l>0 do begin y:=f[l].y; e[y]:=false; l:=f[l].ne; end; end; begin readln(n,m); j:=m; fillchar(d,sizeof(d),$7f); fillchar(b,sizeof(b),false); for i:=1 to j do begin readln(s,t); inc(c); f[c].x:=t;f[c].y:=s;f[c].ne:=ls[t]; ls[t]:=c; b[s]:=true; end; readln(s,t); b[t]:=true; e:=b; for i:=1 to n do if not b[i] then bfs(i); b:=e; spfa; if d[s]=d[0] then writeln('-1') else writeln(d[s]); end.