[백준] 1956 운동 c++

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

1956번: 운동

 

풀이과정

사이클이 생기는 부분의 최소합을 구하면 되는 문제이다.  
i == j일 때는 continue 해주고, arr[i][j] + arr[j][i]일 때의 최솟값을 구하면 된다.  
만약 res가 INF일 경우는, 사이클이 되는 곳이 한 곳도 없으므로 -1을 출력해준다.

 

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

int V, E, a, b, c;
int arr[401][401];
const int INF = 1e9;

void floyd() {
	for (int k = 1; k <= V; k++) {
		for (int i = 1; i <= V; i++) {
			for (int j = 1; j <= V; j++) {
				if (arr[i][j] > arr[i][k] + arr[k][j]) {
					arr[i][j] = arr[i][k] + arr[k][j];
				}
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> V >> E;
  	// 플로이드 와샬 초기 설정
	for (int i = 1; i <= V; i++) {
		for (int j = 1; j <= V; j++) {
			if (i != j) arr[i][j] = INF;
		}
	}
	for (int i = 0; i < E; i++) {
		cin >> a >> b >> c;
		arr[a][b] = c;
	}
	floyd();

	int res = INF;
	for (int i = 1; i <= V; i++) {
		for (int j = 1; j <= V; j++) {
			if (i == j) continue;
			res = min(res, arr[i][j] + arr[j][i]);
		}
	}
	cout << (res == INF ? -1 : res);
}