[백준 11657] 타임머신 (C++)

문제 링크: https://www.acmicpc.net/problem/11657

11657번: 타임머신

1. 주의할 점

- 음의 가중치를 가지는 간선이 존재한다 -> 벨만포드 알고리즘 (다익스트라 알고리즘은 음의 가중치가 있으면 적용하지 못한다)

- Int의 범위를 벗어날 수도 있기 때문에 (Dist의 값이) Long Long으로 설정하지 않으면 "출력초과"가 발생한다

 

2. 구현

- 2차 배열을 이용한 형태와 벡터에 간선을 담는 형태가 있는데 벡터를 이용하겠다(2차 배열 결과: 100ms이상, 벡터 결과: 8ms)

- 입력받는 모든 간선에 대한 정보를 시작점에 저장한다

- Dist[]배열을 전부 MAX로 초기화 해준 후, Node 1에서 시작하기 때문에 Dist[1] =0도 추가적으로 설정한다

- N-1번의 순환을 거친 후, N번째 순환에서(I가) Dist[to]가 또 갱신이 된다면, 음의 사이클이 존재한다고 판단하여 Cycle = True로 설정한다

- Cycle이 True인 경우 -1만 출력한다

- Cycle이 False인 경우 Dist[]값을 출력하며, Dist[]값이 MAX인 자리에는 -1을 출력한다 

#define MAX 987654321
#include <iostream>
#include <vector>
using namespace std;
struct info {
	long long to, val;
};
info tmp;
vector<info> v[501];
long long dist[501];
bool cycle = false;
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int node, edge, from, to, result;
	long long val;
	cin >> node >> edge;
	for (int i = 0; i < edge; i++) {
		cin >> from >> to >> val;
		tmp.to = to;
		tmp.val = val;
		v[from].push_back(tmp);
	}
	for (int i = 1; i <= node; i++)
		dist[i] = MAX;
	dist[1] = 0;

	for (int i = 1; i <= node; i++) {
		for (int j = 1; j <= node; j++) {
			from = j;
			for (int k = 0; k < v[from].size(); k++) {
				to = v[from][k].to;
				val = v[from][k].val;
				if (dist[from] != MAX && dist[to] > dist[from] + val) {
					if (i == node)
						cycle = true;
					dist[to] = dist[from] + val;
				}
			}
		}
	}
	if (cycle)
		cout << -1;
	else {
		for (int i = 2; i <= node; i++) {
			if (dist[i] == MAX) cout << -1 << '\n';
			else cout << dist[i] << '\n';
		}
	}
	return 0;
	system("pause");
}