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):
N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
Map = [[] for _ in range(N)]
ans = 0
for i in range(N):
    for j in range(i+1, N):
        for k in range(N):
            if A[i][j] != A[j][i]:
                print(-1)
                exit()
            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]:
                break
        else:
            Map[i].append(j)
            Map[j].append(i)
            ans += A[i][j]
print(ans)

Solution (Python):
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))


def main():
    n = ii()

    a = []
    direct = [[True for i in range(n)]for j in range(n)]

    for i in range(n):
        a.append(li())


    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
                
                if i==k or k == j:
                    continue
                if a[i][j] == a[i][k] + a[k][j]:
                    direct[i][j] = False
    
    ans = 0
    for i in range(n):
        for j in range(n):
            if direct[i][j]:
                ans += a[i][j]
    print(ans//2)


main()

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

Solution (Python):
N = int(input())
from copy import copy,deepcopy
dist = [list(map(int,input().split())) for _ in range(N)]
dist2 = deepcopy(dist)
seen = [[False]*N for _ in range(N)]
for k in range(N):
    for i in range(N):
        for j in range(N):
            if (i!=k and k!=j) and dist[i][j]>=dist[i][k]+dist[k][j]:
                dist[i][j]= dist[i][k]+dist[k][j]
ans = 0
for i in range(N):
    for j in range(N):
        flag = True
        if i ==j: continue
        for k in range(N):
            if i==k or j ==k: continue
            if dist2[i][j]>dist[i][k]+dist[k][j]:
                print(-1);exit()
            if dist2[i][j]==dist[i][k]+dist[k][j]:
                flag = False
                break
        if flag:
            ans += dist[i][j]
print(ans//2)

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

for i in range(n):
    for j in range(n):
        if i == j:
            continue
        for k in range(n):
            if i == k or j == k:
                continue
            if a_s[i][j] > a_s[i][k] + a_s[j][k]:
                print(-1)
                exit()
            if a_s[i][j] == a_s[i][k] + a_s[j][k]:
                ans -= a_s[i][j]
                break

ans //= 2
print(ans)

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

f = True
for i in range(n):
    if not f: break
    for s in range(n):
        if not f: break
        for t in range(n):
            if a[s][t] > a[s][i] + a[i][t]:
                f = False
                break
            elif i == s or i == t: continue
            elif a[s][t] == a[s][i] + a[i][t]:
                is_neighbor[s][t] = False
if f:
    ans = 0
    for i in range(n):
        for j in range(n):
            if is_neighbor[i][j]:
                ans+=a[i][j]
    print(ans//2)
else:
    print(-1)

Solution (Python):
N = int(input())
costs = [list(map(int, input().split())) for _ in range(N)]
inf = float('inf')
dps = [[inf for _ in range(N)] for _ in range(N)]


for k in range(N):
    for i in range(N):
        for j in range(N):
            
            if costs[i][j] > costs[i][k] + costs[k][j]:
                print(-1)
                exit()
max_cost = 0


for i in range(N):
    for j in range(i + 1, N):
        flag = True
        for k in range(N):
            if k == i or k == j:
                continue
            if costs[i][j] == costs[i][k] + costs[k][j]:
                flag = False
                break
        if flag:
            max_cost += costs[i][j]
print(max_cost)

Solution (Python):
N=int(input())
A = [list(map(int, input().split())) for i in range(N)]
result=0
flag=True
isbreak=False
for m in range(N-1):
    for n in range(m+1,N):
        list_t=list(range(N))
        list_t.remove(m)
        list_t.remove(n)
        for t in list_t:
            if A[m][n]>A[m][t]+A[t][n]:
                result=-1                
                isbreak=True
                break
            elif A[m][n]==A[m][t]+A[t][n] and result!=-1:
                flag=False
                break
        if flag and result!=-1:
            result+=A[m][n]
        else:
            flag=True
        if isbreak:
            break
    if isbreak:
        break
print(result)

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

d = [[False]*n for _ in range(n)]

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

      if mat[i][j] == mat[i][k]+mat[k][j] and mat[i][k]>0 and mat[k][j]>0:
        d[i][j] = True

ans = 0
for i in range(n):
  for j in range(i+1, n):
    if not d[i][j]:
      ans += mat[i][j]

print(ans)

Solution (Python):
N=int(input())
A=[list(map(int,input().split())) for i 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()
INF=10**12
D=[[INF]*N for i in range(N)]
for i in range(N):
  D[i][i]=0
X=[]
for i in range(N):
  for j in range(N):
    if i==j:
      continue
    X.append([A[i][j],i,j])
P=0
X.sort()
for i in range(len(X)):
  for j in range(N):
    if X[i][0]==D[X[i][1]][j]+D[j][X[i][2]] and D[j][X[i][2]]!=0 and D[X[i][1]][j]!=0:
      break
    if j==N-1:
      P+=X[i][0]
  D[X[i][1]][X[i][2]]=X[i][0]
  D[X[i][2]][X[i][1]]=X[i][0]
print(P//2)

Solution (Python):
N = int(input())
A = [list(map(int,input().split())) for _ in range(N)]
B = [A[i][:] for i in range(N)]
C = [A[i][:] for i in range(N)]
for k in range(N):
    for i in range(N):
        for j in range(N):
            if k == i or k == j: continue
            if B[i][k]+B[k][j] <= B[i][j]:
                A[i][j] = -1
                B[i][j] = B[i][k]+B[k][j]

ans = 0
for i in range(N):
    for j in range(N):
        if B[i][j] != C[i][j]:
            print(-1)
            exit()
        if A[i][j] != -1:
            ans += A[i][j]
            A[i][j] = -1
            A[j][i] = -1
print(ans)

Solution (Python):




import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial,sqrt
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

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


n=I() 

d = [[float("inf")]*n for i in range(n)]
lis=[LI() for i in range(n)]

for i in range(n):
    for j in range(i+1,n):
        d[i][j]=lis[i][j]
        d[j][i]=lis[i][j]
for i in range(n):
    d[i][i] = 0 
warshall_floyd(d)
sm=0
for i in range(n):
    sm+=sum(lis[i])


count=0
for i in range(n-1):
    for j in range(i+1,n):
        if d[i][j]!=lis[i][j]:
            print(-1)
            sys.exit()
        if d[i][j]==lis[i][j]:
            for k in range(n):
                if i!=k!=j and d[i][k]+d[k][j]==d[i][j]:
                    count+=lis[i][j]
                    
                    break
print(sm//2-count)

Solution (Python):
n=int(input())
dis=[list(map(int,input().split())) for _ in range(n)]
c=[[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
  for j in range(n):
    c[i][j]=min(dis[i][k]+dis[k][j] for k in range(n))
for i in range(n):
  for j in range(n):
    if c[i][j]!=dis[i][j]:
      print(-1)
      exit()
for i in range(n):
  for j in range(n):
    for k in range(n):
      if i==k or j==k:continue
      if dis[i][j]==dis[i][k]+dis[k][j]:c[i][j]=0
print(sum(sum(c[i]) for i in range(n))//2)

Solution (Python):
import copy
import sys

INF = 2**120

n = int(input())
d = [[] for j in range(n)]
for j in range(n):
    d[j] = [int(i) for i in input().split()]

ans = sum([sum(d[i]) for i in range(n)])

minus = [[0] * n for i in range(n)]

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]:
                print('-1')
                sys.exit()
            if d[i][j] == d[i][k]+d[k][j] and i != k and j != k:
                minus[i][j] = 1

for i in range(n):
    for j in range(n):
        if minus[i][j]:
            ans -= d[i][j]

print(ans//2)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall

n = int(readline())
f = []
A = []
chk = []
for i in range(n):
  ar = list(map(int,readline().split()))
  f.append(ar)
  for j,ai in enumerate(ar):
    if i == j:
      continue
    A.append((i,j,ai))
  
INF = 10**9+1
g = [[INF] * n for _ in range(n)]
for a,b,c in A:
    g[a][b] = c
    g[b][a] = c

g = csr_matrix(g)
d = floyd_warshall(csgraph=g)

t = f == d
if t.all():
  ans = 0
  for i in range(n):
    d[i,i] = INF

  for i in range(n):
    for j in range(i+1,n):
      opt = np.min(d[i] + d[j])
      if opt > d[i,j]:
        ans += d[i,j]
        
  print(int(ans))
else:
  print(-1)

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

INF = 10 ** 9 + 7
G = [[int(_) for _ in input().split()] for _ in range(N)]
G2 = [G[_].copy() for _ in range(N)]

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

            if G2[i][j] < G[i][j]:
                print(-1)
                exit()
ans = 0
for i in range(N - 1):
    for j in range(i + 1, N):
        if i == j: continue
        elif G2[i][j] == G[i][j]:
            v = G2[i][j]
            for k in range(N):
                if i == j or i == k or j == k: continue
                if G2[i][k] + G2[k][j] == G2[i][j]:
                    v = 0
                    break
            ans += v
print(ans)

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

INF = 10 ** 9 + 7
G = [[int(_) for _ in input().split()] for _ in range(N)]
G2 = [G[_].copy() for _ in range(N)]

for k in range(N):
    for i in range(N):
        for j in range(N):
            G2[i][j] = min(G2[i][j], G2[i][k] + G2[k][j])
ans = 0
for i in range(N - 1):
    for j in range(i + 1, N):
        if i == j: continue
        if G2[i][j] < G[i][j]:
            print(-1)
            exit()
        elif G2[i][j] == G[i][j]:
            v = G2[i][j]
            for k in range(N):
                if i == j or i == k or j == k: continue
                if G2[i][k] + G2[k][j] == G2[i][j]:
                    v = 0
                    break
            ans += v
print(ans)

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7






N = getN()
query = [getList() for i in range(N)]
query_before = copy.deepcopy(query)

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

warshall_floyd(query)

if query != query_before:
    print(-1)
    exit()

edges = []
for i in range(N):
    for j in range(i + 1, N):
        edges.append([query[i][j], i, j])

cnt = 0
for i in edges:
    flag = True
    w, s, t = i
    for k in range(N):
        if k != s and k != t and w >= query[s][k] + query[k][t]:
            flag = False
            break
    if flag:
        cnt += w
print(cnt)

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

    ans = 0
    for i in range(n - 1):
        for j in range(i + 1, n):
            d = m[i][j]
            t = min(m[i][k] + m[k][j] if k != i and k != j else d + 1 for k in range(n))
            if t < d:
                print(-1)
                exit()
            if d < t:
                ans += d

    print(ans)


if __name__ == '__main__':
    main()

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

    ans = 0
    for i in range(n - 1):
        for j in range(i + 1, n):
            d = m[i][j]
            for k in range(n):
                if k in (i, j):
                    continue
                t = m[i][k] + m[k][j]
                if t < d:
                    print(-1)
                    return
                if t == d:
                    break
            else:
                ans += d
    else:
        print(ans)


if __name__ == '__main__':
    main()

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

    ans = 0
    for i in range(n - 1):
        for j in range(i + 1, n):
            d = m[i][j]
            for k in range(n):
                if k in (i, j):
                    continue
                t = m[i][k] + m[k][j]
                if t < d:
                    print(-1)
                    exit()
                if t == d:
                    break
            else:
                ans += d
    else:
        print(ans)


if __name__ == '__main__':
    main()

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

    ans = 0
    for i in range(n - 1):
        for j in range(i + 1, n):
            d = m[i][j]
            for k in range(n):
                if k in (i, j):
                    continue
                t = m[i][k] + m[k][j]
                if t < d:
                    print(-1)
                    exit()
                if t == d:
                    break
            else:
                ans += d
    else:
        print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    import heapq
    n = int(readline())
    dist = [[INF] * n for _ in range(n)]
    hq = []
    table = [[0] * n for _ in range(n)]

    for i in range(n):
        a = list(map(int, readline().split()))
        for j in range(i + 1, n):
            hq.append((a[j], i, j))
            table[i][j] = a[j]
            dist[i][j] = a[j]
            dist[j][i] = a[j]

    for i in range(n):
        dist[i][i] = 0

    for i in range(n):
        for j in range(n):
            for k in range(n):
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
                    dist[j][i] = dist[i][j]

    for i in range(n):
        for j in range(i + 1, n):
            if dist[i][j] != table[i][j]:
                print(-1)
                sys.exit()

    ans = 0
    for i in range(n):
        for j in range(i + 1, n):
            for k in range(n):
                if k != i and k!= j:
                    if dist[i][j] == dist[i][k] + dist[k][j]:
                        break
            else:
                ans += dist[i][j]

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
class Graph():  
    def __init__(self, n, edge, indexed=1):
        self.n = n
        self.edge = edge
        self.indexed = indexed
        self.graph = [[] for _ in range(n)]
        for e in edge:
            self.graph[e[0] - indexed].append((e[1] - indexed, e[2]))
            self.graph[e[1] - indexed].append((e[0] - indexed, e[2]))

    def warshall_floyd(self, INF=10**18):
        dist = [[INF for j in range(self.n)] for i in range(self.n)]
        for i in range(self.n):
            dist[i][i] = 0
        for i in range(self.n):
            for j, cost in self.graph[i]:
                dist[i][j] = cost
        for k in range(self.n):
            for i in range(self.n):
                for j in range(self.n):
                    if dist[i][k] != INF and dist[k][j] != INF:
                        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
        return dist

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

E = list()

for i in range(N):
    for j in range(N):
        if i == j:
            continue
        E.append((i, j, A[i][j]))

g = Graph(N, E, 0)
wf = g.warshall_floyd()

flag = False

for i in range(N):
    for j in range(N):
        if A[i][j] != wf[i][j]:
            print(-1)
            flag = True
            break
    if flag:
        break
else:
    res = 0
    for i in range(N - 1):
        for j in range(i + 1, N):
            for k in range(N):
                if i == k or j == k:
                    continue
                if A[i][j] == A[i][k] + A[k][j]:
                    break
            else:
                res += A[i][j]

    print(res)

Solution (Python):
N = int(input())
dist = [[float("inf") if i != j else 0 for i in range(N)] for j in range(N)]

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

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

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 dist[i][j] == dist[i][k] + dist[k][j]:
                break
        else:
            
            ans += dist[i][j]
print(ans)

Solution (Python):
import sys
import itertools

import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines




N = int(input())
dist = [[float("inf") if i != j else 0 for i in range(N)] for j in range(N)]

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

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

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 dist[i][j] == dist[i][k] + dist[k][j]:
                break
        else:
            ans += dist[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):


import sys
input=sys.stdin.readline

def main():
    N=int(input())
    A=[tuple(map(int,input().split())) for i in range(N)]
    
    ans=0
    for i in range(N):
        for j in range(i+1,N):
            ans+=A[i][j]
            for k in range(N):
                if i!=k and j!=k:
                    if A[i][j]>A[i][k]+A[k][j]:
                        print(-1)
                        exit()
                    elif A[i][j]==A[i][k]+A[k][j]:
                        ans-=A[i][j]
                        break
                    
    print(ans)
    
    
if __name__=="__main__":
    main()

Solution (Python):
def resolve():
    N = int(input())
    A = [list(map(int, input().split())) for _ in range(N)]
    ans = 0
    for src in range(N-1):
        for dst in range(src+1, N):
            mintotal = float("inf")
            for trans in range(N):
                if trans == src or trans == dst:
                    continue
                mintotal = min(mintotal, A[src][trans] + A[trans][dst])
            if A[src][dst] > mintotal:
                print(-1)
                return
            if A[src][dst] < mintotal:
                ans += A[src][dst]
    print(ans)




if '__main__' == __name__:
    resolve()

Solution (Python):
n=int(input())
a=[list(map(int,input().split())) for _ in range(n)]
ans=0
for i in range(n-1):
  for j in range(i+1,n):
    flg=True
    for k in range(n):
      if k in (i,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]:
        flg=False
    if flg:
      ans+=a[i][j]
      

print(ans)

Solution (Python):


import sys
input = sys.stdin.buffer.readline

def floyd_warshall(V, dist):                                               
    res = 0
    for i in range(V):
        for j in range(i+1,V):
            flg = 0
            for k in range(V):
                if k==i or k==j:
                    continue
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    return -1
                if dist[i][j] < dist[i][k] + dist[k][j]:
                    flg += 1
                if flg == V-2:
                    res += dist[i][j]
    return res

N = int(input())

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

if N ==2:
    print(dist[0][1])
else:
    print(floyd_warshall(N, dist))

Solution (Python):


LI = lambda: list(map(int, input().split()))


N = int(input())
A = [LI() for _ in range(N)]


def main():
    ans = 0
    for i in range(N):
        for j in range(N):
            flag = True
            for k in range(N):
                if i == k or j == k:
                    continue
                d = A[i][k] + A[k][j]
                if A[i][j] > d:
                    print(-1)
                    return
                if A[i][j] == d:
                    flag = False
            if flag:
                ans += A[i][j]
    ans //= 2
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
def main():
    import sys

    def I():
        return int(sys.stdin.readline().rstrip())

    def LI():
        return list(map(int, sys.stdin.readline().rstrip().split()))  

    N = I()
    A = [[0] * (N + 1)] + [[0] + LI() for _ in range(N)]

    ans = (sum(sum(A[i]) for i in range(N + 1))) // 2
    minus = 0

    
    for i in range(1, N):
        for j in range(i + 1, N + 1):
            for k in range(1, N + 1):
                if k == i or k == j:
                    continue
                else:
                    if A[i][j] > A[i][k] + A[k][j]:  
                        print(-1)
                        exit()
                    elif A[i][j] == A[i][k] + A[k][j]:  
                        minus += A[i][j]
                        break

    print(ans - minus)

if __name__ == '__main__':
    main()

Solution (Python):
import sys

readline = sys.stdin.readline

def main():
    N = int(input())
    grid = []
    for _ in range(N):
        tmp = list(map(int, readline().split()))
        grid.append(tmp)
    
    removes = set([])
    for k in range(N):
        for i in range(N):
            for j in range(N):
                gridij = grid[i][j]
                gridik = grid[i][k]
                gridkj = grid[k][j]
                if gridij > gridik + gridkj:
                    print(-1)
                    return
                elif i != j and j != k and k != i and gridij == gridik + gridkj:
                    removes.add((i, j))
                else:
                    pass
    
    ans = 0
    for i in range(N):
        for j in range(i+1, N):
            ans += grid[i][j] * ((i, j) not in removes)
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
from sys import stdin, stdout
input = stdin.readline
print = stdout.write

N = int(input())
A = [[int(i) for i in input().split()] for _ in range(N)]
sumA = sum(sum(A, [])) // 2
correct = True

def isCorrect():
    for u in range(N):
        for v in range(u + 1, N):
            for k in range(N):
                if A[u][k] and A[v][k]:
                    
                    if A[u][k] + A[k][v] < A[u][v]:
                        return False
    return True


if not isCorrect(): print(str(-1))
else:
    for u in range(N):
        for v in range(u + 1, N):
            for k in range(N):
                if A[u][k] and A[k][v]:
                    if A[u][k] + A[k][v] == A[u][v]:
                        sumA -= A[u][v]
                        break
    print(str(sumA))

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


N = int(input())
A = [[int(i) for i in input().split()] for _ in range(N)]
sumA = sum(sum(A, [])) // 2
correct = True

def isCorrect():
    for u in range(N):
        for v in range(u + 1, N):
            for k in range(N):
                if A[u][k] and A[v][k]:
                    
                    if A[u][k] + A[k][v] < A[u][v]:
                        return False
    return True


if not isCorrect(): print(str(-1))
else:
    for u in range(N):
        for v in range(u + 1, N):
            for k in range(N):
                if A[u][k] and A[k][v]:
                    if A[u][k] + A[k][v] == A[u][v]:
                        sumA -= A[u][v]
                        break
    print(str(sumA))

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)]

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

    print(ans)
    return


if __name__ == '__main__':
    main()

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)]

    ans = 0
    for i in range(N):
        for j in range(i + 1, N):
            needed = True
            for k in range(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]:
                    needed = False
            if needed:
                ans += G[i][j]

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys


from collections import deque, Counter, defaultdict


import heapq
import time

start = time.time()
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
inf = 10**18
MOD = 1000000007
ri = lambda : int(input())
rs = lambda : input().strip()
rl = lambda : list(map(int, input().split()))

n = ri()
a=[rl() for _ in range(n)]
c=[[0]*n for _ in range(n)]



for k in range(n):
    for i in range(n):
        for j in range(n):
            if k==i or k==j or i==j:
                continue
            if a[i][j]==a[i][k]+a[k][j]:
                c[i][j]+=1
            if a[i][j]>a[i][k]+a[k][j]:
                print(-1)
                sys.exit()
            a[i][j]=min(a[i][j], a[i][k]+a[k][j])
ans=0
for i in range(n):
    for j in range(i+1,n):
        if c[i][j]==0:
            ans+=a[i][j]
print(ans)