[백준] 1507번 궁금한 민호

[적용한 알고리즘]

플로이드 와샬

 

[아이디어]

i -> j 로 가는 경로가 있다고 가정해보자.

이때, i -> k -> j 가 가능하다면, i -> j 는 선택하면 안된다.

구하는 값이 간선의 개수를 최소화하는 것이기 때문이다.

따라서, 플로이드-와샬을 이용해서

dist[i][j] = dist[i][k] + dist[k][j] 를 만족하는 k 가 존재한다면,

그 간선을 사용하지 않으면 된다.

 

<코드>

#include <cstdio>
using namespace std;

int dist[21][21];
bool notUse[21][21];

int main(){
    int N;
    scanf("%d", &N);
    for (int i = 1; i <= N; i++){
        for (int j = 1; j <= N; j++){
            scanf("%d", &dist[i][j]);
        }
    }

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

                if (dist[i][j] == dist[i][k] + dist[k][j]){
                    notUse[i][j] = true;
                }

                if (dist[i][j] > dist[i][k] + dist[k][j]){
                    printf("-1\n");
                    return 0;
                }
            }
        }
    }

    int ans = 0;
    for (int i = 1; i <= N; i++){
        for (int j = 1; j <= N; j++){
            if (notUse[i][j]) continue;
            ans += dist[i][j];
        }
    }

    printf("%d\n", ans / 2);
    return 0;
}