[백준] 1507 궁금한 민호 c++

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

1507번: 궁금한 민호

 

풀이과정

예제 입력으로 플로이드 와샬 알고리즘을 수행한 시간이 입력된다.  
그럼에도 불구하고, 플로이드 와샬을 할 때 어느 도시를 거치는 게 더 짧다면  
최소 이동시간이 아니므로 이는 불가능한 경우에 해당되며 -1을 출력한다.
i에서 j로 가는 경로가 k로 거쳐가는 경우와 같다면  
모든 경로를 최소의 도로로 커버해야 하므로 k를 거쳐가는 도로를 선택한다.

 

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

int N, M, result;
int num[21][21];
int res[21][21];

void floyd() {
	for (int k = 1; k <= N; k++) {
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				// 거쳐가는 도시가 출발도시거나 도착도시일 경우
				if (k == i || k == j) continue;
				// 최소 경로가 성립하지 않는 경우 종료
				if (num[i][j] > num[i][k] + num[k][j]) {
					result = -1;
					return;
				}
				// 바로 가는 경로 없애줌
				else if (num[i][j] == num[i][k] + num[k][j]) {
					res[i][j] = 0;
				}
			}
		}
	}
}

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

	cin >> N;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> num[i][j];
			res[i][j] = num[i][j];
		}
	}
	floyd();

	if (result != -1) {
		int sum = 0;
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				sum += res[i][j];
			}
		}
		// i -> j 시간과 j -> i 시간이 중복 계산되어 있으므로 2로 나눠준다.
		cout << sum / 2;
	}
	else cout << result;
}