백준 1507 : 궁금한 민호 C++

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

1507번: 궁금한 민호

 

※ 플로이드 와샬 활용 간단 정리

-> 모든 노드끼리의 가능한 최단거리를 구하는 것임.

 

1) 현재 노드들 사이에 연결된 다리들을 이용해 노드간 거리 초기화

 

2) 기본적으로 노드를 3개 찝어서 활용

시작노드, 도착노드, 거쳐갈 노드

 

3) min( 시작노드 -> 도착노드, 시작노드 ->거쳐갈 노드 + 거쳐갈노드 -> 도착노드)

 

풀이

1. 이놈은 이미 플로이드 와샬이  적용되어 있다

-> 우리가 구해야될건 이놈들의 다리갯수를 최소화 할 수 있는지??

 

2. 현재 주어진거 말고 다른 최단경로가 있으면 잘못된거니 -1 출력

 

3. 다른곳으로 돌아가는거랑 지금 최단 거리랑 똑같으면 직접 연결된 다리는 불필요

 

 

#include <iostream>
using namespace std;

int n;
int input_arr[21][21];
int answer_arr[21][21];
// 만약 출발지 -> 목적지 현재 최단길이기
// 다른데를 거쳐가는데보다 느리다?
// 직접 연결된 다리가 없고 돌아가는 길이 최단이라는겨

int main()
{
	int sum = 0;
	cin >> n;
	for(int i=0;i<n;i++)
		for (int j = 0; j < n; j++)
		{
			cin >> input_arr[i][j];
			answer_arr[i][j] = input_arr[i][j];
		}

	//a 중간
	// b 시작 c 도착
	for (int a = 0; a < n; a++)
	{
		for (int b = 0; b < n; b++)
		{
			for (int c = 0; c < n; c++)
			{
				if ((b == a) || (c == a))
					continue;
				if (input_arr[b][c] > input_arr[b][a] + input_arr[a][c])
				{
					cout << -1 << endl;
					return 0;
				}

				if (input_arr[b][c] == input_arr[b][a] + input_arr[a][c])
					answer_arr[b][c] = 0;

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

	cout << sum / 2 << endl;

	return 0;
}