[백준] 11657번: 타임머신

📌 문제

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

📌 설명

음의 가중치를 가지는 간선에서 최단 경로를 구하는 문제이므로 다익스트라는 사용할 수 없으며, 벨만-포드나 플로이드-워셜 알고리즘을 사용해야 한다. 단, 몇 가지 고려해야 하는 점이 있다.

먼저 출발지와 도착지가 같은 버스가 여러 개 존재할 수 있다. 이는 예제 입력 3에 나와있으며, 단순히 입력을 받을 때 가중치가 작은 값으로 계속 초기화시켜주면 된다.

두 번째는 만약 1번 도시에서 출발해 어떤 도시로 가는 과정에서 시간을 무한히 오래 전으로 되돌릴 수 있다면 첫째 줄에 -1을 출력한다. 라는 부분이다. 이는 최단 거리 배열(dist)에서 음의 사이클이 존재하고, 출발지(1)에서 접근할 수 있는 경우이다. 구체적으로 표현하면, dist[i][i] < 0이고 dist[1][i]의 경로가 존재한다면 -1을 출력하고 종료해야 한다.

마지막으로 삼중 for문을 통해 dist배열을 초기화할 때, 출발 노드에서 중간 노드 또는 중간 노드에서 도착 노드까지의 경로가 존재하지 않는다면 dist를 초기화할 수 없다.

위 사항들을 참고하여 코드를 작성해야 한다.

📌 코드

#include <iostream>
#include <algorithm>

#define MAX_INF 6e7+1

using namespace std;

int arr[501][501];
int dist[501][501];

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

	int n, m;
	cin >> n >> m;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			arr[i][j] = MAX_INF;
		}
	}

	for (int i = 0; i < m; i++) {
		int s, e, c;
		cin >> s >> e >> c;
		arr[s][e] = min(arr[s][e], c);
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i == j)
				dist[i][j] = min(dist[i][j], 0);
			else if (arr[i][j])
				dist[i][j] = arr[i][j];
		}
	}

	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (dist[i][k] == MAX_INF || dist[k][j] == MAX_INF)
					continue;

				dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
			}
		}
	}

	// i에서 음의 사이클이 발생하고 1에서 도달할 수 있는 경우
	for (int i = 1; i <= n; i++) {
		if (dist[i][i] < 0) {
			if (dist[1][i] != MAX_INF) {
				cout << -1;
				return 0;
			}
		}
	}

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