xyzzy(bellman ford).cpp

杭电acm解题报告2001---2099.

//中间不能死
//有正权环的话，得找出终点是否受环影响
#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define MAX 110

int n,m;
int v[MAX],dist[MAX],last[MAX];
vector< vector<int> > path;
queue<int> SQ;

void bellman_ford() 
{
	int now,i,j,l,next;
	l = SQ.size();
	while (l --) {
		SQ.pop();
	}
	SQ.push(1);
	for (i=0;i<=n;i++) {
		dist[i] = INT_MIN;
		last[i] = 0;
	}
	dist[1] = 100;
	
	for (i=0;i<=n;i++) {
		l = SQ.size();
		if (l == 0) {
			break ;
		}
		while (l --) {
			now = SQ.front();
			SQ.pop();
			if (dist[n] > 0) {
				return ;
			}
			for (j=path[now].size()-1;j>=0;j--) {
				next = path[now][j];//注意，每点必须生存
				if (0 < dist[now] + v[next] && dist[next] < dist[now] + v[next]) {
					dist[next] = dist[now] + v[next];
					SQ.push(next);
					last[next] = i;
				}
			}
		}
	}//for
	//检测环是否可到终点
	if (i == n+1) {//有环
		for (i=1;i<=n;i++) {
			if (last[i] != n) {//清空当前环未更新点
				dist[i] = INT_MIN;
			}
			//环标记
			while (true) {
				l = SQ.size();
				if (l == 0 || dist[n] > 0) {
					return ;
				}
				while (l --) {
					now = SQ.front();
					SQ.pop();
					for (j=path[now].size()-1;j>=0;j--) {
						next = path[now][j];
						if (dist[next] < dist[now]) {
							dist[next] = dist[now];//环标记
							SQ.push(next);
						}
					}
				}
			}//for
		}//while
	}
}

int main()
{
	int i,j,t;
	while (scanf("%d",&n) && n!=-1) {
		path.resize(n+10);
		for (i=1;i<=n;i++) {
			scanf("%d",&v[i]);
			path[i].clear();
			scanf("%d",&m);
			for (j=0;j<m;j++) {
				scanf("%d",&t);
				path[i].push_back(t);
			}
		}
		bellman_ford();
		if(dist[n] > 0) {
			puts("winnable");
		}
		else {
			puts("hopeless");
		}
	}
}