1507 - 궁금한 민호

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

(연결된 정점을 x-x 로 표현하겠다)
i-j-k 가 가능한 i-k 가 있다면 i-k 인 간선은 필요가 없다. 왜냐하면 i-k 는 i-j, j-k 로 표현이 가능하고, 같은 거리로 더 많은 도시를 갈 수 있도록 유지되기 때문이다.
결과적으로 필요한 간선만 남게 된다.

불가능한 경우는 잘못된 입력이 주어지는 경우이다. 이를테면 주어진 입력으로 a->b->c 를 해보면 a->c 보다 더 작게 나온다던가 그런 입력.

#include <cstdio>
#include <cstring>

int main(){
    int i, j, k, n;
    int v[21][21]={};
    scanf("%d", &n);
    
    for(i=0; i<n; ++i){
        for(j=0; j<n; ++j)
            scanf("%d", &v[i][j]);
    }
    
    bool destroy[21][21]={};
    for(k=0; k<n; ++k){
        for(i=0; i<n; ++i){
            for(j=0; j<n; ++j){
                if(v[i][k]+v[k][j] < v[i][j]){
                    return puts("-1"), 0;
                }
                
                if(i==j || j==k || i==k) continue;
                if(v[i][k]+v[k][j] == v[i][j]){
                    destroy[i][j] = true;
                }
            }
        }
    }
    
    int ans = 0;
    for(i=0; i<n; ++i){
        for(j=i; j<n; ++j){
            if(!destroy[i][j]) ans += v[i][j];
        }
    }
    printf("%d", ans);
    
    return 0;
}