[BOJ 11657] 백준 타임머신 - C++ 풀이

https://www.acmicpc.net/problem/11657

문제

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

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

내 코드

벨만포드 최단 거리 알고리즘을 공부하고 예제를 풀어봤다.

참고로 costs를 long long으로 두어야하는 이유는 버스 노선의 최대 개수 500 -1 * 간선의 개수 6,000번 연산을 진행하는 데다가 최대 간선 비용 절대값이 10,000이기 때문에 최대 비용이 엄청 커질 수 있기 때문이다. 같은 이유로 MAX 값을 충분히 크게 두지 않는다면 문제가 생길 수 있다.

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

#define MAX 9'999'999

using namespace std;

struct Edge
{
	int from = 0;
	int to = 0;
	int cost = MAX;
};

int main()
{
	int start = 1;
	int node, edge;
	cin >> node >> edge;

	vector<Edge> edges(edge);
	vector<long long> costs(node + 1, MAX);

	// 자기 자신으로 가는 비용은 0
	costs[start] = 0;

	// 간선 입력
	for (int i = 0; i < edge; ++i)
	{
		int a, b, v;

		cin >> a >> b >> v;

		edges[i].from = a;
		edges[i].to = b;
		edges[i].cost = v;
	}

	// 벨만포드
	// 1. n-1번 간선마다 최소 비용을 구한다
	for (int n = 1; n < node; ++n)
	{
		for (int e = 0; e < edge; ++e)
		{
			// 간선의 시작 지점이 start 노드와 연결되어 있지 않다면 continue;
			if (costs[edges[e].from] == MAX)
				continue;

			// 현재 간선을 거쳐 가는 것이 더 빠르다면 갱신
			costs[edges[e].to] = min(costs[edges[e].to], costs[edges[e].from] + edges[e].cost);
		}
	}

	// 2. 한번 더 갱신을 시도. 만약 갱신 된다면 음수 간선 순환이 발생한 것이므로 -1을 출력
	for (int e = 0; e < edge; ++e)
	{
		// 간선의 시작 지점이 start 노드와 연결되어 있지 않다면 continue;
		if (costs[edges[e].from] == MAX)
			continue;

		// 현재 간선을 거쳐 가는 것이 더 빠르다면 갱신
		if (costs[edges[e].to] > costs[edges[e].from] + edges[e].cost)
		{
			cout << -1 << endl;
			return 0;
		}
	}

	// 결과 출력
	for (int n = 2; n <= node; ++n)
	{
		if (costs[n] == MAX) cout << -1 << endl;
		else cout << costs[n] << endl;
	}
	return 0;
}