LEM2 - GUMBI

Tác giả: flashmt

Ngôn ngữ: Pascal

const maxn=1048575;
var n,k,num,s,f:longint;
    p:array[0..20] of longint;
    q,d:array[1..maxn] of longint;
    a:array[1..20] of longint;

procedure rf;
var i,x,j,y:longint;
begin
     read(n,k);
     p[0]:=1;
     for i:=1 to n do p[i]:=p[i-1] shl 1;
     f:=p[k-1];
     for i:=1 to n do
     begin
          read(x);
          for j:=1 to x do
          begin
               read(y);
               a[i]:=a[i] or p[y-1];
          end;
          a[i]:=p[n]-1-a[i];
     end;
     for i:=1 to n do
     begin
          read(x);
          if x=1 then
             s:=s or p[i-1];
     end;
end;

procedure pr;
var i,j,x:longint;
begin
     num:=1; i:=1; d[s]:=1; q[1]:=s;
     repeat
           for j:=1 to n do
           begin
                x:=(q[i] and a[j]) or p[j-1];
                if d[x]=0 then
                begin
                     d[x]:=d[q[i]]+1;
                     if x=f then exit;
                     inc(num);
                     q[num]:=x;
                end;
           end;
           inc(i);
     until (d[f]<>0) or (i>num);
end;

procedure wf;
begin
     if d[f]=0 then writeln(-1)
     else writeln(d[f]-1);
end;

begin
     rf;
     pr;
     wf;
end.

Download