OJ Board

Code: Select all

#include <bits/stdc++.h>
using namespace std;
int n, m, x, dist[111], par[111], enrg[111], vist[111][100 * 100 * 2],
		maxDist[111], id;
bool reach;
char ans[][11] = { "hopeless", "winnable" };
vector<vector<int> > arr;
bool dfs(int x, int des, int health) {
	maxDist[x] = max(maxDist[x], health);
	if (health <= 10000)
		reach = 0;
	if (x == des)
		return 1;
	bool f = 0;
	vist[x][health] = id;
	for (int i = 0, ln = arr[x].size(); i < ln; ++i) {
		int y = arr[x][i];
		if (vist[y][health + enrg[y]] == id)
			continue;
		f |= dfs(y, des, health + enrg[y]);
	}
	return f;
}
int main(int argc, char **argv) {
#ifndef ONLINE_JUDGE
	freopen("a.in", "r", stdin);
#endif
	for (; scanf("%d", &n) > 0 && (n + 1);) {
		arr = vector<vector<int> >(n + 1);
		for (int i = 0; i < n; ++i) {
			maxDist[i] = -1e9;
			dist[i] = 1e9, par[i] = -1;
			scanf("%d%d", &enrg[i], &m);
			while (m--) {
				scanf("%d", &x);
				x--;
				arr[i].push_back(x);
			}
		}
		reach = 1;
		++id;
		if (!dfs(0, n - 1, 100 + 10000)) {
			puts(ans[0]);
			continue;
		}
		if (reach) {
			puts(ans[1]);
			continue;
		}
		dist[0] = 0;
		for (int k = 0; k < n - 1; ++k) {
			for (int i = 0; i < n; ++i) {
				for (int j = 0, ln = arr[i].size(); j < ln; ++j) {
					int y = arr[i][j];
					dist[y] = min(dist[y], dist[x] - enrg[y]);
				}
			}
		}
		bool cycle = 0;
		for (int i = 0; !cycle && i < n; ++i) {
			for (int j = 0, ln = arr[i].size(); j < ln; ++j) {
				int y = arr[i][j];
				if (dist[y] > dist[x] - enrg[y] && dist[y] > 0) {
					cycle = 1;
					break;
				}
			}
		}
		puts(ans[cycle]);
	}
	return 0;
}