# 題目: UVa 10557 – XYZZY

# 題目說明

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


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

  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/