백준 1507 궁금한 민호 | 플로이드-워셜 | C++

 

 

 

이번 포스팅은 백준 1507번 궁금한 민호입니다.

아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다.

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

1507번: 궁금한 민호

 

 

 

기본 알고리즘

플로이드-워셜 알고리즘 Floyd-Warshall Algorithm

 

 

 

전체 코드

 

//백준1507 궁금한 민호
#include <iostream>
using namespace std;
 
const int MAX = 21;
const int INF = 9999999;
int N;
int map[MAX][MAX];
bool road[MAX][MAX];
bool isImpossible; //불가능한 경우
 
void reverse_floyd() {
    for (int k = 1; k <= N; k++) {
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (k == i || i == j || j == k) //서로 다른 두 도시의 경우에서만
                    continue;
                
                if (map[i][j] > map[i][k] + map[k][j]) {
                    //플로이드 알고리즘의 결과가 아님
                    //i-j시간이 최소가 아님, k 거쳐가면 시간이 단축되는 경우 존재
                    isImpossible = true;
                    return;
                }
                else if (map[i][j] == map[i][k] + map[k][j]) {
                    road[i][j] = false; //direct 경로가 아니면 i-j연결도로 삭제
                }
            }
        }
    }
}
 
int main() {
    cin >> N;
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            road[i][j] = true; //모든 도시는 연결되어 있음
        }
    }
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> map[i][j];
        }
    }
 
    reverse_floyd();
 
    int ans = 0; //모든 도로의 시간의 합
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (road[i][j] == true) { //i-j direct도로가 있으면
                ans += map[i][j];
            }
        }
    }
    ans /= 2; //i-j 시간과 j-i 시간이 중복 계산되어있으므로 2로 나눠줌
    
    if (isImpossible)
        cout << -1;
    else
        cout << ans;
 
    return 0;
}