Week8 - Bellman Ford

#include<iostream>
#include<vector>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	const int INF = 99999999;		// 무한
	bool has_cycle = false;			// 음수 사이클 체크
	int n, m;
	long long dist[501];			// 최종 결과값
	vector<pair<int, int>> d[501];	// 간선 정보

	cin >> n >> m;

	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		d[a].push_back({ b, c });
	}

	fill_n(dist, n+1, INF);
	dist[1] = 0;

	for (int i = 0; i < n - 1; i++) {
		for (int here = 1; here <= n; here++) {
			if (dist[here] == INF) continue;
			for (auto& p : d[here]) {
				int there = p.first;
				int t = p.second;
				if (dist[here] + t < dist[there]) dist[there] = dist[here] + t;
			}
		}
	}

	// 음수 사이클이 있는지 확인
	for (int here = 1; here <= n; here++) {
		if (dist[here] == INF) continue;
		for (auto& p : d[here]) {
			int there = p.first;
			int t = p.second;
			if (dist[here] + t < dist[there]) has_cycle = true;
		}
	}

	if (has_cycle) cout << -1;
	else {
		for (int i = 2; i <= n; i++) {
			cout << ((dist[i] == INF) ? -1 : dist[i]) << "\n";
		}
	}
}

#include<iostream>
#include<vector>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int tc;
	cin >> tc;

	for (int i = 0; i < tc; i++) {
		bool has_cycle = false;
		int n, m, w;
		cin >> n >> m >> w;

		long long dist[501];
		vector<pair<int, int>> d[501];

		for (int i = 1; i <= m + w; i++) {
			int s, e, t;
			cin >> s >> e >> t;
			if (i <= m) {
				d[s].push_back({ e,t });
				d[e].push_back({ s,t });
			}
			else d[s].push_back({ e,-t });
		}

		fill_n(dist, n + 1, 0);

		for (int i = 1; i <= n; i++) {
			for (int here = 1; here <= n; here++) {
				for (auto& p : d[here]) {
					int there = p.first;
					int d = p.second;

					if (dist[here] + d < dist[there]) {
						if (i == n) has_cycle = true;
						else dist[there] = dist[here] + d;
					}
				}
			}
		}

		cout << ((has_cycle) ? "YES" : "NO") << "\n";
	}
}