백준 11657 c++ "타임머신" -PlusUltraCode-

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

 

 

 

 

[필자 사고]

음수의 가중치와, 사이클이 존재할 수 있는 가능성 + 최단거리를 묻는 문제 즉 

벨만포드 알고리즘을 사용해야 된다.

 

벨만 포드 알고리즘 이용시 주의할 점은 충분히 많은과정을 반복해야 된다.

아래의 코드처럼 1~N-1까지 반복하는 과정이다.

 

다음으로 마지막에 음수 사이클이 존재하는 지를 확인하기 위해 한번만 더 배열을 탐색하는 과정이 필요하다.

 

알고리즘의 시간복잡도는 O(VE)다. 모든 노드와 모든 간선을 탐색하기 때문이다.

 

 

• Input() 함수
  • 이 함수는 노드와 간선의 정보를 입력받는 역할을 한다.
  • 먼저 노드 수 N과 간선 수 M을 입력받고, 각 노드의 최단 거리를 저장하는 Distance 벡터를 초기화한다.
  • 이후 M개의 간선 정보를 입력받아, 각 간선의 시작 노드, 끝 노드, 그리고 시간을 저장하는 구조체 배열 arr에 저장한다.
• BelManFord() 함수
  • 이 함수는 벨만-포드 알고리즘을 구현한 함수로, 최단 거리를 계산하는 방식이다.
  • 먼저 시작 노드(1번 노드)의 거리를 0으로 초기화한다.
  • 이후 N-1번의 반복을 통해 모든 간선을 확인하며, 각 노드까지의 최단 거리를 갱신한다.
  • 만약, 특정 노드를 거쳐 다른 노드로 가는 경로가 더 짧다면 그 경로로 거리를 갱신하는 방식이다.
• GameStart() 함수
  • BelManFord()를 호출하여 각 노드까지의 최단 경로를 계산한다.
  • 그런 다음, 음수 사이클이 존재하는지 확인한다. 음수 사이클이 있으면, 계속해서 최단 거리를 갱신할 수 있기 때문에, 사이클이 감지되면 -1을 출력하고 종료한다.
  • 음수 사이클이 없을 경우, 1번 노드를 기준으로 다른 노드들까지의 최단 거리를 출력한다. 만약 도달할 수 없는 노드가 있다면 그 노드에 대해 -1을 출력한다.

 

 

 

[소스 코드]

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

struct Edge {
	int start;
	int end;
	long time;
};

vector<Edge> arr;
int N, M;
vector<long> Distance;
void Input() {
	cin >> N >> M;
	Distance.resize(N + 1,LONG_MAX);
	for (int i = 0; i < M; i++) {
		int s, e;
		long w;
		cin >> s >> e >> w;
		arr.push_back({ s,e,w });
	}
}

void BelManFord() {
	Distance[1] = 0;
	for (int i = 1; i < N; i++) {
		for (int k = 0; k < M; k++) {
			Edge edge = arr[k];
			int start = edge.start;
			int end = edge.end;
			int time = edge.time;
			if (Distance[start] == LONG_MAX)continue;
			if (Distance[end] > Distance[start] + time) {
				Distance[end] = Distance[start] + time;
			}
		}
	}
}

void GameStart() {
	BelManFord();
	bool cycle = false;
	for (int i = 0; i < M; i++) {
		Edge edge = arr[i];
		int start = edge.start;
		int end = edge.end;
		int time = edge.time;
		if (Distance[start] == LONG_MAX)continue;
		if (Distance[end] > Distance[start] + time) {
			cycle = true;
			break;
		}
	}

	if (cycle == true) {
		cout << -1;
		return;
	}

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

}

int main(void) {
	Input();
	GameStart();
}