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

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

1507번: 궁금한 민호

[필자 사고]

 

플로이드 와샬 알고리즘이 이미 적용된 상태로 입력값으로 들어온 문제다.

 

이 문제를 해결하려면 3가지 정도를 이해해야 된다.

 

1. s->e 가는 경로보다 s->k + k->e 경로의 합이 더 작을경우 문제가 생긴다.

 

그 이유는 이미 문제에서 입력값이 플로이드 와샬이 적용된 최단 거리만 주어지는데 저 식이 성립한다면 최단거리가 더 존재한다는 의미이다. 문제 자체가 모순이 되기 때문에 -1을 출력하고 종료시키면 된다.

 

2. s==k || k==e 일 경우 continue 시킨다. 

 

그 이유는 만약 s==k인 경우를 생각해보자. s->e 와  s->k+k->e 의 공식이 있을때 k가 s라고 하면

s->e vs s->s + s->e  인 식이 된다. 결국 s->e vs s->e의 관계가 되므로 의미가 없어진다.

 

3. 마지막으로 s->e 가는 경로보다 s->k + k->e 경로의 합이 같을경우 s->e경로를 지운다.

 

그 이유는 s->e의 경로의 시간과 s->k +k->e의 경로의 합의 시간이 같을 경우 s->e의 경로 한개를 살리는 것 보다
 s->k +k->e 이런식의 2가지 경로를 살리는게 훨씬 많은 지역을 연결할 수 있기 때문이다. 

 

이 부분만 잘 캐치해 놓으면 쉽게 문제를 해결할 수 있따. 지금 무방향 그래프이기 때문에 마지막 결과값을 2로 나눠주는건 잊지 말자.

 

[소스 코드]

 

#include <iostream>
#include <vector>

using namespace std;

int N;

vector<vector<int>> Arr;
vector<vector<int>> Arr2;

void Input() {
	cin >> N;
	Arr.resize(N);
	for (int i = 0; i < N; i++) {
		Arr[i].resize(N);
	}
	for (int i = 0; i < N; i++) {
		for (int k = 0; k < N; k++) {
			cin >> Arr[i][k];
		}
	}
	Arr2 = Arr;
}




int main(void) {
	Input();
	
	for (int k = 0; k < N; k++) {
		for (int s = 0; s < N; s++) {
			for (int e = 0; e < N; e++) {
				if (s == k || e == k)continue;
				if (Arr[s][e] > Arr[s][k] + Arr[k][e]) {
					cout << -1;
					return 0;
				}
				if (Arr[s][e] == Arr[s][k] + Arr[k][e]) {
					Arr2[s][e] = 0;
				}
			}
		}
	}
	

	int Result = 0;
	for (int i = 0; i < N; i++) {
		for (int k = 0; k < N; k++) {
			Result += Arr2[i][k];
		}
	}
	cout << Result / 2;
}