#include<iostream>
#include<fstream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<ctype.h>
#include<algorithm>
#include<string>
#define PI acos(-1.0)
#define maxn 110
#define INF 1<<25
#define mem(a, b) memset(a, b, sizeof(a))
typedef long long ll;
using namespace std;
vector<int> v[maxn];
int value[maxn];
int energy[maxn];
int n;
bool flag = false;
int que[100000];
void bfs(int x)
{
int visit[maxn] = {0};
int i, j, q, font = 0, rear = 1;
que[font] = x;
visit[x] = 1;
while(font < rear)
{
q = que[font++];
if (q == n)
{
flag = true;
return ;
}
for (i = 0; i < v[q].size(); i++)
{
j = v[q][i];
if (!visit[j]) que[rear++] = j, visit[j] = 1;
}
}
}
void dfs(int s)
{
if (flag) return ;
if (s == n && energy[s] > 0)
{
flag = true;
return ;
}
int tol = v[s].size();
for (int i = 0; i < tol; i++)
{
int j = v[s][i];
if (energy[j] && energy[s] + value[j] > energy[j])
{
bfs(j);
if (flag) return ;
}
if (!energy[j] && energy[s] + value[j] > 0)
{
energy[j] = energy[s] + value[j];
dfs(j);
}
}
}
int main ()
{
int i, j, k;
while(scanf("%d", &n) != EOF)
{
if (n == -1) break;
flag = false;
for (i = 1; i <= n; i++)
{
v[i].clear();
scanf("%d%d", value + i, &k);
while(k--)
{
scanf("%d", &j);
v[i].push_back(j);
}
}
energy[1] = 100;
dfs(1);
if (flag) puts("winnable");
else puts("hopeless");
mem(energy, 0);
}
return 0;
}
原文:http://blog.csdn.net/sio__five/article/details/18659597