HDU 1317 XYZZY 别想的过于复杂

    题意：从起点1出发，此时身上有100能量，每通过一条路（单向）走到一个房间就可以获得相应能量值（-100~100），如果能量值小于等于0，直接输出hopeless，如果到达终点能量值大于0，输出winnable。

思想：很多人把问题复杂化了许多，会考虑很多点：能不能走到N；遇到能够无限加能量的环如果判断这个环是不是在最长路上；遇到能无限减能量的环如何判断这个环是不是在最长路上（显然这种负环我们绝对不会让它转一圈的）；将过多的焦点放到了输出路径之类的问题上面。

        其实我们可以将问题简单化：如果遇到负环，我最多走一遍就完事了，因为跑的是最长路，所以肯定直走一遍，这一点我们完全不需要特殊判断什么的，那么最关键 的问题来了，如果在没有遇到正环之前如果能量没有小于等于0的话那么不管之后的路上要减去多少能量，就一定能走到终点，因为我可以在正环处将能量值充到无限大，然后再去走接下来的路。那么这么一来就造成一个假象就是“我们一定要知道最长路上有没有正环”，然后无限YY就开始了。其实我们知道关注一点就好了，就是到达终点时候我们的能量是否大于0，那么不管我们遇到的正环是不是在最长路上，我们都让他充能充到无限大（这里面100*100）就够了。然后只要路径能变长我就把它推入队列即可。

        还有一个就是遇到点的权就不会往边上写了，这题目可以假设一个点0，然后从0向点1连一条权值为100的边即可。以上解释了一些关键性问题。下面是AC代卖，500+MS，其实有一个优化，不需要这么多，其实一个点被推入队列N次（不是遇到N次，以为负环的点也能被遇到N次），就直接给他充能无限大也可以。

#include<iostream>
#include<cstring>
#include<queue>
#include<cstdlib>
using namespace std;
const int max_size = 110;
const int inf = 0x7fffffff;
int N;
struct edge{
	int v;
	int w;
	edge *next;
};
typedef struct node{
	edge *fstedge;
}Alist[max_size];
Alist alist; 
void _init()
{
	for(int i = 0; i <= N; ++i){
		alist[i].fstedge = NULL;
	}
}

void add(int u, int v, int w){
	struct edge *new_edge;
	new_edge = (edge*)malloc(sizeof(edge));
	
	new_edge->v = v;
	new_edge->w = w;
	new_edge->next = alist[u].fstedge;
	alist[u].fstedge = new_edge;
} 

bool avail_res()
{
	int dis[max_size];
	queue<int>q;
	
	while(!q.empty()) q.pop();
	for(int i = 0; i <= N; ++i){
		dis[i] = -inf;
	}
	dis[0] = 0;
	q.push(0);
	visit[0] = 1;
	
	while(!q.empty()){
		int u = q.front();
		q.pop();
		for(edge *p = alist[u].fstedge; p != NULL; p = p -> next){
			int v = p->v;
			int w = p->w;
			if(dis[u] < 110 * 110 && dis[v] < dis[u] + w){
				dis[v] = dis[u] + w;
				if(v == N)
				{
					break;
				}
				if(dis[v] > 0)
				{
					pre[v] = u;
					q.push(v);
				}
			} 
		} 
	}
	if(dis[N] > 0) return true;
	return false;
}

int main()
{
	while(cin>>N && N != -1){
		_init();
		add(0, 1, 100);
		for(int i = 1; i <= N; ++i){
			int w, num;
			cin>>w>>num;
			while(num--){
				int v;
				cin>>v;
				add(i, v, w);
			}
		}
		if(avail_res()) cout<<"winnable"<<endl;
		else cout<<"hopeless"<<endl; 
	}
	return 0;
}