궁금한 민호

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

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	128 MB	5291	2771	2180	51.198%

문제

강호는 N개의 도시로 이루어진 나라에 살고 있다.

각 도시는 M개의 도로로 연결되어 있으며, 각 도로를 지날 때 필요한 시간이 존재한다. 

도로는 잘 연결되어 있기 때문에, 도시 A에서 B로 이동할 수 없는 경우는 존재하지 않는다.

도시 A에서 도시 B로 바로 갈 수 있는 도로가 있거나,

다른 도시를 거쳐서 갈 수 있을 때, 도시 A에서 B를 갈 수 있다고 한다.

강호는 모든 쌍의 도시에 대해서 최소 이동 시간을 구해놓았다.

민호는 이 표를 보고 원래 도로가 몇 개 있는지를 구해보려고 한다.

예를 들어, 예제의 경우에 모든 도시 사이에 강호가 구한 값을 가지는 도로가 존재한다고 해도 된다.

하지만, 이 도로의 개수는 최솟값이 아니다.

예를 들어, 도시 1-2, 2-3, 1-4, 3-4, 4-5, 3-5를 연결하는 도로만 있다고 가정해도, 강호가 구한 모든 쌍의 최솟값을 구할 수 있다.

이 경우 도로의 개수는 6개이고, 모든 도로의 시간의 합은 55이다.

모든 쌍의 도시 사이의 최소 이동 시간이 주어졌을 때,

이 나라에 존재할 수 있는 도로의 개수의 최솟값일 때, 모든 도로의 시간의 합을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 도시의 개수 N(1 ≤ N ≤ 20)이 주어진다.

둘째 줄부터 N개의 줄에 각각의 도시 사이에 이동하는데 필요한 시간이 주어진다.

A에서 B로 가는 시간과 B에서 A로 가는 시간은 같다. 또, A와 B가 같은 경우에는 0이 주어지고,

그 외의 경우에 필요한 시간은 2500보다 작거나 같은 자연수이다.

출력

첫째 줄에 도로 개수가 최소일 때, 모든 도로의 시간의 합을 출력한다.

불가능한 경우에는 -1을 출력한다.

예제 입력 1

5
0 6 15 2 6
6 0 9 8 12
15 9 0 16 18
2 8 16 0 4
6 12 18 4 0

예제 출력 1

55

예제 입력 2

3
0 2 2
2 0 2
2 2 0

예제 출력 2

6

예제 입력 3

8
0 1 6 17 26 13 7 16
1 0 5 16 25 12 7 15
6 5 0 21 21 8 12 11
17 16 21 0 41 28 23 31
26 25 21 41 0 13 32 10
13 12 8 28 13 0 19 3
7 7 12 23 32 19 0 22
16 15 11 31 10 3 22 0

예제 출력 3

69

예제 입력 4

3
0 1 3
1 0 1
3 1 0

예제 출력 4

-1

출처

• 문제를 번역한 사람: baekjoon
• 빠진 조건을 찾은 사람: medic_programmer

알고리즘 분류

• 그래프 이론
• 플로이드–워셜

---

접근 방법

i -> j로 가는 최단경로와 i -> k, k -> j 로 가는 최단경로의 합이 같다면 i -> j경로는 없애준다.

i -> j의 최단경로가 더 크다면 입력이 잘못된 것이므로 result를 -1로 저장해준다.

통과된 코드

#include <iostream>

using namespace std;

constexpr int MAX = 21;

int disArr[MAX][MAX];

int route[MAX][MAX];

int N, result;

int main()
{
	ios_base::sync_with_stdio(false); // scanf와 동기화를 비활성화
	// cin.tie(null); 코드는 cin과 cout의 묶음을 풀어줍니다.
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N;

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> disArr[i][j];
			route[i][j] = disArr[i][j];
		}
	}

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			for (int k = 1; k <= N; k++) {

				if (j == k || i == k) continue;

				// 불가능한 경우이므로 -1 출력
				if (disArr[i][j] > disArr[i][k] + disArr[k][j]) {
					cout << "-1";
					return 0;
				}

				// 경로를 지워준다.
				if (disArr[i][j] == disArr[i][k] + disArr[k][j]) route[i][j] = 0;
			}
		}
	}


	for (int i = 1; i <= N; i++) 
		for (int j = 1; j <= N; j++) result += route[i][j];
	
	// 반으로 나누어준다.
	cout << result / 2;

	return 0;
}