[BOJ] 백준 1956번: 운동

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

1956번: 운동

 

경로가 주어지고 v ~-> v로 돌아올 수 있는 최소 경로를 구하는 문제입니다.

V가 400으로 플로이드 와샬 방법으로 모든 경로간 최소 경로를 구하고 그중 가장 작은 v ~-> v 비용을 출력하면 됩니다.

플로이드 와샬의 아이디어는 어떤 정점 i를 거쳐가는 모든 경로 v ~-> i -~> u를 완전탐색 O(n^3)로 구할 수 있습니다.

초기값을 입력 경로로 넣어주고 나머지는 꽤 큰값 (1e9)로 초기화한 뒤 3중 포문으로 구해 나가는 코드입니다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>
#include <queue>
#include <math.h>
#include <memory.h>
#include <set>
using namespace std;


int n, m;
int buf[401][401];
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			buf[i][j] = 1e9;
		}
	}
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		buf[a][b] = min(buf[a][b], c);
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			for (int k = 1; k <= n; k++) {
				buf[j][k] = min(buf[j][k], buf[j][i] + buf[i][k]);
			}
		}
	}
	int ans = 2e9;
	for (int i = 1; i <= n; i++) {
		ans = min(ans, buf[i][i]);
	}
	cout << (ans == 1e9 ? -1 :ans);
}