POJ 1932 XYZZY

問題

N部屋個の部屋があり、それらはいくつかの一方通行の通路で結ばれている。
各部屋にはそれぞれのエネルギーがあり、部屋に入る度に、自分の持っているエネルギーに部屋のエネルギーが足される。
部屋のエネルギーが負であることもある。

自分は最初100のエネルギーを持っており、そのエネルギーが0以下になると死んでしまう。
1番の部屋からN番の部屋へ到達できるかを判定せよ。

制約条件

N≦100
部屋のエネルギーの絶対値≦100

方針

ゴールの部屋からグラフを逆にたどり、「ゴールへ到達可能な頂点」を列挙しておく。
それ以外の頂点は捨ててよい。

グラフを頂点0から深さ優先探索していき、エネルギーが尽きずにゴールに行けるかを見る。
エネルギーを増加させるような閉路を途中で見つけた場合も、（そこでエネルギーを無限に増やせるので）ゴールへ到達可能である。

ソースコード

int n, v[100], cost[100];
vector<vi> g,rg;
bool rv[100];

void rdfs(int c){
	rv[c]=1;
	fr(i,rg[c])if(!rv[*i])rdfs(*i);
}
bool dfs(int c,int cc){
	cc+=v[c];
	if(cc<=0)return 0;
	if(c==n-1)return 1;
	if(cost[c]>=0){
		if(cc>cost[c])return 1;
		return 0;
	}
	cost[c]=cc;
	
	fr(i,g[c])if(rv[*i]&&dfs(*i,cc))return 1;
	return 0;
}
int main()
{
	while(scanf("%d",&n),~n){
		g.clear();g.resize(n);
		rg.clear(); rg.resize(n);
		
		rep(i,n){
			scanf("%d",v+i);
			int m; scanf("%d",&m);
			rep(j,m){
				int t; scanf("%d",&t); t--;
				g[i].pb(t); rg[t].pb(i);
			}
		}
		
		rep(i,n)cost[i]=-inf, rv[i]=0;
		rdfs(n-1);
		
		puts(rv[0]&&dfs(0,100)?"winnable":"hopeless");
	}
	return 0;
}