Problem:
 Score : 500 points    Problem Statement In Takahashi Kingdom, which once existed, there are N cities, and some pairs of cities are connected bidirectionally by roads.
The following are known about the road network:   People traveled between cities only through roads. It was possible to reach any city from any other city, via intermediate cities if necessary.  Different roads may have had different lengths, but all the lengths were positive integers.   Snuke the archeologist found a table with N rows and N columns, A , in the ruin of Takahashi Kingdom.
He thought that it represented the shortest distances between the cities along the roads in the kingdom.  Determine whether there exists a road network such that for each u and v , the integer A_{u, v} at the u -th row and v -th column of A is equal to the length of the shortest path from City u to City v .
If such a network exist, find the shortest possible total length of the roads.      Constraints  1 \leq N \leq 300  If i ≠ j , 1 \leq A_{i, j} = A_{j, i} \leq 10^9 .  A_{i, i} = 0         Inputs Input is given from Standard Input in the following format:  N  A_{1, 1}  A_{1, 2}  ...  A_{1, N}  A_{2, 1}  A_{2, 2}  ...  A_{2, N}  ...  A_{N, 1}  A_{N, 2}  ...  A_{N, N}       Outputs If there exists no network that satisfies the condition, print -1 .
If it exists, print the shortest possible total length of the roads.        Sample Input 1 3
0 1 3
1 0 2
3 2 0      Sample Output 1 3  The network below satisfies the condition:   City 1 and City 2 is connected by a road of length 1 .  City 2 and City 3 is connected by a road of length 2 .  City 3 and City 1 is not connected by a road.        Sample Input 2 3
0 1 3
1 0 1
3 1 0      Sample Output 2 -1  As there is a path of length 1 from City 1 to City 2 and City 2 to City 3 , there is a path of length 2 from City 1 to City 3 .
However, according to the table, the shortest distance between City 1 and City 3 must be 3 .  Thus, we conclude that there exists no network that satisfies the condition.       Sample Input 3 5
0 21 18 11 28
21 0 13 10 26
18 13 0 23 13
11 10 23 0 17
28 26 13 17 0      Sample Output 3 82       Sample Input 4 3
0 1000000000 1000000000
1000000000 0 1000000000
1000000000 1000000000 0      Sample Output 4 3000000000

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    N = int(readline())
    G = [list(map(int, readline().split())) for _ in range(N)]

    H = [[True] * N for _ in range(N)]
    for k in range(N):
        for i in range(N):
            for j in range(i + 1, N):
                if G[i][j] > G[i][k] + G[k][j]:
                    print(-1)
                    return
                if k not in (i, j) and G[i][j] == G[i][k] + G[k][j]:
                    H[i][j] = False

    ans = 0
    for i in range(N):
        for j in range(i + 1, N):
            if H[i][j]:
                ans += G[i][j]

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
n=int(input())
a=[list(map(int,input().split()))for _ in range(n)]
b=[[j for j in i]for i in a]
c=[n*[1]for _ in range(n)]
for k in range(n):
  for i in range(n):
    for j in range(n):
      b[i][j]=min(b[i][j],b[i][k]+b[k][j])
      if a[i][j]==a[i][k]+a[k][j]:
        if i!=j and i!=k and j!=k:
          c[i][j]=0
if a!=b:exit(print(-1))
ans=0
for i in range(n):
  for j in range(i):
    if c[i][j]:ans+=a[i][j]
print(ans)

Solution (Python):
import sys
readline = sys.stdin.readline

N = int(readline())

A = [None] * N
for i in range(N):
  A[i] = list(map(int,readline().split()))
  






import copy
newA = copy.deepcopy(A)

for k in range(N):
  for i in range(N):
    for j in range(N):
      if i == k or k == j or i == j:
        continue
      if A[i][k] + A[k][j] < A[i][j]:
        print(-1)
        exit(0)
      elif A[i][k] + A[k][j] == A[i][j]:
        
        newA[i][j] = 0

ans = 0
for a in newA:
  ans += sum(a)
print(ans // 2)

Solution (Python):
import sys


def main():
    N = int(input())
    A = [list(map(int, input().split())) for i in range(N)]
    ans = 0
    for i in range(N):
        for j in range(i+1, N):
            dij = A[i][j]
            res = True
            for k in range(N):
                if k in [i, j]:
                    continue
                dikj = A[i][k] + A[k][j]
                if dij > dikj:
                    print(-1)
                    sys.exit()
                elif dij == dikj:
                    res = False
            if res:
                ans += dij
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from heapq import heappop, heappush
input = sys.stdin.readline

def main():
    n = int(input())
    a = [list(map(int,input().split())) for _ in range(n)]
    g = [[] for _ in range(n)]
    for i in range(n-1):
        for j in range(i+1,n):
            g[i].append((j,a[i][j]))
            g[j].append((i,a[i][j]))
    ans = 0
    for i in range(n):
        ans += sum(a[i])
    ans //= 2
    w = []
    for i in range(n):
        que = []
        d = [10**15 for _ in range(n)]
        d[i] = 0
        heappush( que,(0,i) )
        while que:
            p =  heappop(que)
            v = p[1]
            if d[v] < p[0]:
                continue
            for k in range(len(g[v])):
                edge = g[v][k]
                if d[edge[0]] > d[v] + edge[1]:
                    d[edge[0]] = d[v] + edge[1]
                    heappush( que,(d[edge[0]] , edge[0]) )
        w.append(d)
    for i in range(n-1):
        for j in range(i+1,n):
            if w[i][j] < a[i][j]:
                print(-1)
                return
            flag = 0
            for k in range(n):
                if i == k or j == k:
                    continue
                if w[i][k] + w[k][j] == w[i][j]:
                    flag = 1
            if flag:
                ans -= w[i][j]
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 998244353

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def main():
    N = int(input())
    A = read_lists(N)
    
    res = 0
    for i in range(N):
        for j in range(i + 1, N):
            if i == j:
                continue

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

                if A[i][j] == A[i][k] + A[k][j]:
                    break

                if A[i][j] > A[i][k] + A[k][j]:
                    print(-1)
                    return
            else:
                res += A[i][j]
    
    print(res)


if __name__ == "__main__":
    main()

Solution (Python):
import copy
N = int(input())
A = [list(map(int, input().split())) for i in range(N)]
B = A

def warshall_floyd(d):
    
    ans = 0
    for k in range(N):
        for i in range(N):
            for j in range(N):
               
               
               
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d











B = copy.deepcopy(A)
cost = warshall_floyd(B)


ans = 0
for i in range(N):
  for j in range(N):
    if cost[i][j] < A[i][j]:
      print("-1")
      quit()

for i in range(N):
  cost[i][i] = 10 ** 18
for i in range(N):
  for j in range(N):
    p = 1
    for k in range(N):
      if cost[i][j] >= cost[i][k] + cost[k][j]:
        p = 0
        break
    if p == 1:
      ans += cost[i][j]


ans = ans / 2



print(int(ans))

Solution (Python):
import copy
from itertools import product, combinations

N = int(input())

dp = []
for _ in range(N):
    dp.append(list(map(int, input().split(' '))))

original = copy.deepcopy(dp)

for k, i, j in product(range(N), repeat=3):
    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])

if dp == original:
    cost = 0
    for i in range(N):
        for j in range(i + 1, N):
            for k in range(N):
                if k == i or k == j:
                    continue
                if dp[i][j] == dp[i][k] + dp[k][j]:
                    break
            else:
                cost += dp[i][j]
    print(cost)
else:
    print(-1)

Solution (Python):
n=int(input())
a=[]
for _ in range(n):
	a.append(list(map(int,input().split())))
from copy import deepcopy
b=deepcopy(a)
for i in range(n):
	for j in range(n):
		for k in range(n):
			b[j][k]=min(b[j][i]+b[i][k],b[j][k])
if a!=b:
	print(-1)
	exit()
ans=0
for i in range(n):
	b[i][i]=10**18
for i in range(n):
	for j in range(n):
		f=1
		for k in range(n):
			if b[i][j]>=b[i][k]+b[k][j]:
				f=0
				break
		if f:
			ans+=b[i][j]
print(ans//2)

Solution (Python):
import sys
input = sys.stdin.readline

def main():
    n = int(input())
    a = [list(map(int, input().split())) for _ in range(n)]
    

    for k in range(n-1,-1,-1):
        for i in range(n-1,-1,-1):
            for j in range(n-1,-1,-1):            
                
                if (i==j or k==i or k==j):
                    continue
                if (a[i][k]!=-1 and a[k][j]!=-1 and a[i][j] == a[i][k]+a[k][j]):
                    a[i][j] = -1
                elif (a[i][k]!=-1 and a[k][j]!=-1 and a[i][j] > a[i][k]+a[k][j]):
                    print(-1)
                    exit()
            
    

    ans = 0
    for i in range(0,n-1):
        for j in range(i,n):
            if (a[i][j]!=-1):
                ans += a[i][j]
    print(ans)
    
if __name__=="__main__":
    main()

Solution (Python):
N = int(input())
A = [list(map(int, input().split())) for i in range(N)]

ans = 0
for i in range(N):
  for j in range(i+1, N):
    dij = A[i][j]
    res = True
    for k in range(N):
      if k in [i, j]:
        continue
      dikj = A[i][k] + A[k][j]
      if dij > dikj:
        print(-1)
        quit()
      elif dij == dikj:
        res = False
    if res:
      ans += dij

print(ans)

Solution (Python):
N=int(input())
A=[list(map(int,input().split())) for i in range(N)]

ans = 0
for i in range(N):
    for j in range(i + 1, N):
        ok = True
        for k in range(N):
            if i == k or j == k:
                continue
            if A[i][j] > A[i][k] + A[k][j]:
                print(-1)
                exit(0)
            elif A[i][j] == A[i][k] + A[k][j]:
                ok = False
        if ok:
            ans += A[i][j]

print(ans)

Solution (Python):


import sys














from copy import copy, deepcopy              















def main():
    mod = 1000000007                
    inf = float('inf')              
    
    sys.setrecursionlimit(10**6)    
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())


    def warshall_floyd(adj_mat_with_weight):
        '''
        Warshall-Floyd 法 (O(V^3), 1 sec だと v~500 とかが限界)
        全点対間の最短経路を三次元 DP で求める
            - 定式化
            - dp[k+1][i][j] を 0...k, i, j なる頂点を使用できる時の i~j 最短距離とする (k+1=0 の時は e(i,j))
            - dp[k+1][i][j] = min(dp[k][i][j], dp[k][i][k+1]+dp[k][k+1][j])
            - 最後に必要なのは dp[V][i][j] 。上の漸化式をみるに 2 次元 array があれば使いまわしてメモリ節約できる。
        Args:
            adj_mat_with_weight (list): 重みを記録した隣接行列 (非接続頂点は inf)
        Returns:
            dp (list): dp[i][j] を見れば全頂点を使用可能な時の i j 最短距離がわかる。最後に dp[i][i] が負になっていたら負サイクルが存在するということ
        '''
        V = len(adj_mat_with_weight)
        
        dp = deepcopy(adj_mat_with_weight)
        for i in range(V):
            dp[i][i] = 0
        
        for k in range(1, V+1):
            for i in range(V):
                for j in range(V):
                    
                    dp[i][j] = min(dp[i][j], dp[i][k-1]+dp[k-1][j])
        return dp

    def check_possible_structure(dp, adj_mat):
        n = len(adj_mat)
        for i in range(n):
            for j in range(i+1, n):
                if dp[i][j] < adj_mat[i][j]:
                    return False
        return True

    def calc_minimum_street(dp, adj_mat):
        n = len(adj_mat)
        total_dist = 0
        for i in range(n):
            for j in range(i+1, n):
                total_dist += adj_mat[i][j]
        
        for i in range(n):
            for j in range(i+1, n):
                
                dist = adj_mat[i][j]
                for k in range(n):
                    if k != i and k != j and dp[i][k] + dp[k][j] == dist:
                        total_dist -= dist
                        break
        return total_dist
    
    
    n = ii()
    adj_mat = [lmi() for _ in range(n)]
    dp = warshall_floyd(adj_mat)

    if not check_possible_structure(dp, adj_mat):
        print(-1)
    else:
        print(calc_minimum_street(dp, adj_mat))


if __name__ == "__main__":
    main()

Solution (Python):
import itertools
import numpy as np
from scipy.sparse.csgraph import floyd_warshall


def main():
    N = int(input())
    matr = np.array([tuple(map(int, input().split())) for _ in range(N)], dtype=np.int64)
    way = floyd_warshall(matr).astype(int)
    if np.any(way < matr):
        print(-1)
        exit()

    ans = 0
    for a, b in itertools.combinations(range(N), 2):
        eq = (matr[a, b] == (matr[a] + matr[:, b]))
        eq[a] = eq[b] = False
        if not np.any(eq):
            ans += matr[a, b]
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
N = int(input())
INF = 10**12
A = []

for i in range(N):
    tmp = list(map(int,input().split()))
    A.append(tmp)

def check():
    c = [[0]*N for i in range(N)]
    ans = 0
    for i in range(N):
        for j in range(N):
            flag = True
            for k in range(N):    
                if k == i or k == j:
                    continue
                if A[i][j] == A[i][k] + A[k][j]:
                    flag = False
                    break
                elif A[i][j] > A[i][k] + A[k][j]:
                    return -1
            if flag:
                c[i][j] = A[i][j]
    for i in range(N):
        ans += sum(c[i])
    return ans // 2

print(check())

Solution (Python):
from scipy.sparse.csgraph import floyd_warshall
import numpy as np


def main():
    INF = 10**12
    N = int(input())
    A = [list(map(int, input().split(' '))) for _ in range(N)]
    wf = floyd_warshall(A)
    for i in range(N):
        A[i][i] = INF
        wf[i][i] = INF
    ans = 0
    for i in range(N):
        for j in range(N):
            if A[i][j] != wf[i][j]:
                print(-1)
                return
            if wf[i][j] < np.min(wf[i] + wf[j]):
                ans += wf[i][j]
    print(int(ans // 2))


if __name__ == '__main__':
    main()

Solution (Python):


def main():
    N = int(input())
    A = [None for _ in range(N)]
    INF = 10**12
    for i in range(N):
        A[i] = list(map(int, input().split()))

    adj = [[0]*N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            flag = True
            for k in range(N):
                if k == i or k == j:
                    continue
                if A[i][j] > A[i][k] + A[k][j]:
                    print(-1)
                    exit()
                elif A[i][j] == A[i][k] + A[k][j]:
                    flag = False
                    break
            if flag:
                adj[i][j] = A[i][j]
    ans = 0
    for i in range(N):
        ans += sum(adj[i])
    print(ans//2)

if __name__ == "__main__":
    main()

Solution (Python):
import copy
N = int(input())

graph = []
for i in range(N):
  graph.append( list(map(int,input().split())) )

dp = copy.deepcopy(graph)
for k in range(N):
  for i in range(N):
    for j in range(N):
      dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j])

res = 0

for i in range(N):
  for j in range(N):
    if dp[i][j] < graph[i][j]:
      print(-1)
      exit()
    elif dp[i][j] == graph[i][j]:
      flg = True
      for k in range(N):
        if k!=i and k!=j and dp[i][j] == dp[i][k]+dp[k][j]:
          flg = False
      if flg:
        res += dp[i][j]

print(res//2)

Solution (Python):







N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]

for k in range(N):
    for i in range(N):
        for j in range(N):
            
            if A[i][j] > A[i][k] + A[k][j]:
                print(-1)
                exit()


"""
存在する道路の長さの和が最小となるようなもの
→ Aについて、i<->jを結ぶ最短の辺（間に他のノードがない辺）だけ足し合わせる
"""
ans = 0
for i in range(N):
    for j in range(i+1, N):
        has_other_edges = False
        for k in range(N):
            if i == k or j == k: continue
            if A[i][j] == A[i][k] + A[k][j]:
                has_other_edges = True

        if not has_other_edges:
            ans += A[i][j]



print(ans)

Solution (Python):
def main():
    N = int(input())
    dist = [list(map(int, input().split())) for _ in range(N)]

    update = False
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if not (dist[i][k] and dist[k][j]): continue  
                d = dist[i][k] + dist[k][j]
                if dist[i][j] > d:
                    dist[i][j] = d
                    update = True

    if update:
        print(-1)
        return

    ans = 0
    for j in range(N):
        for i in range(j):
            for k in range(N):
                if not (dist[i][k] and dist[k][j]): continue  
                d = dist[i][k] + dist[k][j]
                if d == dist[i][j]: break  
            else:
                ans += dist[i][j]
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import heapq
import sys
N = int(input())

r = [[1]*N for _ in range(N)]
g = [[]*N for _ in range(N)]
all = 0
for i in range(N):
  temp = list(map(int,(input().split())))
  g[i] = temp
  all += sum(temp)


for k in range(N):
  for i in range(N):
    for j in range(N):
      if g[i][j] > g[i][k] + g[k][j]:
        print("-1")
        sys.exit()
      elif g[i][j] == g[i][k] + g[k][j] and i != j and j != k and k != i:
        r[i][j] = 0
ans = 0
for i in range(N):
  for j in range(N):
    ans += g[i][j]*r[i][j]

ans = ans//2
print(ans)

Solution (Python):
import copy

N = int(input())
A = []
for i in range(N):
    A.append(list(map(int, input().split())))

B = copy.deepcopy(A)
for i in range(N):
    for j in range(i, N):
        for k in range(N):
            if not (i != j and j != k and k != i):
                continue
            if A[i][j] > A[i][k] + A[k][j]:
                print(-1)
                exit()
            if A[i][j] == A[i][k] + A[k][j]:
                B[i][j] = 0

ans = 0
for i in range(N):
    for j in range(i, N):
        ans += B[i][j]

print(ans)

Solution (Python):
import copy

N = int(input())
A = []
for i in range(N):
    A.append(list(map(int, input().split())))

B = copy.deepcopy(A)
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        for k in range(N):
            if j == k:
                continue
            if k == i:
                continue
            if A[i][j] > A[i][k] + A[k][j]:
                print(-1)
                exit()
            if A[i][j] == A[i][k] + A[k][j]:
                B[i][j] = 0

ans = 0
for i in range(N):
    for j in range(i, N):
        ans += B[i][j]

print(ans)

Solution (Python):

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")



def main():
    n = int(input())
    d = [None]*n

    for i in range(n):
        d[i] = list(map(int, input().split()))
    ans = 0
    for i in range(n):
        for j in range(i+1, n):
            for k in range(n):
                if k in (i,j):
                    continue
                if (d[i][j]>d[i][k]+d[j][k]) or (d[i][k]>d[i][j]+d[j][k]) or (d[k][j]>d[i][k]+d[j][i]):
                    print(-1)
                    return
                if d[i][j]==d[i][k]+d[j][k]:
                    break
            else:
                ans += d[i][j]
    print(ans)
main()

Solution (Python):
n = int(input())
A = [list(map(int, input().split())) for _ in range(n)]
B = [[1] * n for _ in range(n)]

for k in range(n):
    for i in range(n):
        for j in range(n):
            if k != i and k != j:
                if A[i][j] > A[i][k] + A[k][j]:
                    print(-1)
                    exit()
                elif A[i][j] == A[i][k] + A[k][j]:
                    B[i][j] = 0

ans = 0
for i in range(n):
    for j in range(i):
        if B[i][j]:
            ans += A[i][j]

print(ans)

Solution (Python):
import numpy as np

N = int(input())
A = np.array([input().split() for _ in range(N)], dtype=np.int64).reshape(N,N)

INF = 10**15
np.fill_diagonal(A, INF)

ans = 0
for i in range(N-1):
    for j in range(i+1,N):
        detour = np.min(A[i]+A[j])
        if detour > A[i][j]:
            ans+=A[i][j]
        elif detour < A[i][j]:
            print(-1)
            exit()
print(ans)

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n = inp()
a = [inpl() for _ in range(n)]
res = 0
fin = set()
for k in range(n):
    for i in range(n):
        for j in range(n):
            d = a[i][k] + a[k][j]
            if a[i][j] > d:
                print(-1)
                quit()
            if a[i][j] == d and i != k and j != k:
                fin.add((i,j))

for i in range(n):
    for j in range(i+1,n):
        if (i,j) in fin: continue
        res += a[i][j]
print(res)

Solution (Python):

def warshall_floyd(cost):
    ret = [[1]*N for _ in [0]*N]
    for k in range(N):
        for i, c_left in enumerate(cost[i][k] for i in range(N)):
            for j, (c_now, c_right) in enumerate(zip(cost[i], cost[k])):
                if c_left + c_right < c_now:
                    print(-1)
                    exit()
                if i == j or j == k or k == i:
                    continue
                if c_left + c_right == c_now:
                    ret[i][j] = ret[j][i] = 0
    return ret


INF = 10**10
N, *A = map(int, open(0).read().split())
*A, = zip(*[iter(A)]*N)


E = []
for i in range(N):
    for j in range(i+1, N):
        E.append((A[i][j], i, j))
E.sort()

road = warshall_floyd(A)
ans = 0
for cost, i, j in E:
    if not road[i][j]:
        continue
    ans += cost

print(ans)

Solution (Python):
def solve():
    N = int(input())
    d = [[float('inf')]*N for _ in range(N)]
    A = [list(map(int, input().split())) for _ in range(N)]
    for i in range(N):
        for j in range(N):
            d[i][j] = A[i][j]

    
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j] = min(d[i][j], d[i][k]+d[k][j])

    for i in range(N):
        for j in range(N):
            if d[i][j] < A[i][j]:
                return -1
    ans = 0
    for i in range(N):
        for j in range(i+1,N):
            ans += A[i][j]
            for k in range(N):
                if k!= i and k!=j and A[i][j]==A[i][k]+A[k][j]:
                    ans -= A[i][j]
                    break
    return ans
print(solve())

Solution (Python):
N = int(input())

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

def warshall_floyd(d):
    global SUM
    ans = 0
    aroad = set()
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if d[i][j]>d[i][k] + d[k][j]:
                    return -1
                if d[i][j]==d[i][k]+d[k][j] and not (i==k or k==j):
                    aroad.add((min(i, j), max(i, j)))
    for i, j in list(aroad):
        ans -= d[i][j]
    return SUM+ans

SUM = 0
for i in range(N):
    As = list(map(int, input().split()))
    SUM += sum(As)
    for j in range(N):
        d[i][j] = As[j] 
SUM //= 2
print(warshall_floyd(d))

Solution (Python):
N = int(input())

A = [list(map(int, input().split())) for _ in range(N)]

ans = sum(sum(a) for a in A) // 2
removeable = set()

for k in range(N):
    for i in range(N):
        for j in range(N):
            d = A[i][k] + A[k][j]
            if A[i][j] > d:
                print(-1)
                exit()
            if A[i][j] == d and i != k and j != k:
                removeable.add((i, j))

for i in range(N):
    for j in range(i + 1, N):
        if (i, j) in removeable:
            ans -= A[i][j]

print(ans)

Solution (Python):
n=int(input())
a=[list(map(int,input().split())) for _ in range(n)]

for k in range(n):
  for i in range(n):
    for j in range(n):
      if a[i][j]>a[i][k]+a[k][j]:
        print(-1)
        exit(0)

ans=0
for i in range(n):
  for j in range(i+1,n):
    ok=True
    for k in range(n):
      if i==k or j==k:
        continue
      if a[i][j]==a[i][k]+a[k][j]:
        ok=False
        break
    if ok:
        ans+=a[i][j]
print(ans)

Solution (Python):
import copy
n = int(input())

ans = 0
def warshall_floyd(d):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if i == k or j == k:
                    continue
                elif d[i][j] > d[i][k] + d[k][j]:
                    return -1
                elif d[i][j] == d[i][k] + d[k][j]:
                    blist[i][j] = 0
    return sum([sum(l) for l in blist])//2

alist = []
blist = []
for i in range(n):
    a = list(map(int,input().split()))
    alist.append(copy.copy(a))
    blist.append(copy.copy(a))


ans = warshall_floyd(alist)
print(ans)

Solution (Python):
n=int(input())
A=[]
for index in range(n):
    A.append(list(map(int,input().split())))

def warshall_floyd(G):
    h=len(G)

    res=0
    for x in range(h):
        for y in range(x+1,h):
            res+=G[x][y]

    check=[[0]*h for z in range(h)]
    for k in range(h):
        for i in range(h):
            for j in range(h):
                temp=G[i][k]+G[k][j]
                if temp==G[i][j]:
                   if i!=j and j!=k and k!=i:
                       check[i][j]=1
                elif temp<G[i][j]:
                    if i!=j and j!=k and k!=i:
                        check[i][j]=-1
    decrease=0             
    for p in range(h):
        for q in range(h):
            if check[p][q]==-1:
                return [False]
            elif check[p][q]==1:
                decrease+=G[p][q]
    else:
        return [True,res-decrease//2]


ans=warshall_floyd(A)
if not ans[0]:
    print(-1)
else:
    print(ans[1])

Solution (Python):
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)


def road():
    N = int(input())
    A = tuple(tuple(map(int, input().split())) for _ in range(N))

    res = 0
    for s in range(N - 1):
        for t in range(s + 1, N):
            
            dist = A[s][t]
            is_connect = True
            for m in range(N):
                if m in [s, t]:
                    continue
                d = A[s][m] + A[m][t]
                if d < dist:
                    return -1
                elif d == dist:
                    is_connect = False
            if is_connect:
                res += dist
    return res


if __name__ == "__main__":
    print(road())

Solution (Python):
n=int(input())

mat=[[0 for i in range(n)] for j in range(n)]
data=[[0 for i in range(n)] for j in range(n)]
for _ in range(n):
    x=list(map(int,input().split()))
    for j in range(n):
        mat[_][j]=x[j]
        data[_][j]=x[j]
def warshall_floyd(d):
    
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

newmat=warshall_floyd(mat)
if newmat==data:
    ans=0
    for i in range(n):
        for j in range(i+1,n):
            ans+=data[i][j]*int(all(data[i][j]<data[i][k]+data[k][j] for k in range(i))&all(data[i][j]<data[i][k]+data[k][j] for k in range(i+1,j))&all(data[i][j]<data[i][k]+data[k][j] for k in range(j+1,n)))     
    print(ans)      
else:
    print(-1)

Solution (Python):
from sys import stdin, setrecursionlimit

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


def main():
    N = int(input())
    A = [list(map(int, input().split())) for _ in range(N)]

    ans = 0
    for i in range(N):
        for j in range(i + 1, N):
            required = True
            for k in range(N):
                if k == i or k == j:
                    continue
                if A[i][j] > A[i][k] + A[k][j]:
                    print(-1)
                    return
                if A[i][j] == A[i][k] + A[k][j]:
                    required = False
                    break
            if required:
                ans += A[i][j]

    print(ans)

    return


if __name__ == '__main__':
    main()

Solution (Python):
from sys import stdin, setrecursionlimit

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


def main():
    N = int(input())
    A = [list(map(int, input().split())) for _ in range(N)]

    ans = 0
    for i in range(N):
        for j in range(i + 1, N):
            if any(A[i][j] > A[i][k] + A[k][j] for k in range(N) if k != i and k != j):
                print(-1)
                return
            if all(A[i][j] < A[i][k] + A[k][j] for k in range(N) if k != i and k != j):
                ans += A[i][j]

    print(ans)

    return


if __name__ == '__main__':
    main()

Solution (Python):
from sys import stdin, setrecursionlimit

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


def main():
    N = int(input())
    A = [list(map(int, input().split())) for _ in range(N)]

    ans = 0
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if A[i][j] > A[i][k] + A[k][j]:
                    print(-1)
                    return

    ans = 0
    for i in range(N):
        for j in range(i + 1, N):
            if all(A[i][j] < A[i][k] + A[k][j] for k in range(N) if k != i and k != j):
                ans += A[i][j]

    print(ans)

    return


if __name__ == '__main__':
    main()

Solution (Python):
import copy

def warshall_floyd(d,n):
    D = copy.deepcopy(d) 
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if i == k  or k == j:
                    continue
                if d[i][k] + d[k][j] < d[i][j]:
                    return -1 
                elif d[i][k] + d[k][j] == d[i][j]:
                    D[i][j] = 0
    ans = sum([sum(i) for i in D])
    assert not (ans % 2)
    return ans // 2
  
n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
ans = warshall_floyd(a,n)
print(ans)