[C++] 백준 11657 : 타임머신

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

11657번: 타임머신

백준 11657 타임머신을 풀었다.

 

출발 노드로부터 다른 모든 노드까지의 최단 경로를 구해야 하는 문제다.

간선의 가중치가 음수인 경우가 있어서 벨만 포드 알고리즘을 사용해야 한다.

 

벨만 포드 알고리즘을 사용해서 n-1번째 노드까지 최단 경로를 구했으면 다시 한번 모든 간선에 대해 비용 연산을 해서 음의 사이클을 찾아야 한다.

주의해야 할 점은 음의 사이클이 존재하더라도 출발 노드에서 출발해서 음의 사이클에 도달할 수 없는 경우가 있다.

따라서 음의 사이클이 존재한다고 바로 -1을 출력하고 종료하면 안된다.

dist[start] == INF 는 start노드로 가는 경로가 존재하는지 확인하는 조건이다. 이 조건을 사용해서 도달할 수 없는 노드, 음의 사이클은 무시할 수 있다.

 

아래는 전체 코드입니다.

#include <iostream>
#include <stdio.h>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#pragma warning(disable:4996)
using namespace std;

#define INF 987654321

int n, m;
vector<pair<pair<int,int>,int>> busRoute;
vector<long long> dist(501,INF);

int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int start, end, cost;
		scanf("%d %d %d", &start, &end, &cost);
		busRoute.push_back({ {start,end},cost });
	}

	dist[1] = 0;
	for (int i = 1; i <= n-1; i++) {
		for (int j = 0; j < busRoute.size(); j++) {
			int start = busRoute[j].first.first;
			int end = busRoute[j].first.second;
			int cost = busRoute[j].second;
			long long next_cost = cost + dist[start];
			if (dist[start] == INF)
				continue;
			if (dist[end] > next_cost) {
				dist[end] = next_cost;
			}
		}
	}

	for (int i = 0; i < busRoute.size(); i++) {
		int start = busRoute[i].first.first;
		int end = busRoute[i].first.second;
		int cost = busRoute[i].second;
		long long next_cost = cost + dist[start];
		if (dist[start] == INF)
			continue;
		if (dist[end] > next_cost) {
			cout << "-1";
			return 0;
		}
	}


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

	return 0;
}