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, copy
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

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

def resolve():
    N = I()
    A = [LI() for _ in range(N)]

    min_cost = copy.deepcopy(A)
    min_cost = warshall_floyd(min_cost)
    ans = copy.deepcopy(min_cost)

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

if __name__ == '__main__':
    resolve()

Solution (Python):






import sys
input = sys.stdin.readline

import math
import bisect
from collections import deque
from fractions import gcd
from functools import lru_cache






MOD = 10**9+7
INF = float('inf')






def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr


def lcm(a, b):
    return a * b // gcd (a, b)


def bit_count(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count





N = inputI()
A = inputILL(N)

class WarshallFloyd():
  def __init__(self, N):
    self.N = N
    self.d = [[float("inf") for i in range(N)] for i in range(N)]

  def add(self, u, v, c, directed=False):
    if directed is False:
      self.d[u][v] = c
      self.d[v][u] = c
    else:
      self.d[u][v] = c

  def WarshallFloyd_search(self):
    for k in range(self.N):
      for i in range(self.N):
        for j in range(self.N):
          self.d[i][j] = min(self.d[i][j], self.d[i][k] + self.d[k][j])
    hasNegativeCycle = False
    for i in range(self.N):
      if self.d[i][i] < 0:
        hasNegativeCycle = True
        break
    for i in range(self.N):
      self.d[i][i] = 0
    return hasNegativeCycle, self.d
  
graph = WarshallFloyd(N)
for i in range(N):
  for j in range(N):
    graph.add(i,j,A[i][j])
    
hasNegativeCycle, d = graph.WarshallFloyd_search()

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

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

Solution (Python):

N = int(input())
nums = [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 nums[i][j] > nums[i][k] + nums[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 nums[i][j] == nums[i][k] + nums[k][j]:
                flag = False
                break

        if flag:
            max_cost += nums[i][j]


print(max_cost)

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


ans = 0
for i in range(N):
    for j in range(i+1,N):

        f = True
        for k in range(N):
            if k == i or k == j:
                continue
            if A[i][j] == A[i][k] + A[k][j]:
                f = False
                break
        
        if f:
            
            ans += A[i][j]


print(ans)

Solution (Python):
def main():
    N = int(input())
    l = []
    for i in range(N):
        a = list(map(int, input().split()))
        l.append(a)
    ans = 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 or k == j:
                    continue
                if l[i][j] == l[i][k] + l[k][j]:
                    break
                if l[i][j] > l[i][k] + l[k][j]:
                    return -1
            else:
                ans += l[i][j]
    return ans
print(main())

Solution (Python):
def main():
    N = int(input())
    A = [list(map(int, input().split())) for _ in range(N)]
    r = 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 A[i][k] + A[k][j] < A[i][j]:
                    return -1
                if A[i][k] + A[k][j] == A[i][j]:
                    break
            else:
                r += A[i][j]
    return r

print(main())

Solution (Python):
N=int(input())
A=[list(map(int,input().split())) for i in range(N)]
res=0
flag=[[False]*N 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()
            elif k!=i and k!=j and A[i][j]==A[i][k]+A[k][j] and not flag[i][j] and not flag[j][i]:
                flag[i][j]=True
                flag[j][i]=True
                res-=A[i][j]
ans=sum(sum(A[i]) for i in range(N))//2+res

print(ans)

Solution (Python):
n=int(input())
d=[list(map(int,input().split())) for i in range(n)]
def fill(l,x):
    w=len(l[0])
    return [[x]*(w+2)]+[[x]+i+[x] for i in l]+[[x]*(w+2)]
def swap(a,b):
    if a>b:
        return b,a
    return a,b
d=fill(d,0)
edge=[{} for i in range(n+1)]
for j in range(1,n+1):
    for i in range(j+1,n+1):
        edge[j][i]=d[i][j]
for k in range(1,n+1):
    for i in range(1,n+1):
        for j in range(1,n+1):
            if  d[i][j]>d[i][k]+d[k][j]:
                print(-1)
                quit()
            elif d[i][j]==d[i][k]+d[k][j]:
                if k==i or k==j:
                    continue
                x,y=swap(i,j)
                if y in edge[x]:
                    del edge[x][y]
ans=0
for i in edge:
    ans+=sum(i.values())
print(ans)

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



def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def LI(): return list(map(int,input().split()))
def TI(): return tuple(map(int,input().split()))


import copy

def main():
	n=II()
	A=[]
	for _ in range(n):
		a=LI()
		A.append(a)

	for i in range(n):
		A[i][i]=10**10

	B=copy.deepcopy(A)

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

	if A!=B:
		print(-1)
		exit(0)

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

	ans=0

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

	print(ans)


if __name__ == "__main__":
	main()

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


def warshall_floyd(d):
    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()
                elif d[i][j] == d[i][k] + d[k][j] and k != i and k != j:
                    delete[i][j] = True
                    delete[j][i] = True                 
    return d

N = int(input())
inf = float("inf")
delete = [[False]*N for _ in range(N)]



d = [[int(x) for x in input().split()] for _ in range(N)]
d = warshall_floyd(d)

ans = 0

for i in range(N):
    for j in range(i + 1, N):
        if delete[i][j]:
            continue
        ans += d[i][j]
print(ans)

Solution (Python):
from collections import defaultdict
n = int(input())
a = [list(map(int,input().split())) for i in range(n)]
dic = defaultdict(lambda :0)
cut = 0
for k in range(n):
    for i in range(n):
        for j in range(n):
            if i == j:continue
            temp = a[i][k] + a[k][j]

            if a[i][j] > temp:
                print(-1)
                exit()

            if temp == a[i][j] and i < j and k != i and k != j:
                if not dic[(i, j)]:
                    cut += a[i][j]
                    dic[(i, j)] = 1
rec = 0
for i in range(n):
    for j in range(n):
        if i < j :rec += a[i][j]

print(rec - cut)

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

def main():
    N = int(readline())
    A = np.array(read().split(), dtype=np.int64).reshape(N,N)

    INF = 10**15
    ans = 0
    for i in range(N):
        B = A[i,:] + A
        np.fill_diagonal(B, INF)
        B[:,i] = INF
        C = B.min(axis=1)
        C[i] = 0

        if (C < A[i,:]).sum() > 0:
            print(-1)
            exit()
        else:
            index = C > A[i,:]
            ans += A[i, index].sum()

    print(ans // 2)


if __name__ == "__main__":
    main()

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

def main():
    N = int(readline())
    A = [[int(i) for i in readline().split()] for _ in range(N)]

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


if __name__ == "__main__":
    main()

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

def main():
    N = int(readline())
    A = [[int(i) for i in readline().split()] for _ in range(N)]

    via_min = [[10**15] * N for _ in range(N)]

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


if __name__ == "__main__":
    main()

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

def main():
    N = int(readline())
    A = [[int(i) for i in readline().split()] for _ in range(N)]

    via_min = [[10**15] * N for _ in range(N)]

    for i in range(N):
        for j in range(N):
            for k in range(N):
                if k == i or k == j:
                    continue
                via_min[i][j] = min(via_min[i][j], A[i][k] + A[k][j]) 

    ans = 0
    for i in range(N):
        for j in range(i+1,N):
            if via_min[i][j] < A[i][j]:
                print(-1)
                exit()
            elif via_min[i][j] == A[i][j]:
                continue
            else:
                ans += A[i][j]
    
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
from copy import deepcopy
N = int(input())
origin_dp = [list(map(int, input().split())) for _ in range(N)]
dp = deepcopy(origin_dp)

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

judge = origin_dp == dp

if judge:
    ans = 0
    for i in range(N):
        for j in range(N):
            for k in range(N):
                if dp[j][k] == 0 or dp[j][i] == 0 or dp[i][k] == 0: continue

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

    print(ans)
else:
    print(-1)

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

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


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

    return d  
from copy import deepcopy
d = warshall_floyd(deepcopy(dl), n)

if d != dl:
    print(-1)
    exit()

ans = 0
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        flag = True
        for k in range(n):
            if i == k or k == j:
                continue
            if d[i][j] == d[i][k] + d[k][j]:
                flag = False
        if flag:
            ans += d[i][j]
print(ans//2)

Solution (Python):
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
import math





















N = int(input())
A = [list(map(int,input().split())) for _ in range(N)]
flag = 1
s = 0
for i in range(N-1):
    if flag == 0:
        break
    for j in range(i+1,N):
        judge = 1
        if flag == 0:
            break
        a = A[i][j]
        s += a
        for k in range(N):
            if k == i or k == j:
                continue
            elif a > A[i][k] + A[k][j]:
                flag = 0
                break
            elif a == A[i][k] + A[k][j]:
                s -= a
                break
            else:
                continue
if flag == 0:
    print(-1)
else:
    print(s)

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

def warshall_floyd(d):
  
  for k in range(N):
    for i in range(N):
      for j in range(N):
        if i<j and i!=k and k!=j and d[i][j]==d[i][k]+d[k][j]:
          
          shortcut_set.add((i,j))
        d[i][j]=min(d[i][j],d[i][k]+d[k][j])
  return d

mat=[]
for i in range(N):
  mat.append([int(x) for x in input().split()])


dist=[[float("inf")]*N for i in range(N)]
graph=[[] for _ in range(N)]
for i in range(N):
  for j in range(N):
    if i==j:
      dist[i][i]=0
    else:
      graph[i].append((j,mat[i][j]))
      dist[i][j]=mat[i][j]



shortcut_set=set()
dist=warshall_floyd(dist)


for i in range(N):
  for j in range(N):
    if dist[i][j]!=mat[i][j]:
      print(-1)
      sys.exit(0)
      
answer=0
for i in range(N):
  for j in range(i+1,N):
    if not (i,j) in shortcut_set:
      answer+=dist[i][j]
      
print(answer)

Solution (Python):
import copy


def warshalFloyd(n):
    G=[list(map(int,input().split())) for _ in range(n)]
    D=copy.deepcopy(G)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                G[i][j]=min(G[i][j],G[i][k]+G[k][j])

    return G if G==D else -1


n=int(input())
Graph=warshalFloyd(n)
if Graph==-1:print(-1);exit()

for k in range(n):
    for i in range(n):
        for j in range(n):
            if Graph[i][j]!=0 and Graph[i][k]!=0 and Graph[k][j]!=0:
                if Graph[i][j]==Graph[i][k]+Graph[k][j]:
                    Graph[i][j]=0

ans=0
for i in range(n):
    for j in range(i,n):
        ans +=Graph[i][j]
print(ans)

Solution (Python):
import sys
import copy
import heapq
from collections import deque


INF = sys.maxsize



def main():
    n = int(input())
    dist_mat = []
    for i in range(n):
        l = list(map(int, input().split()))
        dist_mat.append(l)

    dist_mat_calc = [[INF for i in range(n)] for j in range(n)]

    ans = 0
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if i == j:
                    continue
                dist_mat_calc[i][j] = min(dist_mat_calc[i][j], dist_mat[i][k] + dist_mat[k][j])

    tmp = [[dist_mat_calc[j][i] if dist_mat_calc[j][i] != INF else 0 for i in range(n)] for j in range(n)]
    if tmp != dist_mat:
        print(-1)
        exit(0)

    ans = 0

    for i in range(n):
        for j in range(i, n):
            if i == j:
                continue
            tmp = min([x+y for (x,y) in zip(dist_mat_calc[i], dist_mat_calc[j])])
            if dist_mat_calc[i][j] < tmp:
                ans+=dist_mat_calc[i][j]

    print(ans)





if __name__ == '__main__':
    main()

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

for i in range(N):
    if A[i][i] != 0:
        print(-1)
        exit()
import copy
ca = copy.deepcopy(A)

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



for i in range(N):
    for j in range(N):
        if A[i][j] != ca[i][j]:
            print(-1)
            exit()

ans = 0
for i in range(N):
    for j in range(N):
        need = True
        for k in range(N):
            if i != k and j != k and ca[i][k] + ca[k][j] == ca[i][j]: 
                need = False
        if need:
            ans += ca[i][j]
ans = ans//2 
print(ans)

Solution (Python):
import copy
n = int(input())
inf = 10**18
g = [[]]
for i in range(n):
    g.append([0]+list(map(int, input().split())))

g2 = copy.deepcopy(g)
for k in range(1, n+1):
    for i in range(1, n+1):
        for j in range(1, n+1):
            if g[i][k] == 0 or g[k][j] == 0:
                continue
            if g[i][j] == g[i][k] + g[k][j]:
                g[i][j] = 0

ans = 0
for i in range(1, n+1):
    ans += sum(g[i])

for i in range(1, n+1):
    for j in range(1, n+1):
        if g[i][j] == 0:
            g[i][j] = inf
    g[i][i] = 0

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

if g != g2:
    ans = -1

print(ans//2)

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

n = int(input())

d = [[float('inf')]*n for i in range(n)]

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

for i in range(n):
    if d[i][i] != 0:
        print(-1)
        exit()

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

ans = 0
for i in range(n):
    for j in range(n):
        for k in range(n):
            if i==k or k==j :continue
            if d[i][j] == d[i][k] + d[k][j]:
                break
        else:
            ans += d[i][j]

print(ans//2)

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N=int(input())
    A=[list(map(int,input().split())) for _ in range(N)]
    f=[[True]*N 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()
                elif i!=k and j!=k and A[i][j]==A[i][k]+A[k][j]:
                    f[i][j]=False
    ans=0
    for i in range(N):
        for j in range(N):
            ans+=A[i][j]*f[i][j]
    print(ans//2)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
input=sys.stdin.readline
n=int(input())
wf=[list(map(int,input().split())) for i in range(n)]

ans=0
for i in range(n):
    for j in range(i+1,n):
        use=True
        for h in range(n):
            if h!=i and h!=j and wf[i][j] > wf[i][h]+wf[h][j]:
                print(-1)
                exit()
            if h!=i and h!=j and wf[i][j] == wf[i][h]+wf[h][j]:
                use=False
        if use:
            ans+=wf[i][j]
print(int(ans))

Solution (Python):

import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read
inp = sys.stdin.buffer.readline
def inpS(): return inp().rstrip().decode()
readlines = sys.stdin.buffer.readlines
MOD = 10**9+7
INF = 1<<60



import numpy as np
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix

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

    csr = csr_matrix(np.array(A))
    wf =  floyd_warshall(csr, directed=False)
    for i in range(N):
        wf[i][i] = INF
        A[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__":
    resolve()

Solution (Python):

import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read
inp = sys.stdin.buffer.readline
def inpS(): return inp().rstrip().decode()
readlines = sys.stdin.buffer.readlines
MOD = 10**9+7
INF = 1<<60



def resolve():
    N = int(input())
    A = [list(map(int, input().split())) for _ in range(N)]
    B = [[True]*(N) 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)
                    return
                
                
                elif A[i][j] == A[i][k] + A[k][j] and k!=i and k!= j:
                    B[i][j] = False

    ans = [sum([A[i][j] for j in range(N) if B[i][j]]) for i in range(N)]
    print(sum(ans)//2)

if __name__ == "__main__":
    resolve()

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

N = int(input())
INF = 10**10
cost = [[INF]*N for _ in range(N)]

for u in range(N):
    C = list(map(int, input().split()))
    for v in range(N):
        if u==v: 
            continue
        cost[u][v] = C[v]
 
ans = 0
for u in range(N):
    for v in range(u+1,N):
        mn = INF 
        for w in range(N):
            mn = min(mn, cost[u][w]+cost[w][v])    
        if (cost[u][v] > mn): 
            print (-1)
            exit()
        elif (cost[u][v] < mn): 
            ans += cost[u][v]                      
print (ans)

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

N = int(input())
INF = 10**10
cost = [[INF]*N for _ in range(N)]

for i in range(N):
    C = list(map(int, input().split()))
    for j in range(N):
        cost[i][j] = C[j]
    cost[i][i] = INF

ans = 0
for j in range(N):
    for k in range(j+1,N):
        mn = INF
        for i in range(N):
            mn = min(mn, cost[j][i]+cost[i][k])    
        if (cost[j][k] > mn):
            print (-1)
            exit()
        elif (cost[j][k] < mn):
            ans += cost[j][k]                      
print (ans)

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

d = [a[i][:] for i in range(n)]
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])

ans = 0
for i in range(n):
    for j in range(n):
        if a[i][j] > d[i][j]:
            ans = -2
            break
        for k in range(n):
            if i == k or j == k: continue
            if d[i][j] == d[i][k] + d[k][j]: break
        else:
            ans += d[i][j]
    else:
        continue
    break

ans //= 2
print(ans)

Solution (Python):
from copy import deepcopy
INF = 10 ** 10
N = int(input())
A = []
for _ in range(N):
    A.append(list(map(int,input().split())))


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

B = deepcopy(A)
for k in range(N):
    for i in range(N):
        for j in range(N):
            if B[i][k] != 0 and B[k][j] != 0 and B[i][j] == B[i][k] + B[k][j]:
                B[i][j] = INF

ans = 0
for i in range(N):
    for j in range(N):
        if B[i][j] != INF:
            ans += B[i][j]
ans //= 2

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 == B:
    print(ans)
else:
    print(-1)

Solution (Python):


import io
import math
import scipy.sparse as s,numpy as n

f=n.loadtxt(open(0),skiprows=1)

g=s.csgraph.dijkstra(f)

h=n.where(g,g,1)

print(int(sum(t[j]*(t[j]<t+h[j]).all()for i,t in enumerate(h)for j in range(i)))*(f==g).all()or-1)

Solution (Python):
from copy import deepcopy
n = int(input())
INF = 10**12

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

B = [[1]*n for _ in range(n)]
G = deepcopy(A)

for k in range(n):
  for i in range(n):
    for j in range(n):
      G[i][j] = min(G[i][j], G[i][k]+G[k][j])
      if not (i==j or j==k or k==i):
        if G[i][j] == G[i][k]+G[k][j]:
          B[i][j] = 0
      
if A==G:
  ans = 0
  for i in range(n):
    for j in range(i+1,n):      
      ans += G[i][j] * B[i][j]
  print(ans)
else:
  print(-1)

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

for i in range(N):    
    for j in range(N):
        ok = True
        for k in range(N):
            if A[i][j] > A[i][k] + A[k][j]:
                print(-1)
                exit()
            if i != k and j != k:
                if A[i][j] == A[i][k] + A[k][j]:
                    ok = False
        if ok:
            ans += A[i][j]

print(ans//2)

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

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

class WarshallFloyd:
    def __init__(self,n):
        self.v = n
        self.d = [[1e100]*n for _ in range(n)]
        for i in range(n):
            self.d[i][i] = 0

    def path(self,x,y,c):
        if x == y:
            return False
        self.d[x][y] = c
        self.d[y][x] = c
        return True

    def build(self):
        for k in range(self.v):
            for i in range(self.v):
                for j in range(self.v):
                    self.d[i][j] = min(self.d[i][j], self.d[i][k] + self.d[k][j])

wf = WarshallFloyd(n)

for i in range(1,n):
    for j in range(i):
        wf.path(i,j,A[i][j])

wf.build()
ans = 0
for i in range(n-1):
    for j in range(i+1,n):
        if A[i][j] > wf.d[i][j]:
            print(-1)
            exit(0)
        flag = 1
        for k in range(n):
            if i != k != j:
                if wf.d[i][j] == wf.d[i][k] + wf.d[k][j]:
                    flag = 0
                    break
        if flag:
            ans += A[i][j]
print(ans)

Solution (Python):
import copy
n = int(input())
l = [list(map(int,input().split())) for i in range(n)]
l1 = copy.deepcopy(l)

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

            elif l[i][j] == l[i][k]+l[k][j]:
                if i != k and k != j :
                    l1[i][j] = 0
ans = 0
for i in l1:
    for j in i:
        ans += j
print(ans//2)

Solution (Python):























import sys
read = sys.stdin.readline
ra = range
enu = enumerate


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    


N = read_a_int()
A = read_matrix(N)
from itertools import combinations
edge_rm = set()
for u, v in combinations(range(N), 2):
    for i in range(N):
        if i == u or i == v:
            continue
        a = A[u][i]
        b = A[i][v]
        c = A[u][v]
        
        if c == a + b:
            
            edge_rm.add((u, v) if u < v else(v, u))
        elif c > a + b:
            print(-1)
            exit()

ans_sum = 0
for a in A:
    for aa in a:
        ans_sum += aa
ans_sum //= 2
for u, v in edge_rm:
    ans_sum -= A[u][v]
print(ans_sum)