[백준] 11657번 타임머신 C++

문제 출처: https://www.acmicpc.net/problem/11657

11657번: 타임머신

벨만 포드 알고리즘을 이용하여 1번에서 출발하여 2,3,...,N번 까지 최단거리를 구하고 문제에서 무한이 오래전으로 돌릴수 있다면 ~이라는 조건이 있으므로 음수 사이클이 존재하는지 확인하여 출력한다.

추가적으로 도시의 개수가 500개, 노선의 개수가 6000개 간선의 가중치가 -10000 ~ 10000이므로 음의 사이클이 존재하지 않는다면 최대 가중치는 500 * 10000이지만 음의 사이클이 존재한다면 -21억을 넘을수 있기 때문에 long long 자료형으로 사용해야 한다.

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>

using namespace std;
typedef pair<int, int>P;

long long INF = 123456789123;
int N, M;
vector<P> adj[501];
long long dist[501];

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

	cin >> N >> M;
	fill(dist, dist + 501, INF);

	for (int j = 0; j < M; j++) {
		int A, B, d;
		cin >> A >> B >> d;
		adj[A].push_back(P(B, d));
	}

	dist[1] = 0;
	int minusCircle = 0;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			for (P p : adj[j]) {
				int next = p.first;
				int d = p.second;
				if (dist[j] != INF && dist[next] > dist[j] + d) {
					dist[next] = dist[j] + d;
					if (i == N)minusCircle = 1;
				}
			}
		}
	}


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


}