[백준OJ] 1956번 운동

www.acmicpc.net/problem/1956

1956번: 운동

---

 

-풀이-

플로이드 와샬 알고리즘을 이용하여 모든 도시에서 모든 도시로의 최소거리를 구해준다. 이때 사이클이 생기는것도 허용해야 하므로, i==j 일때 continue하는 조건을 삭제해준다.

알고리즘을 실행시킨 뒤, 자기가 있는 도시부터 자기가있는 도시까지의 거리중 최솟값( maze[i][i] , i는 1~V까지,) 를 구한다.

 

-시간복잡도-

플로이드와샬의 시간복잡도는 O(V³)이 된다.

 

-코드-

 

#include<iostream>
#include<algorithm>
#define MAX 987654321
using namespace std;

int maze[401][401];
int v, e;

int main() {
	cin >> v >> e;
	for (int i = 1; i <= v; i++)
		for (int j = 1; j <= v; j++)
			maze[i][j] = MAX;

	for (int i = 0; i < e; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		maze[a][b] = c;
	}
	for (int k = 1; k <= v; k++) {
		for (int i = 1; i <= v; i++) {
			for (int j = 1; j <= v; j++) {
                if(i==k||j==k) continue;
				if (maze[i][j] > maze[i][k] + maze[k][j]) {
					maze[i][j] = maze[i][k] + maze[k][j];
				}
			}
		}
	}
	int result = MAX;

	for (int i = 1; i <= v; i++) {
		result = min(result, maze[i][i]);
	}

	if (result == MAX) {
		cout << "-1\n";
	}
	else {
		cout << result << "\n";
	}
	return 0;
}