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

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

1956번: 운동

1. 주의할 점

- 플로이드와샬 알고리즘에 대해 알고 있어야 한다

 

2. 구현

- Node, Edge의 수를 입력 받은 후, Arr[][]배열을 초기화한다

- 플로이드 와샬 알고리즘을 통해 Arr[i][j]를 갱신한다(i에서 j까지의 최단거리)

- Result 변수를 두어 i->j->i까지 거리를 비교하고, Result가 초기 설정값과 같다면 -1을 할당한다

 

#define MAX 9876543210
#include <iostream>
#include <algorithm>
using namespace std;
int node, edge, s, e, val;
long long arr[401][401];

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> node >> edge;
	for(int i=1;i<=node;i++)
		for (int j = 1; j <= node; j++) {
			if (i == j) arr[i][j] = 0;
			else arr[i][j] = MAX;
		}
	for (int i = 0; i < edge; i++) {
		cin >> s >> e >> val;
		arr[s][e] = val;
	}
	for (int k = 1; k <= node; k++) {
		for (int i = 1; i <= node; i++) {
			for (int j = 1; j <= node; j++) {
				arr[i][j] = min(arr[i][j], arr[i][k] + arr[k][j]);
			}
		}
	}
	long long result = MAX;
	for (int i = 1; i <= node; i++) 
		for (int j = 1; j <= node; j++) {
			if (i == j) continue;
			result = min(result, arr[i][j] + arr[j][i]);
		}	
	if (result == MAX) result = -1;
	cout << result;
	system("pause");
	return 0;
}