- 寻找道路
- 2015-10-23 21:11:58 @
var k,i,j,m,n,op,ed:longint;
mb:array[1..200000,1..2] of integer;
a:array[1..10000,1..10000]of 0..1 ;
v,co:array[1..10000] of boolean;
s:array[1..10000] of longint;
procedure back(i:longint);
begin
co[i]:=true;
for j:=1 to n do
if (not co[j]) and (a[j,i]=1) then back(j);
end;
procedure go;
var min:longint;
begin
min:=maxlongint;
for j:=1 to n do
if co[j] and (not v[j]) and (a[k,j]=1) then
if s[j]<min then begin min:=s[j];k:=j;end;
v[k]:=true;
for j:=1 to n do
if co[j] and (not v[j]) and (a[k,j]=1) then
if s[k]+1<s[j] then s[j]:=s[k]+1;
end;
begin
read(n,m);
for i:=1 to n do s[i]:=maxlongint;
fillchar(co,sizeof(co),0);
fillchar(v,sizeof(v),0);
for i:=1 to m do
begin
readln(mb[i,1],mb[i,2]);
a[mb[i,1],mb[i,2]]:=1;
end;
read(op,ed);
back(ed);
for i:=1 to m do
if not co[mb[i,2]] then v[mb[i,1]]:=true;
if v[op] then write('-1')
else if not co[op] then write('-1');
begin for i:=1 to n-2 do go;write(s[ed]);end;
end.
求指教,每次dfs结果都不对
2 条评论
-
天津风 LV 4 @ 2015-10-23 21:43:29
在检查完之后,修改了一下
var k,i,j,m,n,op,ed:longint;
mb:array[1..200000,1..2] of longint;
a:array[1..10000,1..10000]of 0..1 ;
v,co:array[1..10000] of boolean;
s:array[1..10000] of longint;procedure back(i:longint);
var j:longint;
begin
co[i]:=true;
for j:=1 to n do
if (not co[j]) and (a[j,i]=1) then back(j);
end;procedure go;
var min:longint;
begin
min:=maxlongint;
for j:=1 to n do
if co[j] and (not v[j]) and (a[k,j]=1) then
if s[j]<min then begin min:=s[j];k:=j;end;
v[k]:=true;
for j:=1 to n do
if co[j] and (not v[j]) and (a[k,j]=1) then
if s[k]+1<s[j] then s[j]:=s[k]+1;
end;begin
read(n,m);
for i:=1 to n do s[i]:=maxlongint;
fillchar(co,sizeof(co),0);
fillchar(v,sizeof(v),0);
for i:=1 to m do
begin
readln(mb[i,1],mb[i,2]);
a[mb[i,1],mb[i,2]]:=1;
end;
read(op,ed);
back(ed);
for i:=1 to m do
if not co[mb[i,2]] then v[mb[i,1]]:=true;
if v[op] then write('-1')
else if not co[op] then write('-1');
begin
k:=op;
v[k]:=true;
for i:=1 to n do if (a[k,i]=1) and co[i] then s[i]:=1;
for i:=1 to n-2 do go;write(s[ed]);end;
end.只过了三组啊TAT
-
2015-10-23 21:23:40@
发现是调用变量的问题,不过为什么会201,orz
- 1