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;
}

Download