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

11657번: 타임머신

벨만 포드를 이용한 문제이다. 기존 벨만 포드와 동일하게 구현을 해주면 된다. 반복문을 돌 때 간선이 없을 경우가 있기 때문에 d[from] == INF일 경우 continue를 해주는 조건을 추가해주었다. 반복문을 돌면서 최단 거리를 구한 후 다시 한번 더 반복문을 돌면서 음수 사이클을 찾아 만약 존재할 경우 -1을 출력해주었고 없을 경우 각 노드의 최단 거리를 출력해주었다.
생각보다 오래 걸린 문제였다. 처음 문제를 봤을 때 음수 가중치가 존재하고 최단 거리를 구해야 한다는 점을 통해 벨만 포드를 유추해낼 수 있었는데 자료형, 최댓값, 조건문, 음수 사이클 찾기들을 잘 못 설정해 계속해서 틀렸었다. 이는 문제를 잘 읽어보지 못해 일어난 문제였다... 문제를 잘 읽어보고 풀어보도록 하자.

#include <iostream>
#include <vector>

#define INF 4e10

using namespace std;

int N, M;
vector<pair<pair<int, int>, long long>> v;
long long d[501];

void solution() {
	for (int i = 1; i <= N; i++) {
		d[i] = INF;
	}

	d[1] = 0;

	for (int i = 0; i < N - 1; i++) {
		for (int j = 0; j < M; j++) {
			int from = v[j].first.first;
			int to = v[j].first.second;
			int cost = v[j].second;

			if (d[from] == INF || d[to] <= d[from] + cost) continue;

			d[to] = d[from] + cost;
		}
	}

	for (int i = 0; i < M; i++) {
		int from = v[i].first.first;
		int to = v[i].first.second;
		int cost = v[i].second;

		if (d[from] == INF) continue;
		if (d[to] > d[from] + cost) {
			cout << -1;
			return;
		}
	}

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

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

	cin >> N >> M;

	int a, b, c;
	for (int i = 0; i < M; i++) {
		cin >> a >> b >> c;
		v.push_back({ {a, b},c });
	}

	solution();
	
	return 0;
}