[알고리즘] 백준 1956번: 운동 (C++)

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

1956번: 운동

사이클 최소 비용 경로 길이를 찾는 문제다.

플로이드 와샬을 사용하면 풀린다.

풀리는 이유는 플로이드 와샬을 이용하면 자기 자신을 향한 최소 비용 경로도 무조건 다른 노드를 거쳐서 할당되기 때문에 가능하다. 

(물론 최소 비용 경로를 묻는 문제에서는 자기 자신을 향한 경로는 플로이드 와샬이 끝나고 0을 할당해줘야 함)

>> 플로이드 와샬의 특성을 이용하는 문제였다.

#include <iostream>
#include <cmath>
#define MAX 500 + 1
#define INF 987654321
using namespace std;

int graph[MAX][MAX];
int cache[MAX][MAX];
int n, m;

void floydWarshall() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cache[i][j] = graph[i][j];
		}
	}

	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (cache[i][k] != INF && cache[k][j] != INF) {
					cache[i][j] = min(cache[i][j], cache[i][k] + cache[k][j]);
				}
			}
		}
	}
}

int main() {
	cin >> n >> m;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			graph[i][j] = INF;
		}
	}

	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		graph[a][b] = c;
	}

	floydWarshall();

	int minValue = INF;
	for (int i = 1; i <= n; i++) {
		minValue = min(minValue, cache[i][i]);
	}

	if (minValue == INF) cout << -1;
	else cout << minValue;

	return 0;
}