LEM2 - GUMBI

Tác giả: ladpro98

Ngôn ngữ: Pascal

program lem2;
uses    math;
const   maxn=20;
        fi='';
var     press,t:array[1..maxn] of longint;
        d,q:array[0..1 shl maxn] of longint;
        check:array[0..1 shl maxn] of boolean;
        start,n,target,k:longint;

procedure input;
var     inp:text;
        i,s,j,p:longint;
begin
        assign(inp,fi);reset(inp);
        readln(inp,n,k);
        target:=1 shl (k-1);
        for i:=1 to n do
        begin
                read(inp,s);
                press[i]:=1 shl n-1;
                for j:=1 to s do
                begin
                        read(inp,p);
                        dec(press[i],1 shl (p-1));
                end;
                readln(inp);
        end;
        for i:=1 to n do read(inp,t[i]);
        for i:=n downto 1 do start:=2*start+t[i];
        close(inp);
end;

function getbit(i,j:longint):longint;
begin
        exit(i shr (j-1) and 1);
end;

procedure bfs;
var     l,r,u,v,i:longint;
begin
        l:=1;r:=1;
        q[1]:=start;
        check[start]:=true;
        d[start]:=0;
        while l<=r do
        begin
                u:=q[l];inc(l);
                for i:=1 to n do
                begin
                        v:=u and press[i];
                        if getbit(v,i)=0 then
                        v:=v+1 shl (i-1);

                        if not check[v] then
                        begin
                                check[v]:=true;
                                inc(r);
                                q[r]:=v;
                                d[v]:=d[u]+1;
                                if v=target then
                                begin
                                        write(d[v]);
                                        halt;
                                end;
                        end;
                end;
        end;
end;

begin
        input;
        bfs;
        write(-1);
end.

Download