[백준/c++] 1956번 - 운동

[ 문제 ]

 

[ 구현 ]

플로이드 워셜을 통해서 자기 자신으로 돌아오는 사이클을 구할 수 있는 점을 이용하면 쉽게 풀 수 있다.

 

 

[ 코드 ]

 

#include <iostream>
#include <algorithm>

#define INF 987654321

using namespace std;

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

void floyd() {
	for (int k = 1; k <= v; k++) {
		for (int i = 1; i <= v; i++) {
			for (int j = 1; j <= v; j++) {
				graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);
			}
		}
	}
}

int main() {
	ios::sync_with_stdio();
	cin.tie(0);

	cin >> v >> e;
	
	for (int i = 1; i <= v; i++) {
		for (int j = 1; j <= v; j++) {
			graph[i][j] = INF;
		}
	}

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

	floyd();

	int ans = INF;
	
	for (int i = 1; i <= v; i++) {
		if (graph[i][i] != INF) {
			ans = min(ans, graph[i][i]);
		}
	}

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

	return 0;
}

 

 

 

[ 마무리 및 느낀 점 ]

 

처음에는 bfs나 다익스트라의 가능성도 열어두고 생각해보았으나 알고보니 플로이드 워셜로 쉽게 풀리는 문제였다.

알고리즘의 기본적인 동작구조를 잘 익히고 있다면 쉽게 응용이 가능하지만 그렇지 못하다면 조금 산으로 갈 수도 있을 듯하다.