我的dfs又错哪了orz

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 条评论

  • @ 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

信息

ID
1909
难度
7
分类
图结构 点击显示
标签
递交数
3977
已通过
885
通过率
22%
被复制
8
上传者