1507 궁금한 민호

 
#include <stdio.h>
 
int arr[30][30] = { 0 };
int check[30][30] = { 0 };
 
int main() {
    int n;
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i != j)
                 check[i][j] = 1;
        }
    }
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                if (arr[j][k] > arr[j][i] + arr[i][k]) {
                    printf("-1");
                    return 0;
                }
                else if ((arr[j][k] == arr[j][i] + arr[i][k]) && i != j && i != k) {
                    check[j][k] = 0;
                }
            }
        }
    }
       
    int rst = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            if (check[i][j] == 1)
                rst += arr[i][j];
        }
    }
 
    printf("%d", rst);
}