# 題目: UVa 10557 – XYZZY

# 題目說明

給一張有向圖，每個點都有能量變化(可能正可能負)，起點為100能量
求起點是否能走到終點

---

INPUT:
每筆測資第一行有一個整數n，代表有n個點，若n = -1結束程式
接下來有n行，依序為1 ~ n個點的資訊，每行至少有兩個整數val、j

1. val代表該點的能量消耗
2. j代表接下來有j個整數，該點連接到這些整數

---

OUTPUT:
從起點(1)能走到終點(n)輸出winnable，否則輸出hopeless

# 解題方法

因為題目為能量消耗，所以我們要找最大路徑
當有正環發生時，若該點能走到終點，則能量無限，直接輸出winnable
透過dfs從終點反向找，終點是否能走到該點

先建圖，同時建一個反向的圖方便dfs
接著以bellman演算法找到最大路徑，之後判斷正環
有則執行上述，無則判斷終點的能量是否大於0即可

# 參考程式碼

#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;

vector< vector<int> > G;
vector< vector<int> > G_;
vector<int> energy;
vector<int> dis;
unordered_set<int> us;

void dfs(int u)
{
	us.emplace(u);
	for (auto& v : G_[u]) if (!us.count(v)) dfs(v);
}

bool bellman(int n)
{
	dis[1] = 100;

	for (int i = 0; i < n - 1; ++i) for (int u = 1; u <= n; ++u) 
	{
		for (auto& v : G[u]) if (dis[u]) dis[v] = max(dis[v], dis[u] + energy[v]);
	}

	for (int u = 1; u <= n; ++u) for (auto& v : G[u])
	{
		if (dis[u] && dis[v] < dis[u] + energy[v])
		{
			if (us.count(v)) return true;
			dis[v] = dis[u] + energy[v];
		}
	}

	return dis[n];
}

int main()
{
	// fast io
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int n;
	while (cin >> n, n != -1)
	{
		// init
		G.assign(n + 1, vector<int>());
		G_.assign(n + 1, vector<int>());
		energy.assign(n + 1, 0);
		dis.assign(n + 1, 0);
		us.clear();

		for (int i = 1; i <= n; ++i)
		{
			int val, j, nxt;
			cin >> val >> j;
			energy[i] = val;
			while (j--) cin >> nxt, G[i].emplace_back(nxt), G_[nxt].emplace_back(i);
		}

		dfs(n);

		// bellman algorithm
		cout << (bellman(n) ? "winnable\n" : "hopeless\n");
	}

	return 0;
}

# 參考資料

https://www.larrysprognotes.com/UVa%20-%2010557/