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

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

import numpy as np

n = int(readline())
graph = np.array([list(map(int, readline().split())) for _ in range(n)])
inf = 10 ** 10
ans = 0
for i in range(n):
    graph[i][i] = inf
for i in range(n):
    for j in range(i + 1, n):
        v = np.min(graph[i] + graph[j])
        if graph[i][j] > v:
            print(-1)
            exit()
        elif graph[i][j] < v:
            ans += graph[i][j]
print(ans)

Solution (Python):
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
import copy
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]

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

def warshall_floyd(d,d2):
    

    for k in range(n):
        for i in range(n):
            for j in range(n):
                if i==k or j==k:
                    continue
                if d[i][j]>d[i][k] + d[k][j]:
                    print(-1)
                    quit()
                if d[i][j]==d[i][k] + d[k][j]:
                    d2[i][j]=1
                
    return d


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

cnt=0
for i in range(n):
    for j in range(n):
        d[i][j]=a[i][j]
        cnt+=a[i][j]
for i in range(n):
    d[i][i] = 0 


d2 = [[0 for i in range(n)] for i in range(n)]
warshall_floyd(d,d2)

cnt=0
for i in range(n):
    for j in range(n):
        if d2[i][j]==0:
            cnt+=d[i][j]
print(cnt//2)

Solution (Python):
def warshall_floyd(G, n):
    global c
    for i in range(n):
        for j in range(n):
            b = 1
            for k in range(n):
                if j == k or i == k:
                    continue
                if G[i][j] == G[i][k] + G[k][j]:
                    b = 0
                elif G[i][j] > G[i][k] + G[k][j]:
                    print(-1)
                    exit()
            if b == 1:
                c += G[i][j]

n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
c = 0
warshall_floyd(a, n)
print(c // 2)

Solution (Python):
N = int(input())
A = [list(map(int, input().split())) for i in range(N)]
flag = True
Sum = 0 
for i in range(N-1):
    for j in range(i+1, N):
        f = True
        for k in range(N):
            if k == i or k == j:
                continue
            if A[i][k] + A[k][j] < A[i][j]:
                flag = False
            elif A[i][k] + A[k][j] == A[i][j]:
                f = False
        if f:
            Sum += A[i][j]
if flag:
    print(Sum)
else:
    print(-1)

Solution (Python):

def warshall_floyd(d,ans):
    
    flag=True
    for i in range(n):
        for j in range(n):
            x=d[i][j]
            y=float('inf')
            for k in range(n):
                if k!=i and k!=j:
                    y = min(d[i][k] + d[k][j],y)
            if x==y:
                ans-=y
            elif x<y:
                continue
            else:
                flag=False
                break

    return flag,ans


n=int(input())

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


a1,a2=warshall_floyd(d,ans)

if a1:
    print(a2//2)
else:
    print(-1)

Solution (Python):
def warshall_floyd(e, n):
    d = [[e[j][i] for i in range(n)] for j in range(n)]
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if d[i][k] + d[k][j] < d[i][j]:
                    d[i][j] = d[i][k] + d[k][j]
    
    return d

n = int(input())
grid = [list(map(int, input().split())) for i in range(n)]
dgrid = warshall_floyd(grid, n)

ans = [[0 for i in range(n)] for j in range(n)]
for i in range(n):
    for j in range(n):
        if grid[i][j] != dgrid[i][j]:
            print(-1)
            exit()

ans = 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 grid[i][k] + grid[k][j] == grid[i][j]:
                dgrid[i][j] = 0

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

Solution (Python):
from copy import deepcopy

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

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

ans = 0
for u in range(N):
    if ans < 0:
        break
    for v in range(N):
        if graph[u][v] < A[u][v]:
            ans = -1
            break
            
        flg = True
        for w in range(N):
            if w == u or w == v:
                continue
            flg &= graph[u][v] < graph[u][w] + graph[w][v]
        
        if flg:
            ans += graph[u][v]

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

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

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

print(cnt)

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

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

print(cnt // 2)

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

ans = 0
cannot = 0
for i in range(n-1):
  for j in range(i+1,n):
    detour = min([A[i][k] + A[k][j] for k in range(n) if k!=i and k!=j]+[10**18])
    if detour<A[i][j]:
      cannot = 1
    elif detour>A[i][j]:
      ans += A[i][j]
if cannot:
  print(-1)
else:
  print(ans)

Solution (Python):


import copy
import sys
input = sys.stdin.readline
n = int(input()) 

graph = []
for _ in range(n):
    row = [int(i) for i in input().split()]
    graph.append(row)

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

print(ans // 2)

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

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

flag = False
for i in range(n):
    for j in range(n):
        if b[i][j] < a[i][j]:
            ans = -1
            flag = True
            break
        if b[i][j] == a[i][j]:
            for k in range(n):
                if k == i or k == j: continue
                if b[i][j] == b[i][k] + b[k][j]: break
            else:
                ans += b[i][j]
    if flag: break

ans //= 2
print(ans)

Solution (Python):
import heapq
import math
class Graph:
    def __init__(self,v,adj,w_v = None):
        super().__init__()
        self.v = v
        self.w_e = [{} for _ in [0]*self.v]
        self.neighbor = [[] for _ in [0]*self.v]
        
        self.w_v = w_v

        for i, adj_i in enumerate(adj):
            for j, w in enumerate(adj_i):
                self.w_e[i][j] = w 
                self.neighbor[i].append(j)

    def dijkstra(self,v_n):
        d = [10**18]*self.v
        d[v_n] = 0
        prev = [-1]*self.v

        queue = []
        for i,d_i in enumerate(d): heapq.heappush(queue,(d_i,i))
        
        while len(queue)>0:
            d_u,u = queue.pop()
            if d[u]<d_u :continue
            for v in self.neighbor[u]:
                alt = d[u]+self.w_e[u][v]
                if d[v]>alt:
                    d[v] = alt
                    prev[v] = u
                    heapq.heappush(queue,(alt,v))

        return d,prev
    
    def WarshallFloyd(self):
        d = [[10**18]*self.v for _ in [0]*self.v]
        for i in range(self.v):
            for j in self.neighbor[i]:
                d[i][j] = self.w_e[i][j]
                
        for i in range(self.v):
            for j in range(self.v):
                for k in range(self.v):
                    check = d[i][k] + d[k][j]
                    if d[i][j] > check:
                        d[i][j] = check
        return d

def main():
    n = int(input())

    a = [[int(t)for t in input().split()]for _ in [0]*n]

    g = Graph(n,a)
    a_check = g.WarshallFloyd()

    s = 0
    for i in range(n):
        for j in range(n):
            a_ij = a[i][j]
            if a_ij != a_check[i][j]:
                print(-1)
                return
            if sum([a_ij == a[i][k] + a[k][j] for k in range(n) if k != i and k != j]) == 0:
                s+=a_ij
    print(s//2)

if __name__ == "__main__":
    main()

Solution (Python):
def warshall_floyd(G):
    import copy
    ret = copy.deepcopy(G)
    for k in range(N):
        for i in range(N):
            for j in range(N):
                ret[i][j] = min(ret[i][j], ret[i][k] + ret[k][j])
    return ret


N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
W, ans = warshall_floyd(A), 0
if A == W:
    for i in range(N):
        for j in range(N):
            if sum([A[i][j] == A[i][k] + A[k][j] for k in range(N) if k != i and k != j]) == 0:
                ans += A[i][j]
    print(ans // 2)
else:
    print(-1)

Solution (Python):
def solve(V, G):
    ans = 0
    for i in range(V - 1):
        for j in range(i + 1, V):
            direct = G[i][j]
            for k in range(V):
                if k == i or k == j:
                    continue
                ind = G[i][k] + G[k][j]
                if direct > ind:
                    return -1
                elif direct == ind:
                    break
            else:
                ans += direct
    return ans


def main():
    V = int(input())
    G = [[int(i) for i in input().split()] for i in range(V)]
    print(solve(V, G))


if __name__ == "__main__":
    main()

Solution (Python):
import sys 
MOD = 10 ** 9 + 7
INF = 10**5
from collections import deque

def main():
    n = int(input())
    dist = []
    edge = []
    ans = 0
    for i in range(n):
        a = list(map(int,input().split()))
        dist.append(a)
        for j in range(n):
            if i < j:
                edge.append((a[j],i,j))
                ans += a[j]
    
    for k in range(n - 1):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j] ,dist[i][k] + dist[k][j])
    
    edge.sort(reverse = True,key = lambda x:x[0])
    for c,a,b in edge:
        if dist[a][b] < c:
            ans = -1
            break
        for i in range(n):
            if i != a and i != b:
                if c == dist[a][i] + dist[i][b]:
                    ans -= c
                    break
    print(ans)   

if __name__=='__main__':
    main()

Solution (Python):
from heapq import heappush, heappop
def main():
    N=int(input())
    road=[[float("inf") for _ in range(N)]for _ in range(N)]
    pq=[]
    ans=0
    for i in range(N):
        road[i][i]=0
        tmp=list(map(int,input().split()))
        for j in range(i+1,N):
            heappush(pq,(tmp[j],i,j))

    while pq:
        v=heappop(pq)
        d,i,j=v[0],v[1],v[2]
        tmp=road[i][j]
        for k in range(N):
            tmp=min(tmp,road[i][k]+road[k][j])
            if tmp==d:
                break
        if tmp>d:
            road[i][j]=d
            road[j][i]=d
            ans+=d
        elif tmp==d:
            road[i][j]=d
            road[j][i]=d
        else:
            print(-1)
            exit()
    print(ans)
main()

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

A = [[0]*N for i in range(N)]

for i in range(N):
    A[i] = list(map(int,input().split()))
B = [[A[i][j] for j in range(i+1,N)] for i in range(N-1)]



det = 0

for i in range(N-1):
    for j in range(i+1,N):
        for k in range(N):
            if A[i][j] > A[i][k] + A[k][j]:
                det = -1
                break
            elif i != k and j != k and A[i][j] == A[i][k] + A[k][j]:
                B[i][j-(i+1)] = 0
                
        
        if det == -1:
            break

    if det == -1:
        break

if det == 0:
    ans = 0
    for i in range(N-1):
        for j in range(i+1,N):
            ans += B[i][j-(i+1)]
else:
    ans = -1

print(ans)

Solution (Python):

import sys
try:
    from typing import List
except ImportError:
    pass


def solve(N: int, A: "List[List[int]]"):
    es = [
        (A[i][j], i, j)
        for i in range(N)
        for j in range(i)
    ]
    es.sort(reverse=True)
    ans = 0
    for d, i, j in es:
        for k in range(N):
            if k == i or k == j:
                continue
            nd = A[i][k] + A[k][j]
            if nd < d:
                print(-1)
                return
            if nd == d:
                break
        else:
            ans += d
    print(ans)


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):
N=int(input())
A=[[] for i in range(0,N)]
for i in range(0,N):
    A[i]=list(map(int,input().split()))

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

print(count//2)

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

def sol():
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d = A[i][k] + A[k][j]
                if d < A[i][j]:
                    return - 1

    ret = 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]:
                    break
            else:
                ret += A[i][j]

    return ret

print(sol())

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

def sol():
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d = A[i][k] + A[k][j]
                if d < A[i][j]:
                    return - 1

    INF = 10**18

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

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

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

    return ans

print(sol())

Solution (Python):
from collections import deque
import sys
input = lambda: sys.stdin.readline().rstrip()

N = int(input())

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

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

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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)]

sys.setrecursionlimit(1000000)
mod = 1000000007

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


if __name__ == "__main__":
    solve()

Solution (Python):

from copy import deepcopy
n = int(input())
a = [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])

b = deepcopy(a)
warshall_floyd(b, n)

flg = True
ans = 0
for i in range(n):
    for j in range(n):
        if b[i][j] < a[i][j]:
            flg = False
            break
        else:
            flg2 = True
            for k in range(n):
                if i == k or j == k:
                    continue
                elif b[i][j] == b[i][k] + b[k][j]:
                    flg2 = False
            ans += b[i][j] if flg2 else 0
                    
print(ans//2 if flg else -1)

Solution (Python):
"""from collections import *
from itertools import *
from bisect import *
from heapq import *

import math
from fractions import gcd"""
import sys
input = sys.stdin.readline
from heapq import*
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()
res = 0
for i in range(N-1):
    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]:
                break
        else:
            res += A[i][j]
print(res)

Solution (Python):
"""from collections import *
from itertools import *
from bisect import *
from heapq import *

import math
from fractions import gcd"""
from heapq import*
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()
res = 0
for i in range(N-1):
    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]:
                break
        else:
            res += A[i][j]
print(res)

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    
    from itertools import combinations, permutations
    
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    

    
    

    N=int(input())
    dp=[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 dp[i][j]>dp[i][k]+dp[k][j]:
                    print(-1)
                    exit()
    
    res = 0
    for i in range(N-1):
        for j in range(i+1, N):
            for k in range(N):
                if k==i or k == j:
                    continue
                if dp[i][j]==dp[i][k]+dp[k][j]:
                    break
            else:
                res += dp[i][j]
    print(res)


if __name__ == '__main__':
    main()

Solution (Python):
N, *L = map(int, open(0).read().split())
cost = []
for i,m in enumerate(zip(*[iter(L)]*N)):
  cost.append(list(m))
  cost[i][i] = 10**10
ans = 0
for i in range(N):
  for j in range(i):
    m = min(a+b for a, b in zip(cost[i],cost[j]))
    if m<cost[i][j]:
      print(-1)
      exit()
    if m>cost[i][j]:
      ans += cost[i][j]
print(ans)

Solution (Python):
N, *L = map(int, open(0).read().split())
cost = []
for m in zip(*[iter(L)]*N):
  cost.append(m)
ans = 0
for i in range(N):
  for j in range(i):
    for k in range(N):
      if k==i or k==j:
        continue
      if cost[i][j]>cost[i][k]+cost[k][j]:
        print(-1)
        import sys
        sys.exit()
      if cost[i][j]==cost[i][k]+cost[k][j]:
        break
    else:
      ans += cost[i][j]
print(ans)

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

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()
            if (i - j) * (j - k) * (k - i) and dist[j][k] == dist[j][i] + dist[i][k]:
                use[j][k] = False
                
ans = 0

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

print(ans)

Solution (Python):
import sys
input=lambda: sys.stdin.readline().rstrip()
n=int(input())
table=[]
for i in range(n):
  table.append([int(i) for i in input().split()])
Chk=True
for k in range(n):
  for i in range(n):
    for j in range(n):
      if table[i][k]+table[k][j]<table[i][j]:
        Chk=False
        table[i][j]=table[i][k]+table[k][j]

ans=0
for i in range(n):
  for j in range(i+1,n):
    C=True
    for k in range(n):
      if k==i or k==j:
        continue
      else:
        if table[i][k]+table[k][j]==table[i][j]:
          C=False
    if C:
      ans+=table[i][j]
print(ans if Chk else -1)

Solution (Python):
import sys
n = int(input())
road = [0]*n
for i in range(n):
  road[i] = [int(x) for x in input().split()]

road_judge = [[True]*n for i in range(n)]
for k in range(n):
  for i in range(n):
    for j in range(n):
      if road[i][j] > road[i][k]+road[k][j]:
        print(-1)
        sys.exit()
      if road[i][j] == road[i][k]+road[k][j] and i != k and j != k:
        road_judge[i][j] = False
ans = 0
for i in range(n):
  for j in range(n):
    if road_judge[i][j]:
      ans += road[i][j]
print(ans//2)

Solution (Python):
import sys

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

inf = float('inf')
for i in range(N):
	E[i][i] = inf

for k in range(N):
	for i in range(N):
		if i == k:
			continue
		for j in range(N):
			if k == j or i == j:
				continue
			direct = E[i][j]
			detour = E[i][k]+E[k][j]
			if direct == inf or detour == inf:
				continue

			if direct > detour:
				print(-1)
				sys.exit()

			elif direct == detour:		
				E[i][j] = inf
				E[j][i] = inf

answer = 0
for i in range(N):
	for j in range(N):
		if E[i][j] == inf:
			continue
		
		answer += E[i][j]

print(answer//2)

Solution (Python):
import math,itertools,bisect,sys,copy,queue
INF = 10**20

def LI(): return [int(x) for x in sys.stdin.readline().split()]

N = int(input())
A = [LI() for _ in range(N)]
a = copy.deepcopy(A)


for k in range(N):
    for i in range(N):
        for j in range(N):
            if A[i][j] == 0 or A[i][k] == 0 or A[k][j] == 0: continue
            if A[i][j] > A[i][k] + A[k][j]:
                print (-1)
                exit (0)
            if A[i][j] == A[i][k] + A[k][j]:
                A[i][j] = 0
print (sum(sum(A[i]) for i in range(N) )//2)

Solution (Python):
N = int(input())
A = [list(map(int,input().split())) for _ in range(N)]
cnt = 0
for i in range(N):
    for j in range(N):
        cnt += A[i][j]
flg = 0
B = [[0 for _ in range(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]:
                flg = -1
                break
            elif A[i][j]==A[i][k]+A[k][j] and A[i][k]*A[k][j]>0 and B[i][j]==0:
                cnt -= A[i][j]
                B[i][j]=1
        if flg==-1:break
    if flg==-1:break
if flg==-1:
    print(-1)
else:
    print(cnt//2)

Solution (Python):
import sys
import math
import fractions
import itertools
from collections import deque
import copy
import heapq
import bisect


def warshall_floyd(d):
    """
    d[i][l]がi→lへのコストを示す隣接行列
    結果としてd[i][l]はi→lへの最短コストになる。
    """
    info = copy.deepcopy(d)
    for i in range(len(info)):
        for l in range(len(info)):
            for k in range(len(info)):
                info[l][k] = min(info[l][k], info[l][i] + info[i][k])
    return info


MOD = float('inf')
INF = 10 ** 18 + 7
input = lambda: sys.stdin.readline().strip()

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

result = warshall_floyd(A)
ans = 0
for i in range(N):
    for l in range(N):
        if result[i][l] != A[i][l]:
            print(-1)
            sys.exit()
        ans += A[i][l]
        if A[i][l] == 0:
            A[i][l] = INF

ans /= 2
for i in range(N - 1):
    for l in range(i + 1, N):
        for k in range(N):
            if A[i][l] == A[i][k] + A[k][l]:
                ans -= A[i][l]
                break
print(int(ans))

Solution (Python):
import numpy as np

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


def solve():
    N = int(input())
    A = np.array([input().split() for _ in range(N)], dtype=np.int64).reshape(N, N)
    
    B = floyd_warshall(csr_matrix(A), directed=False)
    
    if np.any(B < A):
        print(-1)
        exit()
    
    np.fill_diagonal(B, np.inf)
    for i in range(N - 1):
        for j in range(i + 1, N):
            if B[i][j] == np.min(B[i] + B[j]):
                A[i][j] = A[j][i] = 0
    print(np.sum(A) // 2)


if __name__ == '__main__':
    solve()

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque
 
sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7
 
DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]
 
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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N = I()
    G = []
    for _ in range(N):
        a = LI()
        G.append(a)
    dp = copy.deepcopy(G)
    for i in range(N):
        for j in range(N):
            for k in range(N):
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
 
    if dp != G:
        print(-1)
        return
 
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if j == k:
                    continue
                if i == k:
                    continue
                if dp[i][k] == 0 or dp[i][j] == 0 or dp[j][k] == 0:
                    continue
                if dp[i][j] == dp[i][k] + dp[k][j]:
                    dp[i][j] = 0
                    dp[j][i] = 0
    cnt = 0
    for i in range(N):
        for j in range(N):
            cnt += dp[i][j]
    print(cnt // 2)
main()

Solution (Python):
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix

import numpy as np

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

g = csr_matrix(a)
dist = floyd_warshall(g)

if (dist == a).all():
    sm = a.sum()
    sm //= 2

    INF = 10 ** 18 + 1
    for i in range(n):
        a[i, i] = INF

    for u in range(n):
        for v in range(u + 1, n):
            mn = np.min(a[u] + a[v])
            if mn == a[u, v]:
                sm -= a[u, v]

    print(sm)

else:
    print(-1)