记录编号 |
334187 |
评测结果 |
AAAAAAAAAA |
题目名称 |
[NOIP 2014]寻找道路 |
最终得分 |
100 |
用户昵称 |
转瞬の电流 |
是否通过 |
通过 |
代码语言 |
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.