백준 1956 c++ "운동" -[PlusUltraCode]

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

1956번: 운동

 

[필자 사고]

처음에는 다익스트라 BFS 벨만포드까지 생각을 해봤다. 정작 이 문제의 해결해야 하는 플로이드 와샬알고리즘은 떠오르지 않았다.

 

자료를 찾아보니 플로이드 와샬 알고리즘을 사용한 후 사이클이 있는지 없는지 판단하는 법은 Arr[i][k]와 Arr[k][i] 값 둘이 있을 경우 사이클이 생성된것을 알 수 있다.

 

이 문제를 통해 플로이드 와샬에 개념을 확실히 적립할 수 있었다.

 

[소스 코드]

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <queue>
#include<cstring>
#include <string>
using namespace std;

int N, M;
vector<vector<int>> Arr;

void Input() {
	cin >> N >> M;
	Arr.resize(N + 1);
	for (int i = 0; i <= N; i++) {
		Arr[i].resize(N + 1,10000000);

	}

	for (int i = 0; i < M; i++) {
		int s, e, w;
		cin >> s >> e >> w;
		Arr[s][e] = w;
	}
	for (int i = 0; i <= N; i++) {
		Arr[i][i] = 0;
	}
}

void Floyd_Warshall() {
	for (int k = 1; k <= N; k++) {
		for (int s = 1; s <= N; s++) {
			for (int e = 1; e <= N; e++) {
				if (Arr[s][e] > Arr[s][k] + Arr[k][e]) {
					Arr[s][e] = Arr[s][k] + Arr[k][e];
				}
			}
		}
	}
}

int main(void) {
	Input();
	Floyd_Warshall();
	int result = 9999999;
	for (int i = 1; i <= N; i++) {
		for (int k = 1; k <= N; k++) {
			if (i == k)continue;
			result = min(result, Arr[i][k] + Arr[k][i]);
		}
	}
	if (result == 9999999)cout << -1;
	else cout << result;

}