# 題目: UVa 558 - Wormholes

# 題目說明

給一張有向圖，n個點透過m條邊相連，每個邊有weight
求圖上是否有負環

---

INPUT:
第一行有一個整數T，代表有幾筆測資
每筆測資第一行有兩個整數n、m，代表有n個點及m條邊
接下來有m行，每行有三個整數u、v、w，代表點u連接到點v(單向)且weight為w

---

OUTPUT:
有負環輸出possible，無則輸出not possible

# 解題方法

先建圖
接著以bellman演算法找到最短路徑，若還能找到更短的邊則有負環

# 參考程式碼

#include <iostream>
#include <vector>
#include <tuple>
#include <climits>

using namespace std;

vector< tuple<int, int, int> > edge;
int dis[1001];

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

	for (int i = 0; i < n - 1; ++i) for (auto& [u, v, w] : edge)
		if (dis[u] != -1)  dis[v] = min(dis[v], dis[u] + w);

	for (auto& [u, v, w] : edge) if (dis[u] + w < dis[v]) return true;

	return false;
}

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

	int T;
	cin >> T;

	while (T--)
	{
		int n, m;
		cin >> n >> m;

		// init
		edge.clear();
		fill(dis, dis + n, INT_MAX);

		while (m--)
		{
			int u, v, w;
			cin >> u >> v >> w;
			edge.push_back({ make_tuple(u, v, w) });
		}

		// bellman algorithm
		cout << (bellman(n) ? "possible\n" : "not possible\n");
	}

	return 0;
}

# 參考資料

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