LEM2 - GUMBI
Tác giả: skyvn97
Ngôn ngữ: C++
#include<cstdio>
#include<cstring>
#include<queue>
#define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
#define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
#define MASK(i) (1<<(i))
using namespace std;
int dis[MASK(20)+7];
int stt[22];
int n,goal,sta;
int nextInt(void) {
int x;
scanf("%d",&x);
return (x);
}
void init(void) {
n=nextInt();
goal=MASK(nextInt()-1);
REP(i,n) REP(zz,nextInt()) stt[i]|=MASK(nextInt()-1);
REP(i,n) if (nextInt()==1) sta|=MASK(i);
}
void bfs(void) {
memset(dis,-1,sizeof dis);
queue<int> q;
dis[sta]=0;
q.push(sta);
while (!q.empty()) {
int u=q.front();q.pop();
if (u==goal) {
printf("%d\n",dis[u]);
return;
}
REP(i,n) {
int v=(u|MASK(i))&~stt[i];
if (dis[v]<0) {
dis[v]=dis[u]+1;
q.push(v);
}
}
}
printf("-1\n");
}
int main(void) {
init();
bfs();
return 0;
}