LEM2 - GUMBI

Tác giả: ll931110

Ngôn ngữ: Pascal

{$MODE DELPHI}
Program LEM2;
Const
  input  = '';
  output = '';
  maxn = 20;
  maxd = 2200000;
Var
  n,k: integer;
  start,finish: integer;
  d,queue: array[0..maxd] of integer;
  s: array[1..maxn] of integer;

Procedure init;
Var
  f: text;
  a,i,j,t: integer;
Begin
  Assign(f, input);
    Reset(f);

  Readln(f, n, k);
  For i:= 1 to n do
    Begin
     Read(f, a);
     s[i]:= 0;
     For j:= 1 to a do
       Begin
         Read(f, t);
         s[i]:= s[i] + 1 shl (t - 1);
       End;
    End;

  finish:= 1 shl (k - 1);
  start:= 0;
  For i:= 1 to n do
    Begin
      Read(f, t);
      If t = 1 then start:= start + 1 shl (i - 1);
    End;

  Close(f);
End;

Procedure BFS;
Var
  front,rear: integer;
  u,v,i: integer;
Begin
  If start = finish then
    Begin
      d[start]:= 0;
      exit;
    End;

  Fillchar(d, sizeof(d), 0);
  d[start]:= 0;

  front:= 1;
  rear:= 1;
  queue[1]:= start;

  Repeat
    u:= queue[front];
    inc(front);

    For i:= 1 to n do
      Begin
        v:= (u or (1 shl (i - 1))) and (not s[i]);
        If (d[v] = 0) and (v <> start) then
          Begin
            d[v]:= d[u] + 1;
            If v = finish then exit;
            inc(rear);
            queue[rear]:= v;
          End;
      End;
  Until front > rear;
End;

Procedure printresult;
Var
  f: text;
Begin
  Assign(f, output);
    Rewrite(f);
    If (d[finish] = 0) and (finish <> start)
      then writeln(f, -1) else writeln(f, d[finish]);
  Close(f);
End;

Begin
  init;
  BFS;
  printresult;
End.

Download