#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