http://poj.org/problem?id=1932
spfa求最长路，判断dist[n] > 0，需要注意的是有正环存在，如果有环存在，那么就要判断这个环上的某一点是否能够到达n点,如果能，就说明可以到达，否则，就说明不能。
/*************************************************************************
> File Name: poj1932.cpp
> Author: syhjh
> Created Time: 2014年03月04日 星期二 16时54分43秒
************************************************************************/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std; const int MAXN = ( + );
const int inf = 0x3f3f3f3f;
int n, st, energy[MAXN];
int dp[MAXN], Count[MAXN];
vector<int > g[MAXN];
bool mark[MAXN]; bool spfa()
{
for (int i = ; i <= n; i++) dp[i] = -inf;
memset(mark, false, sizeof(mark));
memset(Count, , sizeof(Count));
queue<int > que;
que.push();
dp[] = ;
while (!que.empty()) {
int u = que.front();
que.pop();
mark[u] = false;
if (Count[u]++ > n || u == n) {
st = u;
return true;
}
for (int i = ; i < (int)g[u].size(); i++) {
int v = g[u][i];
if (dp[u] + energy[v] > dp[v] && dp[u] + energy[v] > ) {
dp[v] = dp[u] + energy[v];
if (!mark[v]) {
mark[v] = true;
que.push(v);
}
}
}
}
return false;
} void dfs(int u)
{
mark[u] = true;
for (int i = ; i < (int)g[u].size(); i++) {
int v = g[u][i];
if (!mark[v]) dfs(v);
}
} int main()
{
while (cin >> n && n != -) {
for (int i = ; i <= n; i++) g[i].clear();
for (int i = ; i <= n; i++) {
int u, k;
cin >> energy[i] >> k;
while (k--) {
cin >> u;
g[i].push_back(u);
}
}
st = -;
if (spfa()) {
memset(mark, false, sizeof(mark));
dfs(st);
if (mark[n]) {
cout << "winnable" << endl;
} else
cout << "hopeless" << endl;
} else if (dp[n] > ) {
cout << "winnable" << endl;
} else
cout << "hopeless" << endl;
}
return ;
}