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):
def examD():
    
    def warshall_floyd(n, d):
        
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j])
        return d
    N = I()
    A = [LI() for _ in range(N)]
    Dist = [[0]*N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            a, b, r = i, j, A[i][j]
            Dist[a][b] = r
    D = warshall_floyd(N,Dist)
    ans = 0
    for i in range(N):
        for j in range(N):
            cur = D[i][j]
            if i==j:
                continue
            if cur<A[i][j]:
                print(-1)
                return
            if cur==A[i][j]:
                flag = True
                for k in range(N):
                    if k==i or k==j:
                        continue
                    if cur==D[i][k]+D[k][j]:
                        flag = False
                if flag:
                    ans += cur
    print(ans//2)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examD()

"""

"""

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

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

            if edges[i][j] > edges[i][k] + edges[k][j]:
                print(-1)
                exit()
            elif edges[i][j] == edges[i][k] + edges[k][j]:
                need_of_routes[i][j] = False

count = 0
for i in range(n):
    for j in range(n):
        if need_of_routes[i][j]:
            count += edges[i][j]

print(count//2)

Solution (Python):
N = int(input())
dic = [0]*N
dist = [[0]*N for i in range(N)]
for i in range(N):
  dic[i] = [int(c) for c in input().split()]
  for j in range(N):
    dist[i][j] = dic[i][j]
  dic[i][i] = float('inf')

ans = 0
for i in range(N):
  for j in range(i):
    d = min(a+b for a, b in zip(dic[i],dic[j]))
    if d<dic[i][j]:
      print(-1)
      exit()
    elif d>dic[i][j]:
      ans += dic[i][j]
print(ans)

Solution (Python):
N = int(input())
dic = [0]*N
dist = [[float('inf')]*N for i in range(N)]
for i in range(N):
  dic[i] = [int(c) for c in input().split()]
  for j in range(N):
    dist[i][j] = dic[i][j]
ans = 0
log = []
for k in range(N):
  for i in range(N-1):
    for j in range(i+1,N):
      dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])
for i in range(N-1):
  for j in range(i+1,N):
    if dist[i][j]<dic[i][j]:
      print(-1)
      import sys
      sys.exit()
    flag = False
    for k in range(N):
      if k==i or k==j:
        continue
      if dist[i][j] == dist[i][k]+dist[k][j]:
        flag = True
    if flag:
      continue
    ans += dic[i][j]
print(ans)

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

def main():
    N = int(input())
    edge = [list(map(int,input().split())) for _ in range(N)]
    for i in range(N):
        edge[i][i] = 10**10
        
    ans = 0
    for i in range(N):
        for j in range(i):
            d = min(a+b for a,b in zip(edge[i],edge[j]))
            if edge[i][j] > d:
                print(-1)
                exit()
            elif edge[i][j] < d:
                ans += edge[i][j]

    print(ans)    

if __name__ == "__main__":
    main()

Solution (Python):
from collections import defaultdict
N = int(input())
cost = [[0]*N for i in range(N)]
dist = [[0]*N for i in range(N)]
log = defaultdict(int)
for i in range(N):
  inf = [int(c) for c in input().split()]
  for j in range(N):
    cost[i][j] = inf[j]
for i in range(N):
  for j in range(i+1,N):
    m = float('inf')
    for k in range(N):
      if cost[i][j]>=cost[i][k]+cost[k][j]:
        m = min(m,cost[i][k]+cost[k][j])
        if k != i and k!= j:
          log[(min(i,j),max(i,j))] = 1
    dist[i][j] = m
    dist[j][i] = m
ans = 0
for i in range(N):
  for j in range(i+1,N):
    flag = False
    if dist[i][j]<cost[i][j]:
      print(-1)
      flag = True
      break
    elif log[(i,j)]==0:
      ans += cost[i][j]
  if flag:
    break
else:
  print(ans)

Solution (Python):











import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log 
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    
    def warshall_floyd(d, 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])
    
    N=I()
    A=LLIN(N)
    d=deepcopy(A)
    warshall_floyd(d, N)

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

    ans = 0
    for a,i,j in edge:
        if d[i][j]<a:
            print(-1)
            return
        need = True
        for k in range(N):
            if k in (i,j):
                continue
            if a==d[i][k]+d[k][j]:
                need = False
                break
        if need:
            ans += a
    print(ans)
        
if __name__ == '__main__':
    main()

Solution (Python):
import sys
from copy import deepcopy
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

def warshall_floyd(d):
    
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d
st = deepcopy(lst1)
st = warshall_floyd(st)
ans = 0
for i in range(n):
    for j in range(i+1,n):
        if lst1[i][j] > st[i][j]:
            print(-1)
            exit()
        elif lst1[i][j]==st[i][j]:
            
            res = [0]*n
            for k in range(n):
                res[k] += lst1[i][k] + lst1[j][k]
            res[i] = -1
            res[j] = -1
            if any([res[k]==lst1[i][j] for k in range(n)]):
                continue
            else:
                ans += lst1[i][j]
        else:
            ans += lst1[i][j]

print(ans)

Solution (Python):
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
INF = 10 ** 9
A = np.array([lr() for _ in range(N)])
np.fill_diagonal(A, INF)
answer = 0
for i in range(N-1):
    for j in range(i+1, N):
        detour = np.min(A[i]+A[j])
        if detour > A[i, j]:
            answer += A[i, j]
        elif detour < A[i, j]:
            print(-1)
            exit()

print(answer)

Solution (Python):
import sys
input = sys.stdin.readline
n = int(input())
dist = [list(map(int,input().split())) for i in range(n)]
ans = 0
for arr in dist:
  ans += sum(arr)

for i in range(n):
  for j in range(n):
    for k in range(n):
      if i != j and j != k and k != i:
        if dist[i][k]+dist[k][j] == dist[i][j] and dist[i][k] != 0 and dist[k][j] != 0:
          ans -= dist[i][j]
          break
        elif dist[i][k]+dist[k][j] < dist[i][j] and dist[i][k] != 0 and dist[k][j] != 0:
          print(-1)
          exit()
print(ans//2)

Solution (Python):
def warshall(d, n):
    e = copy.deepcopy(d)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                
                if i == k or k == j:
                    continue
                if d[i][k] + d[k][j] < d[i][j]:
                    return []
                if d[i][k] + d[k][j] == d[i][j]:
                    
                    e[i][j] = 0
                    e[j][i] = 0
    return e
    
import copy
n = int(input())
edges = []

graph = [list(map(int, input().split())) for i in range(n)]
e = warshall(graph, n)
if e == []:
    print(-1)
    exit()

edge_list = [[] for _ in range(n)]
ans = 0
for i in range(n):
    for j in range(n):
        if e[i][j] > 0:
            edge_list[i].append((e[i][j], j))
        if j > i and e[i][j]:
            ans += e[i][j]

print(ans)

Solution (Python):
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
cnt = 0
for k in range(n):
  for i in range(n-1):
    for j in range(i+1,n):
      if a[i][j] > a[i][k] + a[k][j]:
        print(-1); exit(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
      elif a[i][j] == a[i][k] + a[k][j]:
        cnt += a[i][j]
        break
tot = sum(sum(x) for x in a)//2
print(tot-cnt)

Solution (Python):
N = int(input())
A = [list(map(int,input().split())) for _ in range(N)]
cnt = 0
for i in range(N-1):
    for j in range(i+1,N):
        amin = 10**10
        for k in range(N):
            if k!=i and k!=j:
                amin = min(amin,A[i][k]+A[k][j])
        if A[i][j]>amin:
            cnt = -1
            break
        elif A[i][j]<amin:
            cnt += A[i][j]
    if cnt==-1:break
print(cnt)

Solution (Python):
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = np.array([lr() for i in range(N)])
INF = 10 ** 9
np.fill_diagonal(A, INF)
answer = 0
for i in range(N):
    for j in range(i+1, N):
        detour = np.min(A[i] + A[j])
        if A[i, j] < detour:
            
            answer += A[i, j]
        elif A[i, j] > detour:
            print(-1)
            exit()

print(answer)

Solution (Python):
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = np.array([lr() for i in range(N)])
INF = 10 ** 10
np.fill_diagonal(A, INF)
answer = 0
for i in range(N):
    for j in range(i+1, N):
        detour = np.min(A[i] + A[j])
        if A[i, j] < detour:
            
            answer += A[i, j]
        elif A[i, j] > detour:
            print(-1)
            exit()

print(answer)

Solution (Python):
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = np.array([lr() for i in range(N)])
INF = 10 ** 10
np.fill_diagonal(A, INF)
answer = 0
for i in range(N):
    for j in range(i+1, N):
        detour = np.min(A[i] + A[j])
        if A[i, j] < detour:
            
            answer += A[i, j]
        elif A[i, j] > detour:
            print(-1)
            exit()

print(answer)

Solution (Python):
import copy
loss=0
def warshall_floyd(d):
    
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d
def warshall_floyd2(d):
    
    ans=0
    for i in range(n):
        for j in range(n):
            flg=0
            for k in range(n):
                if i==j or j==k or k==i:
                    continue
                if d[i][j]==d[i][k] + d[k][j]:
                    flg=1
            if flg==0:
                ans+=d[i][j]
    
    return ans

n=int(input())
a=[list(map(int,input().split())) for _ in range(n)]
b=copy.deepcopy(a)
b=warshall_floyd(b)


flg=True
for i in range(n):
    for j in range(n):
        if a[i][j]!=b[i][j]:
            flg=False
            break
    else:
        continue
    break
if flg:
    ans=warshall_floyd2(b)
    print(ans//2)
else:
    print(-1)

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

length = 0
for i in range(n) :
    for j in range(n):
        route = 10000000000
        for k in range(n):
            if k == i or k == j : continue
            route = min(route, a[i][k] + a[k][j] ) 
            if route < a[i][j]:
                print(-1)
                exit() 
        if route > a[i][j] :
            length +=  a[i][j]
print(int(length/2))

Solution (Python):

N = int(input())

matrix = [list(map(int, input().split(' '))) for _ in range(N)]
buf = [list(m) for m in matrix]

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

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

is_used = [[True for _ in range(N)] for m in matrix]
for k in range(N):
    for i in range(N):
        for j in range(N):
            if k != i and k != j:
                if matrix[i][k] + matrix[k][j] == matrix[i][j]:
                    is_used[i][j] = False

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


print(ans)

Solution (Python):
import copy

def warshal_floyd(d):
    
    global 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])
    
    return d


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



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


flag = [[True]*N for _ in range(N)]
for k in range(N):
    for i in range(N):
        for j in range(N):
            if graph[i][j] == graph[i][k] + graph[k][j] and i != k and k != j:
                flag[i][j] = False

ans = 0
for i in range(N):
    for j in range(i+1, N):
        if flag[i][j] == True:
            ans += graph[i][j]
print(int(ans))

Solution (Python):
import sys
from itertools import combinations
  
def solve():
    input = sys.stdin.readline
    N = int(input())
    A = dict()
    for i in range(N):
        A[i] = dict()
        for j, a in enumerate(list(map(int, input().split()))): A[i][j] = a

    length = 0
    possible = True
    for a, b in combinations(range(N), 2):
        Lab = A[a][b]
        for k in range(N):
            if k != a and k != b:
                if Lab < A[a][k] + A[k][b]: continue
                if Lab >  A[a][k] + A[k][b]: possible = False
                break
        else: length += Lab
        if possible: continue
        print(-1)
        break
    else: print(length)
    
    return 0
 
if __name__ == "__main__":
    solve()

Solution (Python):
import sys
from itertools import permutations, combinations
  
def solve():
    input = sys.stdin.readline
    N = int(input())
    A = dict()
    for i in range(N):
        A[i] = dict()
        ain = [int(j) for j in input().split()]
        for j in range(N): A[i][j] = ain[j]

    length = 0
    possible = True
    for a, b in combinations(range(N), 2):
        Lab = A[a][b]
        create_pass = True
        for k in range(N):
            if k != a and k != b:
                if Lab >  A[a][k] + A[k][b]:
                    possible = False
                    break
                elif Lab ==  A[a][k] + A[k][b]:
                    create_pass = False
                    break
        if create_pass: length += Lab
        if not possible:
            print(-1)
            break
    else: print(length)
    
    return 0
  
if __name__ == "__main__":
    solve()

Solution (Python):
import sys
from itertools import permutations, combinations
  
def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [[int(a) for a in input().split()] for _ in range(N)]

    length = 0
    possible = True
    for a, b in combinations(range(N), 2):
        Lab = A[a][b]
        for k in range(N):
            if k != a and k != b:
                if Lab >  A[a][k] + A[k][b]:
                    possible = False
                    break
                elif Lab ==  A[a][k] + A[k][b]:
                    break
        else: length += Lab
        if not possible:
            print(-1)
            break
    else: print(length)
    
    return 0
  
if __name__ == "__main__":
    solve()

Solution (Python):
import sys
from itertools import permutations, combinations
  
def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [[int(a) for a in input().split()] for _ in range(N)]

    length = 0
    possible = True
    for a in range(N):
        for b, l in enumerate(A[a]):
            for k in range(N):
                if k != a and k != b:
                    if l >  A[a][k] + A[k][b]:
                        possible = False
                        break
                    elif l ==  A[a][k] + A[k][b]:
                        break
            else: length += l
        if not possible:
            print(-1)
            break
    else: print(length // 2)
    
    return 0
  
if __name__ == "__main__":
    solve()

Solution (Python):
import sys
from itertools import permutations, combinations
  
def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [[int(a) for a in input().split()] for _ in range(N)]

    length = 0
    possible = True
    for a, b in combinations(range(N), 2):
        Lab = A[a][b]
        create_pass = True
        for k in range(N):
            if k != a and k != b:
                if Lab >  A[a][k] + A[k][b]:
                    possible = False
                    break
                elif Lab ==  A[a][k] + A[k][b]:
                    create_pass = False
                    break
        if create_pass: length += Lab
        if not possible:
            print(-1)
            break
    else: print(length)
    
    return 0
  
if __name__ == "__main__":
    solve()

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

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

for i in range(N):
    for j in range(N):
        if i == j:
            continue
        for k in range(N):
            if i == k or j == k:
                pass
            else:                    
                if d[i][j] > d[i][k] + d[k][j]:
                    print (-1)
                    exit()
                elif d[i][j] == d[i][k] + d[k][j]:
                    check[i][j] = 0

ans = 0
for i in range(N):
    for j in range(N):
        ans += d[i][j] * check[i][j]

print (ans // 2)

Solution (Python):
import sys
import numpy as np

read = sys.stdin.read

N, *A = map(int, read().split())
A = np.array(A, np.int64).reshape(N, N)
'''
answer = 0
for i, j in product(range(N), repeat=2):
    if i < j:
        continue
    edge = A[i][j]
    for k in range(N):
        if i == k or j == k:
            continue

        tmp = A[i][k] + A[k][j]
        if tmp < edge:
            print(-1)
            exit()
        elif tmp == edge:
            break
    else:
        answer += edge
'''

useless = np.zeros_like(A)

for i in range(N):
    grid = A[i] + A[i, None].T
    if np.any(grid < A):
        print(-1)
        exit()
    grid[i] = np.inf
    grid[:, i] = np.inf

    useless |= (A == grid)

print(A[useless != 1].sum() // 2)

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def warshall_floyd(N: int, graph: list) -> list:
    """ ワーシャルフロイド(頂点数, 隣接行列(0-indexed)) """
    from copy import deepcopy

    res = deepcopy(graph)
    for i in range(N):
        
        res[i][i] = 0
    
    for k in range(N):
        for i in range(N):
            for j in range(N):
                res[i][j] = min(res[i][j], res[i][k] + res[k][j])
    
    for i in range(N):
        if res[i][i] < 0:
            return []
    return res

def build_grid(H, W, intv, _type, space=True, padding=False):
    
    if space:
        _input = lambda: input().split()
    else:
        _input = lambda: input()
    _list = lambda: list(map(_type, _input()))
    
    if padding:
        offset = 1
    else:
        offset = 0
    grid = list2d(H+offset*2, W+offset*2, intv)
    for i in range(offset, H+offset):
        row = _list()
        for j in range(offset, W+offset):
            grid[i][j] = row[j-offset]
    return grid

def check1(A, B):
    for i in range(N):
        for j in range(N):
            
            if A[i][j] != B[i][j]:
                return False
    return True

def check2(G):
    res = 0
    S = set()
    for k in range(N):
        for i in range(N):
            for j in range(N):
                
                if i != j and j != k and k != i \
                        and G[i][k] + G[k][j] == G[i][j]:
                    if (i, j) not in S:
                        S.add((i, j))
                        res += G[i][j]
    return res

N = INT()
G = build_grid(N, N, 0, int)


wf = warshall_floyd(N, G)
if not check1(G, wf):
    print(-1)
    exit()


total = 0
for i in range(N):
    for j in range(N):
        total += wf[i][j]
ans = (total - check2(wf)) // 2
print(ans)

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

INF = 10 ** 15
B = [[INF for _ in range(N)] for _ 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):
  if A[i] != B[i]:
    print(-1)
    exit()
    
C = [[1 for _ in range(N)] for _ in range(N)]
for i in range(N):
  for j in range(i + 1, N):
    for k in range(N):
      if i != k and j != k:
        if A[i][k] + A[k][j] == A[i][j]:
          C[i][j] = 0


answer = 0
for i in range(N):
  for j in range(i + 1, N):
    answer += C[i][j] * A[i][j]
print(answer)

Solution (Python):
import sys
import numpy as np 
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix

'''
Aが最短距離を表す、というのはSnukeの推測でしかない。
なので、Aを、A[v, u]が辺の重みを表しているgraphとして捉え、floyd_warshallで実際に最短距離を求め、Bとする。

B[v, u] < A[v, u]が存在したらAが最短距離を表すという推測は間違っていたことになる。
もしB[v, u] == B[v, w] + B[w, u](ただし w ≠ v, w ≠ u)となるようなwが存在したら、
Aのgraphでedge(v, u)はなくても良いことになるので、A[v, u] = A[u, v] = 0として辺を消す。(仮に辺を消しても、shortest_dist(v, u)には影響しないため)

最後に残った辺々だけをつなげてできるグラフの合計の辺の重みが答えとなる
'''

n = int(sys.stdin.readline().rstrip())
A = np.array(sys.stdin.read().split(), dtype=np.int64).reshape(n, n)

def main():
    B = floyd_warshall(csr_matrix(A), directed=False).astype(np.float64)
    if np.any(B < A):
        return -1
        
    np.fill_diagonal(B, np.inf)
    
    for v in range(n-1):
        for u in range(v+1, n):
            detours = B[v] + B[u]
            if np.any(detours == B[v, u]):
                A[v, u] = A[u, v] = 0

    return np.sum(A) // 2

if __name__ == '__main__':
    ans = main()
    print(ans)

Solution (Python):
import sys
import numpy as np 
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix

n = int(sys.stdin.readline().rstrip())
A = np.array(sys.stdin.read().split(), dtype=np.int64).reshape(n, n)

def main():
    B = floyd_warshall(csr_matrix(A), directed=False).astype(np.float64)
    if np.any(B < A):
        return -1
        
    np.fill_diagonal(B, np.inf)
    
    for v in range(n-1):
        for u in range(v+1, n):
            detours = B[v] + B[u]
            if np.any(detours == B[v, u]):
                A[v, u] = A[u, v] = 0
                
    return np.sum(A) // 2

if __name__ == '__main__':
    ans = main()
    print(ans)

Solution (Python):
import sys
import numpy as np 
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix

n = int(sys.stdin.readline().rstrip())
A = np.array(sys.stdin.read().split(), dtype=np.float64).reshape(n, n)

def main():
    B = floyd_warshall(csr_matrix(A), directed=False)
    if np.any(B < A):
        return -1
        
    np.fill_diagonal(B, np.inf)
    
    total_length = 0
    for v in range(n-1):
        for u in range(v+1, n):
            detours = B[v] + B[u]
            if np.all(detours > B[v, u]):
                total_length += B[v, u]

    return int(total_length)

if __name__ == '__main__':
    ans = main()
    print(ans)

Solution (Python):
import sys
import numpy as np 
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix

n = int(sys.stdin.readline().rstrip())
A = np.array(sys.stdin.read().split(), dtype=np.float64).reshape(n, n)

def main():
    B = floyd_warshall(csr_matrix(A), directed=False).astype(np.int64)
    if np.any(B < A):
        return -1
        
    np.fill_diagonal(A, np.inf)
    
    total_length = 0
    for v in range(n-1):
        for u in range(v+1, n):
            detours = A[v] + A[u]
            if np.all(detours > B[v, u]):
                total_length += B[v, u]

    return total_length

if __name__ == '__main__':
    ans = main()
    print(ans)

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

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

ans = 0
for i in range(N):
    for j in range(i+ 1, N):
        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())
d = [list(map(int, input().split())) for _ in range(N)]

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

for i in range(N):
    for j in range(N):
        if i == j:
            continue
        for k in range(N):
            if i == k or j == k:
                pass
            else:                    
                if d[i][j] > d[i][k] + d[k][j]:
                    print (-1)
                    exit()
                elif d[i][j] == d[i][k] + d[k][j]:
                    check[i][j] = 0

ans = 0
for i in range(N):
    for j in range(N):
        ans += d[i][j] * check[i][j]

print (ans // 2)

Solution (Python):
N = int(input())
A = [[int(i) for i in input().split()] for _ in range(N)]
roads = [[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[j][k]:
                print(-1)
                exit()
            if i == j:
                roads[i][j] = False
            if i != k and j != k and A[i][j] == A[i][k]+A[j][k]:
                roads[i][j] = False


ans = 0
for i in range(N):
    for j in range(i+1, N):
        if roads[i][j] is True:
            ans += A[i][j]
print(ans)

Solution (Python):
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))



N = I()
A = []
for i in range(N):
    A.append(III())

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

print(l)