[백준 11657] 타임머신

간선이 음의 가중치가 존재할 수 있다는 점에서 벨만포드를 사용해야한다는 것을 알 수 있다.

 

---

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <vector>
#define SIZE 501
#define INF int(1e9)

using namespace std;

int N, M;
vector<pair<pair<int, int>, int>> v;

void solve() {
	long long ans[SIZE];
	for (int i = 1; i <= N; i++) ans[i] = INF;
	ans[1] = 0;

	int start, end, cost;
	for (int i = 0; i < N - 1; i++) {
		for (int k = 0; k < M; k++) {
			start = v[k].first.first;
			end = v[k].first.second;
			cost = v[k].second;

			if (ans[start] == INF) continue;

			if (ans[start] + cost < ans[end]) {
				ans[end] = ans[start] + cost;
			}
		}
	}

	// 사이클 검사
	for (int k = 0; k < M; k++) {
		start = v[k].first.first;
		end = v[k].first.second;
		cost = v[k].second;

		if (ans[start] == INF) continue;

		if (ans[start] + cost < ans[end]) {
			cout << "-1";
			return;
		}
	}

	for (int i = 2; i <= N; i++) {
		if (ans[i] == INF) cout << "-1" << "\n";
		else cout << ans[i] << "\n";
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> N >> M;

	int start, end, cost;
	for (int i = 0; i < M; i++) {
		cin >> start >> end >> cost;
		v.push_back(make_pair(make_pair(start, end), cost));
	}

	if (N == 1) return 0;

	solve();

	return 0;
}