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
import copy

def solve(N: int, A: "List[List[int]]"):
    B = copy.deepcopy(A)
    for start_node in range(0,N):
        for end_node in range(start_node+1,N):
            min_dist = 10**12
            for transit in range(N):
                if transit == start_node or transit == end_node:
                    continue
                min_dist = min(min_dist,A[start_node][transit]+A[transit][end_node])

            
            if A[start_node][end_node] > min_dist:
                print(-1)
                return 
            elif A[start_node][end_node] == min_dist:
                B[start_node][end_node] = 0
            else:
                continue
    answer =0
    for i in range(N):
        for j in range(i+1,N):
            answer+=B[i][j]
    print(answer)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    A = [[int(next(tokens)) for _ in range(N)] for _ in range(N)]  
    solve(N, A)

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    N = int(input())
    A = [[int(a) for a in input().split()] for _ in range(N)]
    B = [[A[i][j] for j in range(N)] for i in range(N)]
    C = [[A[i][j] for j in range(N)] for i in range(N)]
    for k in range(N):
        for i in range(N):
            for j in range(N):
                t = B[i][k] + B[k][j]
                if t < B[i][j]:
                    return -1
                if B[i][k] and B[k][j] and t == B[i][j]:
                    C[i][j] = 0
    return sum([sum([C[i][j] for j in range(i)]) for i in range(N)])
print(main())

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

Solution (Python):
INF = 10 ** 12

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

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

res = 0
for i in range(N):
    for j in range(i + 1, N):
        for k in range(N):
            if i != k and j != k and a[i][j] == a[i][k] + a[k][j]:
                break
        else:
            res += a[i][j]

print(res)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

n=int(input())
aa=LLI(n)

def main():
    ans=sum(sum(ar) for ar in aa)//2
    fin=set()
    for w in range(n):
        aaw=aa[w]
        for u in range(n):
            if u==w:continue
            aau=aa[u]
            for v in range(u):
                if v==w:continue
                d=aau[w]+aaw[v]
                if d<aau[v]:
                    print(-1)
                    exit()
                if d==aau[v] and (u,v) not in fin:
                    ans-=d
                    fin.add((u,v))
    print(ans)

main()

Solution (Python):
import sys
inf = float('inf')
N = int(input())
d = [list(map(int, input().split())) for _ in range(N)]
for i in range(N):
    d[i][i] = 0
ans=0
for a in range(N):
    for b in range(N):
        flag = True
        for i in range(N):
            if i == a or i == b:
                continue
            if d[a][i]+d[i][b]<d[a][b]:
                print(-1)
                sys.exit()
            if d[a][i]+d[i][b]==d[a][b]:
                flag = False
                break
        if flag:
            ans+=d[a][b]
            
print(ans//2)

Solution (Python):
n = int(input())
dist = [list(map(int,input().split())) for i in range(n)]
use = [[True for i in range(n)] for j in range(n)]
ans = 0

for i in range(n):
    for j in range(n):
        for k in range(n):
            if dist[j][k] > dist[j][i] + dist[i][k]:
                print(-1)
                exit()
            elif j != i and j != k and i != k and dist[j][k] == dist[j][i] + dist[i][k]:
                use[j][k] = False

for i in range(n):
    for j in range(n):
        if use[i][j]:
            ans += dist[i][j]

print(ans//2)

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

ans = 0
for i in range(N):
    for j in range(N):
        if all([A[i][j] < A[i][k]+A[k][j] or k==i or k==j for k in range(N)]):
            ans += A[i][j]
            
print(ans//2)

Solution (Python):
def main():
    n=int(input())
    if n==1:
        print(0)
        return 0
    import numpy as np
    p=np.array([np.array(list(map(int,input().split()))) for _ in [0]*n])
    if n==2:
        print(p[0][1])
        return 0
    import scipy.sparse.csgraph as sp
    ans=0
    d=np.full((n,n),0)
    for i in range(n):
        for j in range(i+1,n):
            b=p[i][j]
            if b!=np.sort(p[i]+p[j])[2]:
                d[i][j],d[j][i]=b,b
                ans+=b
    s=sp.shortest_path(d)
    if (s==p).all():
        print(ans)
    else:
        print(-1)
main()

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, atan2
from operator import mul
from functools import reduce
sys.setrecursionlimit(10 ** 9)

INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


n = I()
G = []
for _ in range(n):
    G += [LI()]


ret = 0
for i in range(n):
    for j in range(i + 1, n):
        flag = 1
        for k in range(n):
            if i == k or j == k:
                continue
            if G[i][j] > G[i][k] + G[k][j]:
                print(-1)
                exit()
            elif G[i][j] == G[i][k] + G[k][j]:
                flag = 0
        if flag:
            ret += G[i][j]


print(ret)

Solution (Python):
import heapq
from collections import deque

N = int(input())
A = [[int(a) for a in input().split()] for _ in range(N)]

def dijkstra_heap(s, edge, n):
    
    d = [10**9+1] * n
    used = [True] * n 
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d


Road = [[] for _ in range(N)]
h = []
for i in range(N):
    for j in range(i+1, N):
        heapq.heappush(h, (A[i][j], i, j))
        
m = h[0][0]
D = [[10**9+1]*N for _ in range(N)]
ans = 0
while h:
    t = heapq.heappop(h)
    cost = t[0]
    i = t[1]
    j = t[2]
    if cost < 2*m:
        Road[i].append((cost, j))
        Road[j].append((cost, i))
        D[i][j] = cost
        D[j][i] = cost
    elif D[i][j] > cost:
        D[i] = dijkstra_heap(i, Road, N)
        if D[i][j] > cost:
            Road[i].append((cost, j))
            Road[j].append((cost, i))
            D[i][j] = cost
            D[j][i] = cost
    if D[i][j] < cost:
        ans = -1
        break
            
if ans == 0:
    for i in range(N):
        for t in Road[i]:
            ans += t[0]
            
    ans //= 2
        
print(ans)

Solution (Python):
n = int(input())
mat = [list(map(int, input().split())) for _ in range(n)]
ans = 0
d = [[1] * n for _ in range(n)]
for i in range(n):
    for j, c2 in enumerate(row[i] for row in mat):
        for k, (c1, c3) in enumerate(zip(mat[j], mat[i])):
            if c1 > c2+c3:
                print(-1)
                exit(0)
            elif i != j and i != k and c1 == c2 + c3:
                d[j][k] = 0
for i in range(n):
    for j in range(n):
        if d[i][j]:
            ans += mat[i][j]
print(ans // 2)

Solution (Python):
N = int(input())
A = list(list(map(int,input().split()))for i in range(N))
B = [A[i][:] for i in range(N)]
ans = 0
for i in range(N):
    for j in range(i+1,N):
        flag = True
        for k in range(N):
            if not i != k != j:
                continue
            if A[i][j] == A[i][k] + A[j][k]:
                flag = False
            elif A[i][j] > A[i][k] + A[j][k]:
                print(-1)
                exit()
        if flag:
            ans += A[i][j]
print(ans)

Solution (Python):
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def size(self, x):
        if self.parents[x] < 0:
            return -self.parents[x]
        else:
            self.parents[x] = self.size(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

n = int(input())
A = [list(map(int,input().split())) for i in range(n)]
M = [[j for j in i] for i in A]

for k in range(n):
    for i in range(n):
        for j in range(n):
            M[i][j] = min(M[i][j], M[i][k] + M[k][j])

b = 0
if A != M:
    print(-1)
else:
    ans = 0
    for i in range(n):
        for j in range(i+1, n):
            b = 0
            for k in range(n):
                if k != i and k != j and M[i][j] == M[i][k] + M[k][j]:
                    b = 1
                    break
            if b == 0:
                ans += A[i][j]
    print(ans)

Solution (Python):
import sys
n=int(input())
a=[list(map(int,input().split())) for i in range(n)]
inf=float("inf")
data=[[inf]*n for i in range(n)]
ans=0
for i in range(n):
    for j in range(n):
        for k in range(n):
            if i==k or j==k:
                continue
            if a[i][j]==a[i][k]+a[k][j]:
                break
            elif a[i][j]>a[i][k]+a[k][j]:
                print(-1)
                sys.exit()
        else:
            data[i][j]=a[i][j]
            ans+=a[i][j]
print(ans//2)

Solution (Python):
import copy
N = int(input())
A = [list(map(int, input().split())) for i in range(N)]
B = copy.deepcopy(A)
table = [[True]*N for i in range(N)]
ans = 0
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        for k in range(N):
            if k == i or k == j:
                continue
            else:
                if B[i][k] == B[i][j]+B[j][k]:
                    table[i][k] = False
                B[i][k] = min(B[i][k], B[i][j]+B[j][k])


if A == B:
    for i in range(N):
        for j in range(N):
            if table[i][j]:
                ans += B[i][j]
    print(ans//2)
else:
    print(-1)

Solution (Python):



import sys
input = sys.stdin.readline
def inputs():return [int(x) for x in input().split()]
N= int(input())
dist_mat=[inputs() for _ in range(N)]
ans=0
for i in range(N):
  for j in range(N):
    for k in range(N):
      if dist_mat[j][k]==dist_mat[j][i]+dist_mat[i][k] and dist_mat[j][i]>0 and dist_mat[i][k]>0:
        
        dist_mat[j][k]=0
      elif dist_mat[j][k]>dist_mat[j][i]+dist_mat[i][k] and dist_mat[j][i]>0 and dist_mat[i][k]>0:
        print(-1)
        exit()
for i in range(N):
  for j in range(N):
    ans +=dist_mat[i][j]
print(ans//2)

Solution (Python):
import sys
from copy import deepcopy as dc
input = sys.stdin.buffer.readline
N = int(input())
d = [list(map(int, input().split())) for _ in range(N)]
d2 = dc(d)
for k in range(N):
  for i in range(N):
    for j in range(N):
      d2[i][j] = min(d2[i][k] + d2[k][j], d2[i][j])
f = 0
for i in range(N):
  for j in range(N):
    if d[i][j] != d2[i][j]:
      f = 1
if f:
  print(-1)
else:
  res = 0
  for i in range(N):
    for j in range(N):
      x = 1
      for k in range(N):
        if k != i and k != j:
          if d[i][j] == d[i][k] + d[k][j]: x = 0
      res += x * d[i][j]
          
  print(res // 2)

Solution (Python):
def union(parent,size,a,b):
    x=find(parent,a)
    y=find(parent,b)
    if x!=y:
        if size[x]<size[y]:
            parent[x]=y 
            size[y]=size[x]+size[y]
        else:
            parent[y]=x 
            size[x]=size[x]+size[y]
    return parent,size 
def find(parent, a):
    while a != parent[a]:
            parent[a]=parent[parent[a]]
            a=parent[a]
    return a
n=int(input())
mat=[]
for i in range(n):
    mat.append([int(i) for i in input().split()])
mat1=[[mat[i][j] for j in range(n)]for i in range(n)]
for k in range(n):
    for i in range(n):
        for j in range(n):
            mat1[i][j]=min(mat1[i][j],mat1[i][k]+mat1[k][j])

if mat1!=mat:
    print(-1)
    exit()
need=[[1 for j in range(n)]for i in range(n)]
for k in range(n):
    for i in range(n):
        for j in range(i):
            if k==j or k==i:
                continue 
            if mat[i][k]+mat[k][j]==mat[i][j]:
                need[i][j]=need[j][i]=0 
ans=0 
for i in range(n):
    for j in range(n):
        ans+=need[i][j]*mat[i][j]
print(ans//2)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
from bisect import bisect_left, bisect_right
import random
from itertools import permutations, accumulate, combinations
import sys
import string



INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7




def warshall_floyd(graph):
    
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if graph[i][j] > graph[i][k] + graph[k][j]:
                    return 1




n = I()
graph = [[INF] * n for _ in range(n)]

for i in range(n):
    edges = LI()
    for j in range(n):
        graph[i][j] = edges[j]
        graph[j][i] = edges[j]



if warshall_floyd(graph):
    print(-1)
else:
    ret = 0
    for i in range(n):
        for j in range(i + 1, n):
            if i == j:
                continue
            for k in range(n):
                if k != i and k != j and graph[i][k] + graph[k][j] == graph[i][j]:
                        break
            else:
                ret += graph[i][j]
    print(ret)

Solution (Python):
import copy

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

n=int(input())
arr=[list(map(int,input().split())) for _ in range(n)]
g=[[float('inf')]*n for _ in range(n)]
for i in range(n):
  for j in range(n):
    g[i][j]=arr[i][j]
d=Warshall_Floyd(copy.deepcopy(g),n)
ans=0
for a in range(n):
  for b in range(n):
    if a>=b:
      continue
    w=g[a][b]
    if d[a][b]<w:
      print(-1)
      exit()
    else:
      tmp=10**10
      for k in range(n):
        if k==a or k==b:
          continue
        tmp=min(tmp,d[a][k]+d[k][b])
      if w==tmp:
        continue
      else:
        ans+=w
else:
  print(ans)

Solution (Python):
import copy

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

n=int(input())
arr=[list(map(int,input().split())) for _ in range(n)]
g=[[float('inf')]*n for _ in range(n)]
for i in range(n):
  for j in range(n):
    g[i][j]=arr[i][j]
d=Warshall_Floyd(copy.deepcopy(g),n)
ans=0
for a in range(n):
  for b in range(n):
    if a>=b:
      continue
    w=g[a][b]
    if d[a][b]<w:
      print(-1)
      exit()
    else:
      tmp=10**10
      for k in range(n):
        if k==a or k==b:
          continue
        tmp=min(tmp,d[a][k]+d[k][b])
      if w==tmp:
        continue
      else:
        ans+=w
else:
  print(ans)

Solution (Python):
def Warshall_Floyd(edges,N):
  for k in range(N):
    for i in range(N):
      for j in range(N):
        edges[i][j]=min(edges[i][j],edges[i][k]+edges[k][j])
  return edges

n=int(input())
arr=[list(map(int,input().split())) for _ in range(n)]
edge=[]
for i in range(n):
  for j in range(n):
    if i>=j:
      continue
    edge.append((arr[i][j],(i,j)))
edge=sorted(edge,key=lambda x:x[0])
g=[[float('inf')]*n for _ in range(n)]
for i in range(n):
  for j in range(n):
    g[i][j]=arr[i][j]
d=Warshall_Floyd(g,n)
ans=0
for w,(a,b) in edge:
  if d[a][b]<w:
    print(-1)
    break
  else:
    tmp=10**10
    for k in range(n):
      if k==a or k==b:
        continue
      tmp=min(tmp,d[a][k]+d[k][b])
    if w==tmp:
      continue
    else:
      ans+=w
else:
  print(ans)

Solution (Python):
n = int(input())
ary = [list(map(int,input().split())) for _ in range(n)]
ans = sum([sum(i) for i in ary])
for i in range(n):
    for j in range(n):
        for k in range(n):
            if j == k or i == k:continue
            if ary[i][j] > ary[i][k] + ary[k][j]:print(-1);exit()
            if ary[i][j] == ary[i][k] + ary[k][j]:
                ans -= ary[i][j]
                break
print(ans//2)

Solution (Python):
n = int(input())
ary = [list(map(int,input().split())) for _ in range(n)]
ans = sum([sum(i) for i in ary])
for i in range(n):
    for j in range(n):
        flag = 0
        for k in range(n):
            if j == k or i == k:continue
            if ary[i][j] > ary[i][k] + ary[k][j]:print(-1);exit()
            if ary[i][j] == ary[i][k] + ary[k][j]:
                flag = 1
        if flag:ans -= ary[i][j]
print(ans//2)

Solution (Python):
import sys

n = int(input())

a = []

for _ in range(n):
    A = list(map(int, input().split( )))
    a.append(A)

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




for k in range(n):
    for i in range(n):
        for j in range(n):
            if a[i][k] + a[k][j] < a[i][j]:
                print(-1)
                sys.exit()
            if i!=k and j!=k and a[i][k] + a[k][j] == a[i][j]:

                b[i][j] = 0
ans = 0
for i in range(n):
    ans += sum(b[i])

print(ans//2)

Solution (Python):
n = int(input())
dp = [list(map(int,input().split())) for _ in range(n)]
ans = sum([sum(i) for i in dp])
for i in range(n):
    for j in range(n):
        if dp[i][j] == 0:continue
        a = 0
        for k in range(n):
            if dp[i][k] == 0:continue
            if j == k:continue
            if dp[i][k]+dp[k][j] < dp[i][j]:print(-1);exit()
            if dp[i][k] + dp[k][j] == dp[i][j]:
                a = 1
        if a == 1:ans -= dp[i][j]
print(ans//2)

Solution (Python):
def main():
    N = int(input())
    A = []
    dist = [[0 for _ in range(N)] for _ in range(N)]
    for i in range(N):
        Ai = list(map(int, input().split()))
        A.append(Ai)
        for j in range(N):
            dist[i][j] = Ai[j]

    def wf(dist):
        need = [[1 for _ in range(N)] for _ in range(N)]
        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]:
                        print(-1)
                        exit()
                    elif dist[i][j] == dist[i][k] + dist[k][j]:
                        if i != k and j != k:
                            need[i][j] = 0
                            need[j][i] = 0
        return need

    need = wf(dist)
    ans = 0
    for i in range(N):
        for j in range(i+1, N):
            ans += need[i][j] * dist[i][j]
    print(ans)


if __name__ == '__main__':
    main()

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

import copy

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

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

INF = int(1E17)
ok = True
ans = 0
for i in range(N-1):
    for j in range(i+1, N):
        if A[i][j] != B[i][j]:
            ok = False
        d = INF
        for k in range(N):
            if k == i or k == j:
                continue
            d = min(d, A[i][k] + A[k][j])
        if d > A[i][j]:
            ans += A[i][j]
                
if not ok:
    print(-1)
else:
    print(ans)

Solution (Python):
n=int(input())
d=[]

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

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

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

for i in range(n):
    for j in range(i+1,n):
        for k in range(n):
            if i==k or j==k:
                continue
            if d[i][j]>d[i][k]+d[k][j]:
                print(-1)
                exit()
            elif d[i][j]==d[i][k]+d[k][j]:
                ans[i][j]=0
res=0
for i in range(n):
    res+=sum(ans[i])
print(res)

Solution (Python):
n=int(input())
d=[]
ans=0
for i in range(n):
    tmp=[int(j) for j in input().split()]
    d.append(tmp)
for i in range(n):
    for j in range(i+1,n):
        ans+=d[i][j]

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

Solution (Python):



import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = [LI() for _ in range(n)]
ans = 0
for i in range(n):
    for j in range(i+1,n):
        ans += a[i][j]

for i in range(n):
    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]:
                print(-1)
                quit()
            if a[i][j] == a[i][k] + a[k][j]:
                ans -= a[i][j]
                break
print(ans)

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

flag = [[True] * N for _ in range(N)]

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 A[i][j] > A[i][k] + A[k][j]:
                print(-1)
                exit()
            elif A[i][j] == A[i][k] + A[k][j]:
                flag[i][j] = False

ans = 0

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

print(ans)

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

flag = [[0] * N for _ in range(N)]
dist = [line[:] for line in A]

for k in range(N):
    for i in range(N):
        for j in range(N):
            if i == j or j == k or k == i:
                continue
            if dist[i][j] > dist[i][k] + dist[k][j]:
                dist[i][j] = dist[i][k] + dist[k][j]
            elif dist[i][j] < dist[i][k] + dist[k][j]:
                flag[i][j] += 1

if A != dist:
    print(-1)
    exit()

ans = 0
for i in range(N):
    for j in range(N):
        if flag[i][j] == N-2:
            ans += A[i][j]

ans //= 2
print(ans)

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    N = int(input())
    A = [list(map(int,input().split())) for i in range(N)]
    
    import copy
    D = [[[0,1] for i in range(N)] for j in range(N)]
    for i in range(N):
        for j in range(N):
            D[i][j][0] = A[i][j]
    flag = 0
    
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if k != i and k != j:
                    if D[i][j][0] > D[i][k][0] + D[k][j][0]:
                        flag = 1
                    elif D[i][j][0] == D[i][k][0] + D[k][j][0]:
                        D[i][j][1] += 1
    ans = 0
    for i in range(N):
        for j in range(i+1,N):
            if D[i][j][1] == 1:
                ans += D[i][j][0]
    if flag == 1:
        print(-1)
    else:
        print(ans)
    
main()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=sys.stdin.readline
def resolve():
    n=int(input())
    A=[0]*n
    ans=0
    for i in range(n):
        A[i]=list(map(int,input().split()))
        ans+=sum(A[i])
    from copy import deepcopy
    B=deepcopy(A)
    
    from itertools import product
    for k,i,j in product(range(n),repeat=3):
        B[i][j]=min(B[i][j],B[i][k]+B[k][j])
    
    if A!=B:
        print(-1)
        return
    for i,j in product(range(n),repeat=2):
        if i==j: continue
        flag=False
        for r in range(n):
            if i==r or j==r: continue
            flag=(flag or B[i][j]==B[i][r]+B[r][j])
        if flag: ans-=B[i][j]
    print(ans//2)

resolve()

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

for k in range(n):
    for i in range(n):
        for j in range(n):
            if a[i][k] + a[k][j] < a[i][j]:
                print(-1)
                exit()
            elif a[i][k] + a[k][j] == a[i][j] and i!=k!=j:
                b[i][j] = 0

ans = 0
for i in range(n):
    for j in range(n):
        if b[i][j]:
            ans += a[i][j]
print(ans//2)

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

for i in range(n):
    for j in range(n):
        for k in range(n):
            if a[i][k] + a[k][j] < a[i][j]:
                print(-1)
                exit()
            elif a[i][k] + a[k][j] == a[i][j] and i!=k!=j:
                b[i][j] = 0

ans = 0
for i in range(n):
    for j in range(n):
        if b[i][j]:
            ans += a[i][j]
print(ans//2)

Solution (Python):

import copy

N = int(input())
A = [list(map(int,input().split())) for i in range(N)]
G = copy.deepcopy(A)
whole = 0
for i in range(N):
    for j in range(N):
        whole+=A[i][j]




def warshall_floyd(dist):
    global N
    
    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])

warshall_floyd(G)


flag = 0
ans = 0
for i in range(N):
    for j in range(N):
        if A[i][j] != G[i][j]:
            flag = 1
        else:
            for k in range(N):
                if k != i and k != j:
                    
                    if G[i][j] == G[i][k] + G[k][j]:
                        ans+=A[i][j]
                        
                        break
                
            
if flag == 1:
    print(-1)
else:
    print((whole-ans)//2)

Solution (Python):
N = int(input())
A = []
for i in range(N):
  As = list(map(int, input().split()))
  A.append(As)
r = 0
for i in range(N):
  for j in range(i+1, N):
    ok = False
    for k in range(N):
      if A[i][j] > A[i][k]+A[k][j]:
        print(-1)
        exit()
      if A[i][j] == A[i][k]+A[k][j] and k != i and k != j:
        ok = True
    if not(ok):
      r += A[i][j]
print(r)