백준1956 - 운동

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

1956번: 운동

플루이드 와샬 문제다. 플루이드 와샬을 수행한 결과 사이클이 존재하는 경우를 묻는 문제다. 사이클이 이루어지는 경우 행과 열의 인덱스를 교환해도 INF값이 존재하는 것이 아닌 다른 정수 값이 존재하는 경우로 가정하여 풀었다. 이제 플루이드 와샬 문제말고 다른 분류의 문제를 집중적으로 풀어야 겠다.

 

#include <iostream>
#define INF 100000 //무한대를 표현
using namespace std;

int mat[401][401]; //현재 한번에 갈 수 있는 마을간의 정보
int d[401][401]; //플루이드 와샬을 수행 후 갈 수 있는 마을의 정보
int V, E; //V는 도시의 갯수 E는 도로의 갯수
int a, b, c; //a는 출발하는 도시, b는 도착할 도시, c는 a->b로 가는 비용
int Min = INF; //최소 값을 일단 INF로 지정

//입력하기전 행과 열이 같은 경우를 빼고 모두 무한대로 지정
void setting() {
	for (int i = 1; i <= V; i++) {
		for (int j = 1; j <= V; j++) {
			if (i == j) {
				mat[i][j] = 0;
			}
			else {
				mat[i][j] = INF;
			}
		}
	}
}

//플루이드 와샬을 수행
void FloydWarshall() {
	for (int i = 1; i <= V; i++) {
		for (int j = 1; j <= V; j++) {
			d[i][j] = mat[i][j];
		}
	}

	for (int k = 1; k <= V; k++) { //거처가는 곳의 좌표
		for (int i = 1; i <= V; i++) { //출발하는 곳의 좌표
			for (int j = 1; j <= V; j++) { //도착하는 곳의 좌표
				if (d[i][k] + d[k][j] < d[i][j]) { //k를 거쳐가는 방법이 지금 i->j로 가는 방법보다 빠르면
					d[i][j] = d[i][k] + d[k][j]; //갱신
				}
			}
		}
	}
}

int main() {	
	cin >> V >> E;
	setting(); //일단 입력전 2차원 배열에 작업

	for (int i = 0; i < E; i++) {
		cin >> a >> b >> c;
		mat[a][b] = c;
	}

	FloydWarshall(); //플루이드 와샬 수행

	for (int i = 1; i <= V; i++) {
		for (int j = 1; j <= V; j++) {
			if (i == j) {
				continue;
			}
			else {
				if (d[i][j] + d[j][i] < Min) { //i->j로 오는 길과 j->i로 오는 길이 모두 존재하고 이 길이 현재 최솟값보다 작으면
					Min = d[i][j] + d[j][i]; //갱신
				}
			}
		}
	}
	if (Min == INF) { //사이클이 이루어지지 않을 경우
		cout << -1;
	}
	else { //사이클이 이루어진 경우
		cout << Min;
	}
}