记录编号 334187 评测结果 AAAAAAAAAA
题目名称 [NOIP 2014]寻找道路 最终得分 100
用户昵称 Gravatar转瞬の电流 是否通过 通过
代码语言 Pascal 运行时间 0.215 s
提交时间 2016-10-31 19:41:12 内存使用 4.13 MiB
显示代码纯文本
program xzdl;
var
i,j,k,m,n,s,u,v,be,en:longint;
t,w,d:array[-2..10001]of longint;
pp,pa,pb:array[0..10001]of boolean;
b,c2,e,c,dui:array[0..200200]of longint;

procedure jia(x,y:longint);
begin
if t[x]=-1 then begin c[y]:=-1;t[x]:=y;end
 else
 begin
 c[y]:=t[x];
 t[x]:=y;
 end;
end;

procedure jia1(x,y:longint);
begin
if w[x]=-1 then begin c2[y]:=-1; w[x]:=y; end
 else
 begin
 c2[y]:=w[x];
 w[x]:=y;
 end;
end;
procedure tui(x:longint);
var
o:longint;
begin
o:=w[x];
while o<>-1 do
 begin
 if pp[b[o]]=false then
  begin
  pp[b[o]]:=true;
  tui(b[o]);
  end;
 o:=c2[o];
 end;
end;

procedure shan(x:longint);
var
o:longint;
begin
o:=w[x];
while o<>-1 do
 begin
 pb[b[o]]:=true;
 o:=c2[o];
 end;
end;

procedure zd(x:integer);
var
o,p:longint;
begin
o:=t[x];
while o<>-1 do
 begin
 {writeln('>>',e[o],'<',x);}
 if pp[e[o]]=true then
 begin
 {writeln('>',e[o],'<',x,' ',d[e[o]],'<>',d[x]);}
 if d[e[o]]>d[x]+1 then
  begin
  d[e[o]]:=d[x]+1;
  if pa[e[o]]=false then
   begin
   inc(k);
   if k>200200 then k:=k-200200;
   dui[k]:=e[o];
   if d[dui[k]]<d[dui[j+1]] then
    begin
    p:=dui[k];
    dui[k]:=dui[j+1];
    dui[j+1]:=p;
    end;
   pa[e[o]]:=true;
   end;
  end;
 end;
 o:=c[o];
 end;
pa[x]:=false;
end;


procedure spfa(x:integer);
var
o:longint;
begin
for o:=1 to 200200 do
 dui[o]:=-1;
d[-1]:=-1;
for o:=1 to n do
 begin
 pa[o]:=false;
 d[o]:=maxint;
 end;
d[x]:=0;
pa[x]:=true;
dui[1]:=x;
k:=1;
j:=1;
 while dui[j]<>-1 do
  begin
  zd(dui[j]);
  inc(j);
  if j>200200 then j:=j-200200;
  end;
end;

begin
assign(input,'roadb.in');
assign(output,'roadb.out');
reset(input);
rewrite(output);
readln(n,m);
for i:=1 to n do
 begin
 t[i]:=-1;
 w[i]:=-1;
 pp[i]:=false;
 pb[i]:=false;
 end;
for i:=1 to m do
 begin
 readln(u,e[i]);
 jia(u,i);
 b[i]:=u;
 jia1(e[i],i);
 end;
readln(be,en);
pp[en]:=true;
tui(en);
{for i:=1 to n do
writeln(pp[i]);}
for i:=1 to n do
 if pp[i]=false then shan(i);
for i:=1 to n do
 if pb[i]=true then pp[i]:=false;
if pp[be]=false then writeln(-1)
else
 begin
 spfa(be);
 {for i:=1 to n do
 writeln(d[i]);}
 if d[en]=maxint then writeln(-1)
  else writeln(d[en]);
 end;
{for i:=1 to n do
writeln(i,' ',pp[i]);
for i:=1 to n do
writeln(t[i]);}
close(input);
close(output);
end.