백준 11657번(타임머신) c++ <벨만 포드 알고리즘>

문제

11657번: 타임머신

n개의 노드가 주어지고, m개의 노드 간선 정보가 주어집니다.

간선 정보는 a, b, c 형태로 주어지고 a는 출발점, b는 도착점, c는 비용입니다.

c는 음수도 가능합니다.

1번 노드에서 시작해서 2~n번 노드까지의 최소 비용을 차례대로 출력하면 되는 문제입니다.

만약 1번 노드에서 도달할 수 없는 노드는 -1을 출려하고, 최솟값을 정할 수 없으면 -1을 출력합니다.

 

비용이 음수이기 때문에 음의 사이클이 형성되면 사이클 돌때마다, 최솟값이 갱신될 수 있습니다.

따라서 최소비용을 구하는 다익스트라 알고리즘은 사용할 수 없습니다.

 

이때, 벨만 포드 알고리즘을 사용할 수 있습니다.

벨만 포드 알고리즘 또한 최소비용을 구하는 알고리즘입니다. 

벨만 포드 알고리즘은 간선의 비용이 음수여도 최솟값을 구할 수 있습니다.

하지만 음의 사이클이 형성되면 제대로 작동하지 않습니다.

#include<iostream>
#include<string>
#include<cstring>
#include<sstream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>

#define INF 2000000000
using namespace std;
using ll = long long;
ll dist[501];
int n, m;
vector<pair<pair<int, int>, int>>edge;
void bellman_ford();
int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		edge.push_back({ {a, b}, c });
	}
	for (int i = 1; i <= n; i++)dist[i] = INF;

	bellman_ford();
	


	return 0;
}
void bellman

먼저 입력 부분입니다. 

n과 m을 입력받고 m개의 간선정보를 edge라는 벡터안에 저장합니다.

dist[]는 모두 INF로 초기화 해주고 

bellman_ford() 함수를 실행합니다.

void bellman_ford() {
	dist[1] = 0;
	for (int i = 0; i < n - 1; i++) {
		for (int j = 0; j < edge.size(); j++) {
			int from = edge[j].first.first;
			int to = edge[j].first.second;
			int cost = edge[j].second;

			if (dist[from] == INF)continue;
			if (dist[to] > dist[from] + cost)
				dist[to] = dist[from] + cost;
		}
	}
}

먼저 1번 노드가 출발점이므로 dist[1] = 0으로 초기화 해줍니다.

그 다음 n-1번 반복하게 되는데 이때 다이나믹 프로그램 형식으로 진행됩니다.

for (int j = 0; j < edge.size(); j++) {
		int from = edge[j].first.first;
		int to = edge[j].first.second;
		int cost = edge[j].second;

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

그 다음 한번더 벨만 포드 알고리즘을 더 돌립니다.

이 때 dist의 값이 또 다시 낮아지면 음의 사이클이 발생했다는 의미 이므로 -1을 출력합니다.

---

전체 코드입니다.

#include<iostream>
#include<string>
#include<cstring>
#include<sstream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>

#define INF 2000000000
using namespace std;
using ll = long long;
ll dist[501];
int n, m;
vector<pair<pair<int, int>, int>>edge;
void bellman_ford();
int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		edge.push_back({ {a, b}, c });
	}
	for (int i = 1; i <= n; i++)dist[i] = INF;

	bellman_ford();
	


	return 0;
}
void bellman_ford() {
	dist[1] = 0;
	for (int i = 0; i < n - 1; i++) {
		for (int j = 0; j < edge.size(); j++) {
			int from = edge[j].first.first;
			int to = edge[j].first.second;
			int cost = edge[j].second;

			if (dist[from] == INF)continue;
			if (dist[to] > dist[from] + cost)
				dist[to] = dist[from] + cost;
		}
	}

	for (int j = 0; j < edge.size(); j++) {
		int from = edge[j].first.first;
		int to = edge[j].first.second;
		int cost = edge[j].second;

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

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