[백준] 1507 - 궁금한 민호

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

1507번: 궁금한 민호

 

최단 경로에 포함된 간선의 합을 구하는 문제이다.

 

맨 처음에 플로이드-와샬 알고리즘을 한 번 돌려본다.

이때 갱신되는 가중치가 생기면 미리 구해놓은 표는 맞지 않으므로 -1을 출력한다.

 

표가 맞다면, 모든 간선을 순회하며 각 간선의 가중치를 0으로 만들고 임시 배열로 플로이드-와샬 알고리즘을 수행한다.

이때 임시 배열의 가중치와 원래 배열의 가중치가 다르면 꼭 필요한 간선이 되므로, 답에 더한다.

 

#include <iostream>
using namespace std;

int n;
int map[20][20];
bool check() {
	int temp[20][20] = { 0, };

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			temp[i][j] = map[i][j];
		}
	}

	for (int k = 0; k < n; k++) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {

				if (i == j)continue;
				if (map[i][k] && map[k][j]) {
					if (temp[i][j] == 0 || temp[i][j] > map[i][k] + map[k][j]) {
						temp[i][j] = map[i][k] + map[k][j];
					}
				}
			}
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (map[i][j] != temp[i][j])return false;
		}
	}
	return true;
}
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
		}
	}
	if (check()) {
		int ans = 0;
		for (int i1 = 0; i1 < n; i1++) {
			for (int j1 = i1 + 1; j1 < n; j1++) {
				int num = map[i1][j1];
				int temp[20][20] = { 0, };
				map[i1][j1] = 0;

				for (int k = 0; k < n; k++) {
					for (int i = 0; i < n; i++) {
						for (int j = 0; j < n; j++) {

							if (i == j)continue;
							if (map[i][k] && map[k][j]) {
								if (temp[i][j] == 0 || temp[i][j] > map[i][k] + map[k][j]) {
									temp[i][j] = map[i][k] + map[k][j];
								}
							}
						}
					}
				}
				if (temp[i1][j1] != num) ans += num;
				map[i1][j1] = num;
			}
		}
		cout << ans;
	}
	else cout << -1;
}