백준 11657(타임머신)

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

11657번: 타임머신

 

개빡대가리였었던 문제

 

N개의 도시가 있고, M개의 이동경로가 있다. 만약 1번의 도시에서 나머지 도시까지 최단경로로 갈때, 그 최단거리를 구하는 문제. 

 

다익스트라 하지만 다 익스트라에서는 음수의 간선을 사용할 수 없다. 왜냐하면 일단 다익스트라는 순환구조가 불가능하기 때문이다. 

 

그렇기 때문에 음수의 간선이 들어가면 계속해서 순환하는 경우를 생각하지 못 하게 된다. 

 

그래서 만약에 계속해서 순환하는 경우가 생기는 경우에는 다른 알고리즘을 사용해야 함을 알 수 있다. 

 

벨만 포드 알고리즘이라고 하는 알고리즘을 사용해야 한다. 

 

수학적 증명은 하지 않겠다. 

 

어떻게 진행되냐면 N개의 정점수 * 탐색을 하는데 

 

탐색방법은 

 

모든 간선에 대해서 

 

a->b 인경우에 

dist[b] vs dist[a] + city[a][b] 

 

dist[]를 최신화해준다. 

 

물론 더 작을때

				if (dist[i] > dist[j] + city[j][i]) {
					dist[i] = dist[j] + city[j][i];

 

이렇게 N-1번 반복하면 최종 최단거리가 나온다고 하고, 

만약에 음수 순환인 경우에는 N-1번 이후에 한 번 더 순환했을때, 결과가 바뀌므로 그걸 체크해주면 된다.

 

그냥 인접행렬을 이용해서 N^3의 풀이로 풀었다. 

 

#include<iostream>
#include<vector>
using namespace std;
#define MAX 501

int city[MAX][MAX];
long long dist[MAX];
int N, M, a, b, c;
int INF = 987654321;
bool cycle;
bool check[MAX][MAX];

void solve() {
	for (int i = 2; i <= N; i++) {
		dist[i] = INF;
	}
	for (int k = 1; k <= N; k++) {
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				if (i == j || dist[j] == INF || city[j][i] == INF) continue;
				if (dist[i] > dist[j] + city[j][i]) {
					dist[i] = dist[j] + city[j][i];
					if (k == N) cycle = true;
				}
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		cin >> a >> b >> c;
		if (check[a][b]) {
			if (city[a][b] > c) city[a][b] = c;
		}
		else city[a][b] = c;
		check[a][b] = true;
	}
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (i == j || check[i][j]) continue;
			if (city[i][j] == 0) city[i][j] = INF;
		}
	}
	solve();

	if (cycle) {
		cout << -1 << "\n";
		return 0;
	}

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

}

 

 

인접행렬이 아니라 인접리스트로 실제 간선만 조사하면 시간복잡도는 훨씬 줄어든다.