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,bisect as bs,collections as cl
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): 
    return list(map(int,input().split()))
def m(): 
    return map(int,input().split())
def onem(): 
    return int(input())
def s(x): 
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): 
    return " ".join(map(str,x))
def max2(x): 
    return max(map(max,x))
def In(x,a): 
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
n = onem()

ans = 0
a = []

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

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

print(ans)

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

flag = True
for k in range(N):
	for i in range(N):
		for j in range(i):
			if A[i][j] > A[i][k] + A[k][j]:
				flag = False
				break
		if not flag:
			break
	if not flag:
		break

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

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

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


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-1):
    for j in range(i,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:
            ans += A[i][j]

print(ans)

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

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


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

print(ans)

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

field = [ [ int(v) for v in input().split() ] for i in range(n) ]
field_2 = [ [ 1 for i in range(n) ] for i in range(n) ]

err = 0
for k in range(n):
    for i in range(n):
        for j in range(n):
            if i != j and j != k and k != i:
                if field[i][k] + field[k][j] == field[i][j]:
                    field_2[i][j] = 0
                if field[i][k] + field[k][j] < field[i][j]:
                    err = 1

if err == 0:
    ans = 0
    for i in range(n):
        for j in range(n):
            ans += field[i][j] * field_2[i][j]
    print(ans//2)
else:
    print(-1)

Solution (Python):
import sys
input=sys.stdin.readline
import copy
 
def WarshallFloyd(Map):
    Dist=copy.deepcopy(Map)
    l=len(Dist)
    for k in range(l):
        for i in range(l):
            for j in range(l):
                Dist[i][j]=min(Dist[i][j],Dist[i][k]+Dist[k][j])
    return Dist

def solve(n,A):
    B=WarshallFloyd(A)
    for i in range(n):
        for j in range(n):
            if A[i][j]>B[i][j]:
                return -1
    for k in range(n):
        for i in range(n):
            if i==k:
                continue
            for j in range(n):
                if j==k:
                    continue
                if A[i][j]==A[i][k]+A[k][j]:
                    B[i][j]=0; B[j][i]=0
    ret=0
    for i in range(n):
        ret+=sum(B[i])
    ret//=2
    return ret

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

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

class UnionFind():
    def __init__(self,n):
        self.par = [i for i in range(n)]
        self.rank = [0] * n

    def root(self,x):
        if x == self.par[x]:
            return x
        r = self.root(self.par[x])
        self.par[x] = r
        return r

    def unit(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y: return False
        if self.rank[x] < self.rank[y]: x, y= y, x,
        if self.rank[x] == self.rank[y]: self.rank[x] += 1
        self.par[y] = x
        return True

def A():
    n, a = II(), II()
    print(n * n - a)
    return


def B():
    _ = II()
    k = II()
    x = LI()
    ans = 0
    for xi in x:
        ans += min(xi, k - xi)
    print(ans * 2)
    return


def C():
    a, b, c, d, e, F = LI()
    ans = [min(a,b)*100, 0]
    for ai in range(F // (100 * a) + 1):
        for bi in range((F - 100 * ai * a) // (100 * b) + 1):
            if ai == bi == 0:
                continue
            ab = ai * 100 * a + bi * 100 * b
            for ci in range((F - ab) // c + 1):
                for di in range((F - ab - ci * c) // d + 1):
                    if (ai * a + bi * b) * e < ci * c + di * d:
                        continue
                    if ans[1] / ans[0] < (ci * c + di * d) / (ab + ci * c + di * d):
                        ans = [ab + ci * c + di * d, ci * c + di * d]
    print(*ans)
    return


def D():
    n = II()
    edg = LIR(n)

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

    for x in range(n):
        for y in range(x + 1, n):
            for k in range(n):
                if x == k or y == k:
                    continue
                if edg[x][y] > edg[x][k] + edg[k][y]:
                    print(-1)
                    return
                if edg[x][y] == edg[x][k] + edg[k][y]:
                    ans -= edg[x][y]
                    break

    print(ans)

    return


if __name__ == '__main__':

    D()

Solution (Python):
import sys
input = sys.stdin.readline
def main():
    INF = float('inf')
    N = int(input())
    d = [[int(x) for x in input().split()]for _ in range(N)]
    ans = 0
    flag = True
    for i in d:
        ans += sum(i)
    ans //= 2
    max_d = 0
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if(i==j or j==k or i==k or d[i][j]==INF):continue
                max_d = max(max_d,d[i][j])
                if(d[i][j]==d[i][k] + d[k][j]):
                    ans -= d[i][j]
                    d[i][j] = INF
                    d[j][i] = INF
                elif(d[i][j]>d[i][k] + d[k][j]):
                    flag = False
    print(ans if (ans >= max_d)and flag else -1)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

import copy

def warshall_floyd(d):
    
    arr = copy.deepcopy(d)
    n = len(arr)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                arr[i][j] = min(arr[i][j], arr[i][k] + arr[k][j])
    return arr

def main(): 
    N = II()
    tizu = []
    for _ in range(N):
        tizu.append(LI())

    min_road = warshall_floyd(tizu)
    for i in range(N):
        for j in range(N):
            if tizu[i][j] > min_road[i][j]:  
                print(-1)
                return

    
    
    

    for keiyu in range(N):
        for i in range(N):
            if i == keiyu: continue
            for j in range(N):
                if j == keiyu: continue
                if tizu[i][j] == tizu[i][keiyu] + tizu[keiyu][j]:
                    min_road[i][j] = 0
                    min_road[j][i] = 0
    
    ans = 0
    for i in range(N):
        ans += sum(min_road[i])

    print(ans//2)


main()

Solution (Python):
N=int(input())
A=[list(map(int,input().split())) for i in range(N)]
r=0
for i,aa in enumerate(A):
    for j,a in enumerate(aa[i+1:]):
        f=1
        j+=i+1
        for k in range(N):
            if k==i or k==j:
                continue
            if a>A[i][k]+A[k][j]:
                f=r=-1
                break
            if a==A[i][k]+A[k][j]:
                f=0
                break
        if f==1:
            r+=a
        elif f==-1:
            break
    if r<0:
        break
print(r)

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

def judge() :
    s = 0
    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][k] + A[k][j] < A[i][j] :
                    return -1
                elif A[i][k] + A[k][j] == A[i][j] :
                    s += A[i][j]
                    break
    tot = 0
    for i in range(N) :
        for j in range(i + 1, N) :
            tot += A[i][j]
    return tot - s
    
print(judge())

Solution (Python):



import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline


n = int(input())
d = [[int(i) for i in readline().split()] for i in range(n)]
e = []
for i in range(n):
    for j in range(i+1,n):
        e.append((d[i][j],i,j))

e.sort()

ans = 0
for c,i,j in e:
    eq = 0
    for k in range(n):
        dk = d[k][i] + d[k][j]
        if dk < c:
            print(-1)
            exit()
        elif dk == c and k != i and k != j:
            eq = 1
    if eq: continue
    else: ans += c

            
print(ans)

Solution (Python):
inf = float("inf")
N = int(input())
A = []
for _ in range(N):
    a = [int(s) for s in input().split()]
    A.append(a)
d = [a[:] for a in A]
ans = 0
for i in range(N - 1):
    for j in range(i + 1, N):
        dmin = min([inf] + [d[i][k] + d[k][j]
                            for k in range(N) if k not in (i, j)])
        if d[i][j] > dmin:
            print(-1)
            exit()
        if d[i][j] != dmin:
            ans += d[i][j]
print(ans)

Solution (Python):
n=int(input())
INF=float("inf")
g=[[INF]*n for _ in range(n)]
ans=0
for i in range(n):
	for j,c in enumerate(map(int,input().split())):
		if i!=j:
			g[i][j]=c
for i in range(n):
	for j in range(i):
		m=min(a+b for a,b in zip(g[i],g[j]))
		if g[i][j]>m:
			print(-1)
			exit()
		if g[i][j]<m:
			ans+=g[i][j]
print(ans)

Solution (Python):

import sys
INF = float("inf")


class Graph(object):
    def __init__(self, N):
        self.N = N
        self.V = list(range(N))
        self.E = [[] for _ in range(N)]

    def add_edge(self, edge):
        """辺を加える。edgeは(始点, 終点、重み)からなるリスト
        重みがなければ、重み1とする。
        """
        if len(edge) == 2:
            edge.append(1)
        elif len(edge) != 3:
            print("error in add_edge")
            pass

        s, t, w = edge
        self.E[s].append([t, w])
        self.E[t].append([s, w])  

        pass

    def remove_edge(self, edge):
        if len(edge) == 2:
            edge.append(1)
        elif len(edge) != 3:
            print("error in add_edge")
            pass

        s, t, w = edge
        for tt, ww in self.E[s]:
            if tt == t:
                break
        if tt == t:
            self.E[s].remove([t, ww])
            self.E[t].remove([s, ww])
        pass


def Warshall_Floyd(g: Graph):
    """ワーシャルフロイド法により、全節点対の最短距離を求める。O(V^3)
    https://ja.wikipedia.org/wiki/%E3%83%AF%E3%83%BC%E3%82%B7%E3%83%A3%E3%83%AB%E2%80%93%E3%83%95%E3%83%AD%E3%82%A4%E3%83%89%E6%B3%95
    """
    N = g.N
    dist = [[INF]*N for _ in range(N)]
    for from_, toweights in enumerate(g.E):
        for to_, w in toweights:
            dist[from_][to_] = w

    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


def solve(N: int, A: "List[List[int]]"):

    g = Graph(N)
    for i in range(N):
        for j in range(i+1, N):
            g.add_edge([i, j, A[i][j]])

    B = Warshall_Floyd(g)

    counter = 0
    for i in range(N):
        for j in range(i+1, N):
            if B[i][j] < A[i][j]:
                print(-1)
                return

            flag = True
            for k in range(N):
                if B[i][j] == B[i][k]+B[k][j]:
                    flag = False
            if flag == True:
                counter += B[i][j]
    print(counter)

    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):
INF = float('inf')
N = int(input())
a = [list(map(int, input().split())) for i in range(N)]
b = [[INF] * N for i in range(N)]
for k in range(N):
    for i in range(N):
        for j in range(N):
            b[i][j] = min(b[i][j], a[i][k] + a[k][j])
for i in range(N):
    for j in range(N):
        if b[i][j] < a[i][j]:
            print(-1)
            quit()
ans = 0
for i in range(N-1):
    for j in range(i+1, N):
        flag = 1
        for k in range(N):
            if a[i][j] == a[i][k] + a[k][j] and k != i and k != j:
                flag = 0
                break
        if flag: ans += a[i][j]
print(ans)

Solution (Python):
N = int(input())
A = [[float('inf')]*(N+1)] + [[float('inf')]+list(map(int,input().split())) for _ in range(N)]
test = [[float('inf')]*(N+1) for _ in range(N+1)]
def main():
    for i in range(1,N+1):
        for j in range(1,N+1):
            for k in range(1,N+1):
                test[i][j] = min(test[i][j],A[i][j],A[i][k] + A[k][j])
    ans = 0
    if test == A:
        for i in range(1,N+1):
            for j in range(i+1,N+1):
                flag = True
                for k in range(1,N+1):
                    if A[i][j] == A[i][k] + A[j][k] and k != i and k != j:
                        flag = False
                        break
                if flag:
                    ans += A[i][j]    
        print(ans)                
    else:
        print(-1)
main()

Solution (Python):
N = int(input())
G = [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 G[i][k] + G[k][j] < G[i][j]:
                print(-1)
                exit()

Need = [[True] * N for i in range(N)]
for k in range(N):
    for i in range(N):
        for j in range(N):
            if (i == k) or (j == k):
                continue
            if G[i][k] + G[k][j] == G[i][j]:
                Need[i][j] = False

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

print(ans // 2)

Solution (Python):
import sys
import numpy as np
input = sys.stdin.readline
n = int(input())
G = np.array([list(map(int, input().split())) for _ in range(n)], dtype=float)
G2 = G
for i in range(n):
    G2[i,i] = np.inf
use = np.ones((n,n),dtype=bool)
impossible = np.zeros((n,n),dtype=bool)
for w in range(n):
    D = sum(np.meshgrid(G2[w], G2[w]))
    use &= ~(G == D)
    impossible |= G > D
if impossible.sum() > n:
    print(-1)
else:
    print(int(np.sum(G[use]) / 2))

Solution (Python):
import sys
import numpy as np
input = sys.stdin.readline
n = int(input())
G = np.array([list(map(int, input().split())) for _ in range(n)], dtype=float)
use = np.ones((n,n),dtype=bool)
impossible = np.zeros((n,n),dtype=bool)
for w in range(n):
    D = sum(np.meshgrid(G[w], G[w]))
    D[w] = np.inf
    D[:,w] = np.inf
    use &= ~(G == D)
    impossible |= G > D
if impossible.any():
    print(-1)
else:
    print(int(np.sum(G[use]) / 2))

Solution (Python):
def main():
    N = int(input())
    A = [list(map(int, input().split())) for _ in range(N)]
    ans = 0
    for i in range(N):
        A[i][i] = float('INF')
    for i in range(N):
        for j in range(i):
            if i == j:
                A[i][j] = float('INF')
                continue
            b = min(map(sum, zip(A[i], A[j])))
            if A[i][j] > b:
                print(-1)
                return
            if b > A[i][j]:
                ans += A[i][j]
    print(ans)


main()

Solution (Python):
from subprocess import*
call(('python3','-c',"""
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]*all(t[j]<t+h[j])for i,t in enumerate(h)for j in range(i)))*(f==g).all()or-1)
"""))

Solution (Python):
import sys
from itertools import permutations, combinations

N=input()
d=[ [ float("inf") for j in range(N+1) ] for i in range(N+1) ] 

KOUHO=[]
for i in range(N):
	L=map(int, sys.stdin.readline().split())
	d[i][i]=0
	for j in range(i+1,N):
		length=L[j]
		d[i+1][j+1]=length
		d[j+1][i+1]=length
		KOUHO.append( (length,i+1,j+1))


ans=0
for c,i,j in KOUHO:
	for k in range(1,N+1):
		if k==i or k==j: continue
		a=d[i][k]
		b=d[j][k]
		if a+b==c:
			break
		elif a+b<c:
			print -1
			quit()
	else:
		ans+=c

print ans

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

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

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

print(ans)

Solution (Python):
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]*all(t[j]<t+h[j])for i,t in enumerate(h)for j in range(i)))*(f==g).all()or-1)

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

MP3=[[-1]*N for _ in range(N)]


for k in range(N):
    for i in range(N):
        for j in range(N):
            cand = MP2[i][k] + MP2[k][j]
            if cand <= MP2[i][j]:
                MP2[i][j] = cand
                if (i != k and j != k):
                    MP3[i][j] = k

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

checked=set()

res = set()
def dfs(i,j):
    k = MP3[i][j]
    if k == -1:
        k = i
    if (i,j) in checked:
        return
    checked.add((i,j))
    if (i == k or j == k):
        if i < j:
            res.add((i,j))
    else:
        dfs(i,k)
        dfs(k,j)

for i in range(N):
    for j in range(N):
        dfs(i,j)

ressum = 0
for i,j in res:
    ressum += MP[i][j]




print(ressum)

Solution (Python):
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):
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)
a=0
for i,t in enumerate(h):
  for j in range(i):
    a+=t[j]*(t[j]<t+h[j]).all()
print(int(a)*(f==g).all()or-1)

Solution (Python):
import numpy as np



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

from collections import* 
from fractions import gcd
from functools import* 
from itertools import* 
from operator import mul,itemgetter
from bisect import* 
from heapq import* 
from math import factorial,pi
from copy import deepcopy
import sys
input=sys.stdin.readline  
sys.setrecursionlimit(10**8)

def main():
    n=int(input())
    grid=[list(map(int,input().split()))for i in range(n)]
    p=floyd_warshall(csgraph=csr_matrix(grid))
    q=[list(i) for i in p]
    
    if q!=grid:
        print(-1)
    else:
        for i in range(n):
            p[i][i]=float("inf")
        ans=0
        for i in range(n):
            for j in range(i):
                if p[i][j]<min(np.array(p[i])+np.array(p[j])):
                    
                    ans+=p[i][j]
        print(int(ans))

if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np



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

from collections import* 
from fractions import gcd
from functools import* 
from itertools import* 
from operator import mul,itemgetter
from bisect import* 
from heapq import* 
from math import factorial,pi
from copy import deepcopy
import sys

sys.setrecursionlimit(10**8)

def main():
    n=int(input())
    grid=[list(map(int,input().split()))for i in range(n)]
    p=floyd_warshall(csgraph=csr_matrix(grid))
    q=[list(i) for i in p]
    
    if q!=grid:
        print(-1)
    else:
        for i in range(n):
            p[i][i]=float("inf")
        ans=0
        for i in range(n):
            for j in range(i):
                if i==j:
                    continue
                if p[i][j]<min(np.array(p[i])+np.array(p[j])):
                    
                    ans+=p[i][j]
        print(int(ans))

if __name__ == '__main__':
    main()

Solution (Python):
N=int(input())
A=[]
for i in range(N):
    a=list(map(int,input().split()))
    A.append(a)
ans=0
for i in range(N):
    for j in range(N):
        ans+=A[i][j]
        for k in range(i+1,N):
            if A[i][j]+A[j][k]<A[i][k]:
                print(-1)
                quit()
ans//=2
for i in range(N):
    for k in range(i+1,N):
        for j in range(N):
            if i==j or j==k:
                continue
            if A[i][j]+A[j][k]==A[i][k]:
                ans-=A[i][k]
                break

print(ans)

Solution (Python):
N = int(input())
As =[list(map(int, input().split())) for _ in range(N)]
flag1 = False
ans = 0
for i in range(N):
    for j in range(i+1, N):
        flag2 = True
        for k in range(N):
            if k == i or k == j:
                continue
            if As[i][k]+As[k][j] < As[i][j]:
                flag1 = True
                break
            elif As[i][k]+As[k][j] == As[i][j]:
                flag2 = False
        if flag2:
            ans += As[i][j]
        if flag1:
            break
    if flag1:
        break
if not flag1:
    print(ans)
else:
    print(-1)

Solution (Python):
import sys

import numpy as np

sys.setrecursionlimit(10000)
INF = float('inf')

N = int(sys.stdin.readline())
A = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
A = np.array(A, dtype=float) + np.diag([np.inf] * N)

useless = np.zeros((N, N), dtype=bool)
impossible = np.zeros((N, N), dtype=bool)
for via in range(N):
    
    R = sum(np.meshgrid(A[via], A[via]))
    useless |= R == A
    impossible |= R < A

if (impossible ^ np.eye(N, dtype=bool)).sum():
    print(-1)
else:
    print(int(A[~useless].sum() // 2))

Solution (Python):
import itertools
import sys

sys.setrecursionlimit(10000)
INF = float('inf')

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


def solve():
    
    useless = [[0] * N for _ in range(N)]

    
    for st, en in itertools.combinations(range(N), r=2):
        for via in range(N):
            if via in [st, en]:
                continue
            if A[st][via] + A[via][en] < A[st][en]:
                return -1
            if A[st][via] + A[via][en] == A[st][en]:
                useless[st][en] = True
                useless[en][st] = True
    return sum([A[s][e] for s, e in itertools.product(range(N), repeat=2) if not useless[s][e]]) // 2


print(solve())

Solution (Python):
import sys

import numpy as np

sys.setrecursionlimit(10000)
INF = float('inf')

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

A = np.array(A, dtype=float)

useless = np.zeros((N, N), dtype=bool)
impossible = np.zeros((N, N), dtype=bool)
for via in range(N):
    
    R = sum(np.meshgrid(A[via], A[via]))
    R[via] = np.inf
    R[:, via] = np.inf
    useless |= R == A
    impossible |= R < A
if impossible.sum():
    print(-1)
else:
    print(int(A[~useless].sum() // 2))

Solution (Python):






import numpy as np
N = int(input())
A = [[int(x) for x in input().split()] for _ in range(N)]

edge = []

for i in range(N):
  for j in range(i):
    edge.append((A[i][j],j,i))
edge.sort()

INF = 10**18
dist = np.full((N,N),INF,dtype=np.int64) - np.eye(N,dtype=np.int64)*INF

answer = 0
for d,x,y in edge:
  if d > dist[x,y]:
    answer = -1
    break
  if d == dist[x,y]:
    continue
  
  answer += d
  dist[x,y] = d
  dist[y,x] = d
  
  
  dist_use_xy = np.add.outer(dist[:,x], dist[:,y]) + d
  dist = np.minimum(dist,np.minimum(dist_use_xy,dist_use_xy.T))
  
print(answer)

Solution (Python):
N = int(input())
li = [ [ int(it) for it in input().split() ]  for i in range(N) ]
iru = [[1]*N for i in range(N)] 

Flag = True
s = 0
for i in range(N):
  for j in range(N):
    for k in range(N):
      if ( i==j or j==k or k==i ):
        continue
      if ( li[i][j] > li[i][k] + li[k][j] ):
        Flag = False
      if ( li[i][j] == li[i][k] + li[k][j] ):
        iru[i][j]=0
for i in range(N):
  for j in range(N):
    if (i<j):
      s += iru[i][j] * li[i][j]

print ( s if Flag else -1 )

Solution (Python):
n = int(input())
import numpy as np
a = np.array([list(map(int,input().split())) for _ in range(n)])
ans = 0
for i in range(n):
    a[i][i] = 10**9+1
for i in range(n):
    for j in range(i,n):
        if i==j:
            continue
        dp = np.min(a[i]+a[j])
        if a[i][j]<dp:
            ans += a[i][j]
        elif a[i][j]>dp:
            print(-1)
            exit()
print(ans)

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(i,n):
        if i==j:
            continue
        dp = 10**9+1
        for k in range(n):
            if k==j or k==i:
                continue
            dp = min(dp,a[i][k]+a[k][j])
        if a[i][j]<dp:
            ans += a[i][j]
        elif a[i][j]>dp:
            print(-1)
            exit()
print(ans)

Solution (Python):
from itertools import accumulate
from math import*
from collections import deque
from collections import defaultdict
from itertools import permutations
from heapq import*
from collections import Counter
from itertools import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = 10**18
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

n = int(input())
l = [list(map(int,input().split())) for _ in range(n)]
ans = 0
for j in range(n):
    for i in range(n):
        f = True
        for k in range(n):
            if l[i][j] > l[i][k]+l[k][j]:
                print(-1)
                exit()
            if l[i][j] == l[i][k] + l[k][j] and i !=k and k != j:
                f = False
        if f:
            ans += l[i][j]
print(ans//2)

Solution (Python):
import numpy as np
N = int(input())
A = np.array([list(map(int,input().split())) for _ in range(N)],dtype=np.int64)

INF = 10**9+10
E = np.zeros(((N*(N-1))//2,3),dtype=np.int64)
k = 0
for i in range(N):
    for j in range(i+1,N):
        E[k,0] = A[i][j]
        E[k,1] = i
        E[k,2] = j
        k += 1
E = E[E.argsort(0)[:,0]]
B = np.ones((N,N),dtype=np.int64)*INF
ans = 0
for l,i,j in E:
    l_min = np.min(B[i]+B[j])
    if l > l_min:
        ans = -1
        break
    elif l < l_min:
        ans += l
    B[i][j] = l
    B[j][i] = l
print(ans)

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

INF = 10**10
E_list = []
for i in range(N):
    for j in range(i+1,N):
        E_list.append([A[i][j],i,j])
E_list.sort()
B = [[INF]*N for _ in range(N)]
ans = 0
for l,i,j in E_list:
    l_min = INF
    for k in range(N):
        l_min = min(l_min,B[i][k]+B[k][j])
    if l > l_min:
        ans = -1
        break
    elif l < l_min:
        ans += l
    B[i][j] = l
    B[j][i] = l
print(ans)