[C/C++] 백준 11657번 - 타임머신 (벨만-포드 알고리즘)

문제

N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 버스가 M개 있다. 각 버스는 A, B, C로 나타낼 수 있는데, A는 시작도시, B는 도착도시, C는 버스를 타고 이동하는데 걸리는 시간이다. 시간 C가 양수가 아닌 경우가 있다. C = 0인 경우는 순간 이동을 하는 경우, C < 0인 경우는 타임머신으로 시간을 되돌아가는 경우이다.

1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. 

출력

만약 1번 도시에서 출발해 어떤 도시로 가는 과정에서 시간을 무한히 오래 전으로 되돌릴 수 있다면 첫째 줄에 -1을 출력한다. 그렇지 않다면 N-1개 줄에 걸쳐 각 줄에 1번 도시에서 출발해 2번 도시, 3번 도시, ..., N번 도시로 가는 가장 빠른 시간을 순서대로 출력한다. 만약 해당 도시로 가는 경로가 없다면 대신 -1을 출력한다.

 

<코드>

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
#define INF 2100000000 // 21억

int N, M;
int A, B, C;
int a, b;
long long dist[501];
bool cycle;
vector<pair<int, int>> v[501];

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie();

	cin >> N >> M;

	for (int i = 0; i < M; i++)
	{
		cin >> A >> B >> C;
		v[A].push_back({ B,C });
	}
	
	for (int i = 1; i <= N; i++)
		dist[i] = INF; // 모든 노드를 INF로 세팅

	dist[1] = 0; // 시작점 0으로 초기화
	
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
		{
			for (int k = 0; k < v[j].size(); k++)
			{
				int next = v[j][k].first;
				int d = v[j][k].second;

				if (dist[j] != INF && dist[next] > dist[j] + d)
				{
					dist[next] = dist[j] + d;
					if (i == N) cycle = true;
				}
					
			}
		}

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

	
}

 

풀이 방법

 

다익스트라와 벨만 포드 알고리즘은 모두 최단 거리를 구하는 알고리즘이지만 다익스트라의 경우 실행속도는 빠른 반면 음의 간선이 있을 경우 제대로 동작하지 않을 가능성이 있습니다. 벨만 포드 알고리즘의 시간 복잡도는 O(VE)로 다익스트라(O(ElogV))보다 느리지만 음의 간선이 있는 경우에도 사용이 가능합니다.

 

for (int i = 1; i <= N; i++)
	for (int j = 1; j <= N; j++)
	{
		for (int k = 0; k < v[j].size(); k++)
		{
			int next = v[j][k].first;
			int d = v[j][k].second;

			if (dist[j] != INF && dist[next] > dist[j] + d)
			{
				dist[next] = dist[j] + d;
				if (i == N) cycle = true;
			}
					
		}
	}

V를 정점이라고 할 때 벨만-포드 알고리즘에서는 V-1번의 반복문을 돌고나면 최단 거리가 완성됩니다. 그리고 여기서 반복문을 한번 더 돌렸을 때 최단거리가 갱신이 된다면 음의 싸이클이 존재한다는 의미이므로

i가 N일 때 최단거리가 갱신될 시에 bool형 변수인 cycle을 true로 저장합니다.

 

 

www.acmicpc.net/problem/11657

11657번: 타임머신

 

 

 

 

참고 블로그 - m.blog.naver.com/kks227/220796963742