any help ?
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;
}