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 bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def warshall_floyd(g):
    d = defaultdict(dict)
    V = list(g.keys())
    for v in g.values():
        V.extend(list(v))
    V = set(V)
    for i in V:
        for j in V:
            if i in g and j in g[i]:
                d[i][j] = g[i][j]
            else:
                d[i][j] = sys.maxsize
    for k in g:
        for i in g:
            for j in g:
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]

    return d


@mt
def slv(N, A):
    g = defaultdict(dict)
    for i, r in enumerate(A):
        for j, c in enumerate(r):
            g[i][j] = c
            g[j][i] = c

    d = warshall_floyd(g)

    for i in range(N):
        for j in range(N):
            if A[i][j] != d[i][j]:
                return -1
    ans = 0
    for i in range(N):
        for j in range(i, N):
            for k in range(N):
                if A[i][k] == 0:
                    continue
                if j != k and A[i][k] + A[k][j] == A[i][j]:
                    break
            else:
                ans += A[i][j]
    return ans


def main():
    N = read_int()
    A = [read_int_n() for _ in range(N)]
    
    
    
    
    print(slv(N, A))


if __name__ == '__main__':
    main()

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

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

if np.any(A != floyd_warshall(A)):
    print(-1)
else:
    ans = 0
    A += np.diag([float('inf')] * N)
    for i in range(N):
        for j in range(i + 1, N):
            if np.min(A[i] + A[j]) != A[i, j]:
                ans += int(A[i, j])
    print(ans)

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

N = int(input())
A = np.asarray([[int(Aij) for Aij in input().split()] for _ in range(N)])

A2 = floyd_warshall(A, directed=False)

if np.any(A != A2):
    print(-1)
else:
    d = 0
    A += np.diag([2*10**9] * N)
    for i in range(N):
        for j in range(i + 1, N):
            if np.min(A[i] + A[j]) != A[i, j]:
                d += A[i, j]
    print(d)

Solution (Python):
import numpy as np

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

for i in range(n):
  a[i,i] = 1e9 + 1

ans = 0
for u in range(n):
    for v in range(u + 1, n): 
        dist = a[u,v]
        cd = np.min(a[u] + a[v])
        if dist > cd:
            print(-1)
            exit(0)
        if dist < cd:
            ans += dist
 
print(int(ans))

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

def calc(N, A):
    r = 0
    if N == 1:
        return 0
    if N == 2:
        return A[0][1]
    for i in range(0, N):
        for j in range(i + 1, N):
            a = A[i][j]
            d = min(A[i][k] + A[k][j] for k in range(0, N) if k != i and k != j)
            if a > d:
                return -1
            if a < d:
                r += a
    return r

print(calc(N, A))

Solution (Python):
N = int(input())
A = [list(map(int, input().split())) for i in range(N)]
ans = 0
for i in range(N-1):
    for j in range(i+1, N):
        direct = A[i][j]
        for k in range(N):
            if k == i or k == j:
                continue
            ind = A[i][k] + A[k][j]
            if direct > ind:
                print(-1)
                exit()
            elif direct == ind:
                break
        else:
            ans += direct
print(ans)

Solution (Python):
N = int(input())
A,B,Ans = [],[],0
for i in range(N):
    x = list(map(int,input().split()))
    A.append(x[:])
    B.append(x[:])

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

if A!=B:
    print(-1)
else:
    for i in range(N):
        for j in range(i+1,N):
            exists = True
            for k in range(N):
                if k not in (i,j) and B[i][j]==B[i][k]+B[k][j]:
                    exists = False                    
            if exists:
                Ans += B[i][j]
    print(Ans)

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

ans = sum([sum(Map[i]) for i in range(N)])

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

for i in range(N):
    for j in range(N):
        for k in range(N):
            if i == k or j == k:
                continue
            if Map[i][k] + Map[k][j] == Map[i][j]:
                ans -= Map[i][j]
                break

print(ans//2)

Solution (Python):
import numpy as np
N = input()
A = [np.array(map(int,raw_input().split()), dtype=np.int64) for _ in [0]*N]
inf = 10**10
for i in range(N):
    A[i][i] = inf



result = 0
for i in range(N-1):
    for j, d1 in enumerate(A[i][i+1:], start=i+1):
	
        d2 = np.min(A[i]+A[j])
        if d1 >= d2:
            if d1 > d2:
                print(-1)
                exit()
        else:
            result += d1
print(result)

Solution (Python):
import numpy as np
N = int(input())
A = [np.array(input().split(), dtype=np.int64) for _ in range(N)]
ans = 0
inf = 10**10
result = 0
for i in range(N):
    A[i][i] = inf

for i in range(N-1):
    for j, d1 in enumerate(A[i][i+1:], start=i+1):
        d2 = np.min(A[i]+A[j])
        if d1 >= d2:
            if d1 > d2:
                print(-1)
                exit()
        else:
            result += d1

print(result)

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

ret = 0
for i in range(V):
    for j in range(i+1, V):
        f = True
        for k in range(V):
            if i == k or j == k:
                continue
            if A[i][j] > A[i][k] + A[k][j]:
                print(-1)
                exit()
            elif A[i][j] == A[i][k] + A[k][j]:
                f = False
        if f:
            ret += A[i][j]

print(ret)

Solution (Python):
import numpy as np
import sys

def read_data():
    try:
        LOCAL_FLAG
        import codecs
        import os

        lines = []
        file_path = os.path.join(os.path.dirname(__file__), 'data.dat')
        with codecs.open(file_path, 'r', 'utf-8') as f:
            n_lines = int(f.readline())
            for i in range(n_lines):
                lines.append(f.readline().rstrip("\r\n"))

    except NameError:
        lines = []
        n_lines = int(input())
        for i in range(n_lines):
            lines.append(input())
    return lines

raw_data = read_data()
tarray = []
for each in raw_data:
    tarray.append(each.split())
A = np.array(tarray, dtype='int64')
N = A.shape[0]

def Restoring_Road_Network():

    import scipy.sparse.csgraph as graph

    MAX = [10000000000]*N  
    d = np.diag(MAX)
    C = A.copy()
    C += d
    total_dis = 0
    n_path = 0
    for i in range(N-1):
        for j in range(i+1, N):
            dis_two_node = np.min(C[i] + C[j])
            if dis_two_node > C[i,j]:
                total_dis += C[i,j]
                
            elif dis_two_node < C[i,j]:
                print(-1)
                exit()

    print(total_dis)

Restoring_Road_Network()

Solution (Python):
import numpy as np
import sys

def read_data():
    try:
        LOCAL_FLAG
        import codecs
        import os

        lines = []
        file_path = os.path.join(os.path.dirname(__file__), 'data.dat')
        with codecs.open(file_path, 'r', 'utf-8') as f:
            n_lines = int(f.readline())
            for i in range(n_lines):
                lines.append(f.readline().rstrip("\r\n"))

    except NameError:
        lines = []
        n_lines = int(input())
        for i in range(n_lines):
            lines.append(input())
    return lines

raw_data = read_data()
tarray = []
for each in raw_data:
    tarray.append(each.split())
A = np.array(tarray, dtype='int64')
N = A.shape[0]


def Restoring_Road_Network2():

    not_available = False
    for k in range(0, N):
        for i in range(0, N):
            if(k==i): continue
            for j in range(0, N):
                if((i==j) or (j==k)): continue
                if(A[i][k] + A[k][j] < A[i][j]):
                    not_availabel = True
                if(A[i][k] + A[k][j] == A[i][j]):
                    B[i][j] = 1
                    B[j][i] = 1

    try:
        LOCAL_FLAG
        print(B)
    except NameError:
        pass

    if(not_available):
        print(-1)
    else:
        total_dis = 0
        for i in range(0, N):
            for j in range(i, N):
                if(B[i][j] == 0):
                    total_dis += A[i][j]
        print(total_dis)

def Restoring_Road_Network3():

    import scipy.sparse.csgraph as graph

    MAX = [10000000000]*N  
    d = np.diag(MAX)
    C = A.copy()
    C += d
    total_dis = 0
    n_path = 0
    for i in range(N-1):
        for j in range(i+1, N):
            dis_two_node = np.min(C[i] + C[j])
            if dis_two_node > C[i,j]:
                total_dis += C[i,j]
                
            elif dis_two_node < C[i,j]:
                print(-1)
                exit()

    print(total_dis)

def AA():
    import numpy as np

    for i in range(N):
        A[i][i] = 10000000000

    result = 0
    for i in range(N-1):
        for j, d1 in enumerate(A[i][i+1:], start=i+1):
            d2 = np.min(A[i]+A[j])
            
            
            if d1 >= d2:
                if d1 > d2:
                    print(-1)
                    exit()
            else:
                result += d1
    print(result)

Restoring_Road_Network3()

Solution (Python):
import numpy as np
N = int(input())
A = [np.array(input().split(), dtype=np.int64) for _ in [0]*N]
inf = 10**10
for i in range(N):
    A[i][i] = inf
 
result = 0
for i in range(N-1):
    for j, d1 in enumerate(A[i][i+1:], start=i+1):
        d2 = np.min(A[i]+A[j])
        if d1 >= d2:
            if d1 > d2:
                print(-1)
                exit()
        else:
            result += d1
print(result)

Solution (Python):
def Warshall_Floyd(edges,N):
  import copy
  d=copy.deepcopy(edges)
  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

import sys
N=int(input())
A=[list(map(int,input().split())) for i in range(N)]
B=Warshall_Floyd(A,N)
if A!=B:
  print(-1)
  sys.exit()

ans=0
for i in range(N):
  for j in range(i):
    need=1
    for k in range(N):
      if k!=i and k!=j:
        if A[i][j]==A[i][k]+A[k][j]: need=0
    ans+=need*A[i][j]
print(ans)

Solution (Python):
def Warshall_Floyd(edges,N):
  """頂点N個のグラフ上の隣接行列edges(空欄はinfとせよ)が与えられたとき, 
  2点間の最短距離距離を隣接行列で返す"""
  for k, i, j in itertools.product(range(N), range(N),range(N)):
    if edges[i][j]>edges[i][k]+edges[k][j]: return 1
  return 0
 
import sys
import itertools
N=int(input())
A=[list(map(int,input().split())) for i in range(N)]
if Warshall_Floyd(A,N):
  print(-1)
  sys.exit()
 
ans=0
for i, j in itertools.product(range(N),range(N)):
  need=1
  for k in range(N):
    if k!=i and k!=j and A[i][j]==A[i][k]+A[k][j]:
      need=0
      break
  if need:ans+=A[i][j]
print(ans//2)

Solution (Python):
import numpy as np
import scipy.sparse.csgraph as graph

N = int(input())
G = np.array([list(map(int, input().split())) for i in range(N)])

G2 = graph.floyd_warshall(G, directed=False)

if np.any(G != G2):
    print(-1)
    exit()
else:
    c = [2*10**9]*N
    d = np.diag(c)
    G += d
    ans = 0
    for i in range(N):
        for j in range(i+1, N):
            two = np.min(G[i]+G[j])
            if two != G[i,j]:
                ans += G[i,j]

print(ans)

Solution (Python):
def main():
    """
    ワーシャルフロイドで経由したときに変更がないことを確認する
    変更がある場合、
        最短経路ではないため条件を満たさない
    変更がない場合、
        経由の経路でも最短距離になるケースを除いて距離を計算する
    """
    N = int(input())
    a = [None] * N
    total = 0
    for i in range(N):
        a[i] = list(map(int, input().split()))
        total += sum(a[i])

    for k in range(N):
        for i in range(N):
            for j in range(N):
                
                d = a[i][k] + a[k][j]
                if a[i][j] > d:
                    return -1

    
    v = [[False] * N for _ in range(N)]
    no_need = 0
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if i == k or j == k:
                    continue
                if not v[i][j] and (a[i][j] == a[i][k] + a[k][j]):
                    no_need += a[i][j]
                    v[i][j] = True

    
    return (total - no_need) // 2

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

Solution (Python):
def D_RestoringRoadNetwork(N, A):
    dist = [x[:] for x in A] 
    dist2 = [x[:] for x in A] 
    isMinDist = True  

    
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if A[i][j] > dist[i][k] + dist[k][j]:
                    
                    isMinDist = False
                elif A[i][j] == dist[i][k] + dist[k][j] and dist[i][k] > 0 and dist[k][j] > 0:
                    
                    dist2[i][j] = 0
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    if isMinDist:
        ans = 0
        for i in range(N):
            for j in range(i, N):
                
                ans += dist2[i][j]
        return ans
    else:
        return -1

N=int(input())
A=[[int(i) for i in input().split()] for j in range(N)]
print(D_RestoringRoadNetwork(N, A))

Solution (Python):
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]

n=i1()
a=[]
e=0
for i in range(n):
    a.append(i2())
    e+=sum(a[-1])
d=[x[:] for x in a]
dd=[x[:] for x in a]
c=0
for i in range(n):
    for j in range(n):
      for k in range(n):
        if a[j][k]>d[j][i] + d[i][k]:
            c=-1
        elif a[j][k]==d[j][i] + d[i][k] and d[j][i]>0 and d[i][k]>0:
            dd[j][k]=0
        d[j][k] = min(d[j][k], d[j][i] + d[i][k])
if c<0:
    print(-1)
else:
    s=0
    for i in range(n):
        for j in range(i,n):
           s+=dd[i][j]
    print(s)

Solution (Python):
n=int(input())
d=[]
for i in [0]*n:
    d.append([int(x) for x in input().split()])
from itertools import product
ans=0
for i,j in product(range(n),range(n)):
    flag=0
    for k in range(n):
        if d[i][j]>d[i][k]+d[k][j]:
            print(-1)
            import sys
            sys.exit()
        if d[i][j]==d[i][k]+d[k][j] and (k!=i and k!=j and i!=j ):
            flag=1
    if flag==0:
        ans+=d[i][j]
print(ans//2)