[백준] 1507: 궁금한 민호

0. 문제 주소

 

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

1507번: 궁금한 민호

 

 

1. 풀이

 

플로이드 워셜 알고리즘을 이용해서

 

i번 도시에서 j번 도시로 가는 최단거리가, 중간에 k번 도시를 거쳐서 가는 거리보다 클 경우 불가능, 

 

같을 경우 i번 ~ j번을 직접적으로 잇는 도로는 필요가 없기 때문에 이를 저장해두고

 

순회가 끝나면 남은 도로들의 가중치만 더해주면 된다.

 

 

2. 풀이 코드

 

* 유의할 점

 

#include <bits/stdc++.h>

using namespace std;

int N;
int dist[22][22];
bool notused[22][22];

int main(){
	#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	#endif

	// ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	scanf("%d", &N);
	
	for (int i=0;i<N;i++){
		for (int j=0;j<N;j++){
			scanf("%d", &dist[i][j]);
		}
	}
	int ans = 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 || j==k || k==i) continue;
				if (dist[i][k] + dist[k][j] == dist[i][j]){
					notused[i][j]= true;
				}
				else if (dist[i][k] + dist[k][j] < dist[i][j]){
					printf("-1");
					return 0;
				}
			}
		}
	}
	
	for (int i=0;i<N;i++){
		for (int j=i;j<N;j++){
			if (!notused[i][j]) ans += dist[i][j];
		}
	}
	
	printf("%d\n", ans);
	
	return 0;
}