[백준] 1956-운동(C++)

문제링크: https://www.acmicpc.net/problem/1956

1956번: 운동

 

대표적인 플로이드 와샬 문제입니다.

플로이드 와샬에 대한 이해가 필요합니다. 

 

O(V^3) 만큼 반복하면서 모든 노드의 최단거리를 도출하고 결과값을 도출하는 문제입니다.

 

 

아래는 정답 코드입니다.

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
/*

주의점
1. 중복경로에 대한 예외처리
2. long long
*/

int v, e;
long long arr[401][401];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> v >> e;
	for (int i = 1; i <= v; i++)
		for (int j = 1; j <= v; j++) {
			if (i == j) arr[i][j] = 0;
			else arr[i][j] = 2000000000; 	
		}

	int a, b, c;
	for (int i = 0; i < e; i++) {
		cin >> a >> b >> c;
		if (arr[a][b] > c) //중복경로
			arr[a][b] = c;
	}

	//플로이드 와샬
	for (int k = 1; k <= v; k++)
		for (int i = 1; i <= v; i++)
			for (int j = 1; j <= v; j++)
				arr[i][j] = min(arr[i][j], arr[k][j] + arr[i][k]);

	long long result = 2000000000;

	for (int i = 1; i <= v; i++)
		for (int j = 1; j <= v; j++) {
			if (i == j) continue;
			result = min(result, arr[i][j] + arr[j][i]);
		}
	if (result == 2000000000)
		cout << -1 << endl;
	else
		cout << result << endl;
	return 0;
}