AOJ 1032 : Course Planning for Lazy Students

問題リンク：Course Planning for Lazy Students | Aizu Online Judge

問題概要：
n個の科目から最低取得単位数Uをこえる最小の科目数をもとめよ

使用した言語：C++

解説：
dfsだとTLEになったのでbitをもたせてbfsをした
mincost[1<

#include<cstdio>
#include<iostream>
#include<bitset>
#include<deque>
#include<algorithm>
using namespace std;
 
struct Pox
{
  int state,cost;
  Pox(int state,int cost):state(state),cost(cost){}
};
 
int main()
{
  while(1)
    {
      int n,U,k,r;
      scanf("%d %d",&n,&U);
      if(n+U == 0)
    break;
      int mincost[1<<n];
      for(int i=0;i<(1<<n);i++)
    mincost[i] = (1<<n);
      deque<Pox> deq;
      int G[n];
      int c[n];
      for(int i = 0;i<n;i++)
    {
      scanf("%d %d",&c[i],&k);
        G[i] = 0;
 
      for(int j=0;j<k;j++)
        {
          scanf("%d",&r);
          G[i] |= (1<<r);
        }
    }
 
      deq.push_back(Pox(0,0));
      mincost[0] = 0;     
      int ans = (1<<n);
      while(!deq.empty())
    {
      Pox pox = deq.front(); deq.pop_front();
      int num = __builtin_popcount(pox.state);
      if(num >= ans)
        continue;
    
      if(pox.cost >= U)
        {
          ans = min(ans,num);
          continue;
        }    
 
      for(int i=0;i<n;i++)
        {
          if((pox.state >> i) & 1)
        continue;
          int pre = G[i];
          pre &= pox.state;
          if(pre != G[i])//先修科目をすべてとっているか？
        continue;
          if(mincost[pox.state|(1<<i)] <= num+1)
        continue;
          mincost[pox.state|(1<<i)] = num+1;
          if(pox.cost + c[i] < U)
        deq.push_back(Pox(pox.state|(1<<i),pox.cost+c[i]));
          else
        ans = min(ans,num+1);
        }
    }
      cout << ans << endl;
    }
  return 0;
}