PKU 1932 XYZZY

http://poj.org/problem?id=1932
ある地点からエネルギー100を持って部屋を移動する。
この部屋はそれぞれにエネルギーがあり、そのエネルギーを足していく。
エネルギーを失うこと無く目的の部屋に辿りつけるかを判定しろというような問題。

幅優先探索。
通るか微妙でしたが、DFSとかで両方向から到達性を判定するコードとかを書くのが、面倒くさかったので適当な回数で探索を打ち切ってます。

int en[100];
int room[100];
vector<int> G[100];

main(){
  int n;
  while(cin>>n,~n){
    rep(i,n)G[i].clear();
    rep(i,n){
      cin>>room[i];
      int v;
      cin>>v;
      rep(j,v){
        int t;
        cin>>t;
        G[i].pb(t-1);
      }
    }
    memset(en,0,sizeof(en));
    queue<PI>q;
    q.push(mp(0,100));
    bool ok=false;
    int loop=0;
    while(!q.empty() && ++loop<1000000){
      int v=q.front().F,c=q.front().S;
      q.pop();
      if(en[v]>=c)continue;
      en[v]=c;
      if(v==n-1){
        ok=true;
        break;
      }
      rep(i,SZ(G[v])){
        int to=G[v][i];
        int nc=c+room[to];
        if(nc<=en[to])continue;
        q.push(mp(to,nc));
      }
    }
    if(ok)cout<<"winnable"<<endl;
    else cout<<"hopeless"<<endl;
  }
}