BOJ - 1507 - 궁금한 민호

import sys

def solution():
    N = int(input())
    arr = []
    for _ in range(N):
        arr.append(list(map(int, sys.stdin.readline().split())))

    ret = [[0] * N for _ in range(N)]

    for k in range(N):
        for i in range(N):
            for j in range(N):
                if i == j or j == k or i == k:
                    continue

                if arr[i][j] == arr[i][k] + arr[k][j]:
                    ret[i][j] = 1
                elif arr[i][j] > arr[i][k] + arr[k][j]:
                    print(-1)
                    return

    sum = 0
    for i in range(N):
        for j in range(N):
            if not ret[i][j]:
                sum += arr[i][j]
    print(sum // 2)
    
solution()

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