BOJ - 11657번 타임 머신 (C++)

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

문제 난이도

Gold 4

문제 접근법

벨만-포드를 이용하는 기본적인 문제이다.
문제 설명 중 시간 C가 양수가 아닌 경우가 있다. C = 0인 경우는 순간 이동을 하는 경우, C < 0인 경우는 타임머신으로 시간을 되돌아가는 경우이다.를 참고하자.
다익스트라는 음의 가중치를 허용하지 않는다.
그리디 알고리즘을 기반으로 했기 때문에 근의 거리만 파악해서 그렇다. 벨만-포드는 간선 횟수만큼 돌며 가중치를 파악하기 때문에 음의 가중치가 있어도 가능하다. DP기반으로 사용한다 생각하면 점화식은 distance[i] = min(distance[i], distance[i] + (i에서 다음으로 가는 가중치))가 된다.

통과 코드

1번째

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

#define INF 987654321

using namespace std;

vector<pair<int,int>> arr[501];
long long dp[501];

int main() {
	int N, M;
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		arr[a].push_back({ b,c });
	}
	for (int i = 1; i <= N; i++) dp[i] = INF;
	dp[1] = 0;
	bool flag = false;
	for (int i = 1; i <= N; i++){
		for (int j = 1; j <= N; j++) {
			for (int k = 0; k < arr[j].size(); k++) {
				int next = arr[j][k].first;
				int val = arr[j][k].second;
				if ((dp[j] != INF) && (dp[next] > dp[j] + val)) {
					dp[next] = dp[j] + val;
					if (i == N) {
						flag = true; //음의 사이클 발견
						break;
					}
				}
			}
		}
	}
	if (flag) cout << "-1\n";
	else {
		for (int i = 2; i <= N; i++) {
			if (dp[i] == INF) cout << "-1\n";
			else cout << dp[i] << "\n";
		}
	}
	return 0;
}

2번째

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

#define INF 987654321

using namespace std;

long long dist[501];

struct Edge {
	int s;
	int e;
	int val;
	Edge(int a, int b, int c) {
		s = a;
		e = b;
		val = c;
	}
};

int main() {
	vector<Edge> Ed;
	int N, M,i,j;
	cin >> N >> M;
	for (i = 1; i <= M; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		Ed.push_back(Edge(a, b, c));
	}
	for (i = 1; i <= N; i++) {
		dist[i] = INF;
	}
	dist[1] = 0;
	for (i = 1; i < N; i++) {
		for (j = 0; j < Ed.size(); j++) {
			int s = Ed[j].s;
			int e = Ed[j].e;
			int t = Ed[j].val;
			if (dist[s] != INF && dist[s] + t < dist[e]) {
				dist[e] = dist[s] + t;
			}
		}
	}
	for (j = 0; j < Ed.size(); j++) {
		int u = Ed[j].s;
		int v = Ed[j].e;
		int w = Ed[j].val;
		if (dist[u] != INF && dist[u] + w < dist[v]) { //음의 사이클 발견
			printf("-1\n");
			return 0;
		}
	}
	for (i = 2; i <= N; i++) {
		if (dist[i] == INF) cout << -1 << "\n";
		else cout << dist[i] << "\n";
	}
	return 0;
}

피드백

처음에 출력초과가 떠서 당황했는데 배열값을 long long 데이터 타입으로 선언했어야 했다. 문제에서 말했듯 만약 1번 도시에서 출발해 어떤 도시로 가는 과정에서 시간을 무한히 오래 전으로 되돌릴 수 있다면 이니깐 말이다!