백준 11657 타임머신

벨만포드 알고리즘을 수행하면서, 음수사이클이 있을 경우 -1 출력

참고 : 

벨만포드 알고리즘 http://deque.tistory.com/72

백준 1865 웜홀 http://deque.tistory.com/71

//deque.tistory.com

#define _CRT_SECURE_NO_WARNINGS

#include <iostream> 
#include <vector> 
#include <queue> 
#include <map>
#include <fstream> 
#include <string> 
#include <algorithm>
#include <functional>
#include <limits.h>

using namespace std;

template <typename FIRST, typename SECOND, typename THIRD>
class triple {
public:
	FIRST first;
	SECOND second;
	THIRD third;
	triple(FIRST a, SECOND b, THIRD c) {
		first = a;
		second = b;
		third = c;
	}
};

bool BellmanFord(vector<int> &dist, vector<triple<int, int, int>> &edge, int V, int E, int StartNode) {
	bool hasMinusCycle = false;

	for (int i = 1; i <= V; i++) {
		dist[i] = INT_MAX;
	}
	dist[StartNode] = 0;
	for (int i = 1; i <= V; i++) {
		for (auto nowEdge : edge) {
			int from = nowEdge.first;
			int to = nowEdge.second;
			int weight = nowEdge.third;

			if (dist[from] == INT_MAX) continue;
			if (dist[to] > dist[from] + weight) {
				dist[to] = dist[from] + weight;

				if (i == V) hasMinusCycle = true;
			}
		}
	}
	return hasMinusCycle;
}

int N, M;

int main() {
	scanf("%d %d", &N, &M);

	vector<int> dist(N + 1, INT_MAX);
	vector<triple<int, int, int>> edge; //from, to, weight

	int from, to, weight;
	for (int i = 1; i <= M; i++) {
		scanf("%d %d %d", &from, &to, &weight);
		edge.push_back(triple<int, int, int>(from, to, weight));
	}
	bool hasMinusCycle = BellmanFord(dist, edge, N, M, 1);

	for (int i = 2; i <= N; i++) {
		if (hasMinusCycle) {
			printf("%d\n", -1);
			break;
		}
		if (dist[i] == INT_MAX) dist[i] = -1;
		printf("%d\n", dist[i]);
	}

	return 0;
}