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 copy
N=int(input())



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


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

H=copy.deepcopy(G)


H=warshall_floyd(H)



for i in range(N):
    for j in range(N):
        if G[i][j]!=H[i][j]:
            print(-1)
            exit()
T=copy.deepcopy(H)
for k in range(N):
    for i in range(N):
        for j in range(N):
            if H[i][j]==H[i][k] + H[k][j] and i!=k and j!=k:
                T[i][j]=0
ans=0
for i in range(N):
    ans+=sum(T[i])
print(ans//2)

Solution (Python):
from copy import deepcopy
N = int(input())
A = [list(map(int, input().split())) for _ 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

B = deepcopy(A)





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 A[i][k] + A[k][j] < A[i][j]:
        print(-1)
        exit()
      elif A[i][k] + A[k][j] == A[i][j]: 
        B[i][j] = 0

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

print(ans)

Solution (Python):
N=int(input())
import copy
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

  
cost=[list(map(int,input().split())) for i in range(N)]
D=copy.deepcopy(cost)
E=warshall_floyd(cost)
      
if D!=E: 
  print(-1)
  exit()
D=cost
for k in range(N):
  for i in range(N):
    for j in range(N):
      a,b,c=D[i][j],D[j][k],D[i][k]
      if a!=0 and b!=0 and c!=0:
        if D[i][j]==D[i][k]+D[k][j]:
          D[i][j]=0       
ans=0
for i in range(N):
  ans+=sum(D[i]) 
print(ans//2)

Solution (Python):
'''
自宅用PCでの解答
'''
import math

import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"

def main():
    n = int(ipt())
    a = [[int(i) for i in ipt().split()] for _ in range(n)]

    for i in range(n):
        for j in range(n):
            for k in range(n):
                if a[j][k] > a[j][i]+a[i][k]:
                    print(-1)
                    exit()
    for i in range(n):
        for j in range(n):
            for k in range(n):
                if a[j][i] != 0 and a[i][k] != 0 and a[j][k] == a[j][i]+a[i][k]:
                    a[j][k] = 0

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

    print(ans)

    return None

if __name__ == '__main__':
    main()

Solution (Python):
N=int(input())
import copy
def warshall_floyd(N):
  d=[list(map(int,input().split())) for i in range(N)]
  D=copy.deepcopy(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])
  if d==D:
    return d
  else:
    return -1
  
E=warshall_floyd(N)
if E==-1:
  print(-1)
  exit()
  
for k in range(N):
  for i in range(N):
    for j in range(N):
      if E[i][j]!=0 and E[i][k]!=0 and E[k][j]!=0:
        if E[i][j]==E[i][k]+E[k][j]:
          E[i][j]=0       
ans=0
for i in range(N):
  ans+=sum(E[i]) 
print(ans//2)

Solution (Python):
import copy


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

    return G if G==D else -1


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

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

ans=0
for i in range(n):
    ans +=sum(Graph[i])
print(ans//2)

Solution (Python):



n = int(input())
dp = [[int(x) for x in input().split()] for y in range(n)]
del_l = []
ans = 0

for i in range(n-1):
    for j in range(i+1,n):
        for k in range(n):
            if k in (i,j):
                continue
            if dp[i][j] > dp[i][k] + dp[k][j]:
                print("-1")
                exit()
            elif dp[i][j] == dp[i][k] + dp[k][j]:
                break
        else:
            ans += dp[i][j]

print(ans)

Solution (Python):



n = int(input())
dp = [[int(x) for x in input().split()] for y in range(n)]
del_l = []
ans = 0

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

for i in range(n-1):
    for j in range(i+1,n):
        for k in range(n):
            if k in (i,j):
                continue
            if dp[i][j] > dp[i][k] + dp[k][j]:
                print("-1")
                exit()
            elif dp[i][j] == dp[i][k] + dp[k][j]:
                ans -= dp[i][j]
                break

print(ans)

Solution (Python):



n = int(input())
dp = [[int(x) for x in input().split()] for y in range(n)]
del_l = []
ans = 0





for i in range(n-1):
    for j in range(i+1,n):
        for k in range(n):
            if k in (i,j):
                continue
            if dp[i][j] > dp[i][k] + dp[k][j]:
                print("-1")
                exit()
            elif dp[i][j] == dp[i][k] + dp[k][j]:
                break
        else:
            ans += dp[i][j]

print(ans)

Solution (Python):

import sys


def solve(N: int, A: "List[List[int]]"):
    import numpy as np
    from scipy.sparse.csgraph import floyd_warshall
    A = np.array(A, dtype=np.float64)
    B = floyd_warshall(A, directed=True)
    if not np.array_equal(A, B):
        return -1
    delta = 1e-1
    _, pre = floyd_warshall(A-delta, return_predecessors=True)
    return int(A[pre == [[i]*N for i in range(N)]].sum()) // 2


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)]  
    print(solve(N, A))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    
    main()

Solution (Python):

import sys


def solve(N: int, A: "List[List[int]]"):
    import numpy as np
    from scipy.sparse.csgraph import floyd_warshall
    A = np.array(A, dtype=np.float64)
    B = floyd_warshall(A, directed=True)
    if not np.array_equal(A, B):
        return -1
    delta = 1e-1
    _, pre = floyd_warshall(A-delta+np.identity(N)*delta, return_predecessors=True)
    return int(A[pre == [[i]*N for i in range(N)]].sum()) // 2


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)]  
    print(solve(N, A))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    
    main()

Solution (Python):

import sys


def solve(N: int, A: "List[List[int]]"):
    import numpy as np
    from scipy.sparse.csgraph import floyd_warshall
    A = np.array(A, dtype=np.float64)
    B = floyd_warshall(A, directed=True)
    if not np.array_equal(A, B):
        return -1
    delta = 1e-3
    _, pre = floyd_warshall(A-delta+np.identity(N)*delta, return_predecessors=True)
    return int(A[pre == [[i]*N for i in range(N)]].sum()) // 2


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)]  
    print(solve(N, A))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    
    main()

Solution (Python):

import sys


def solve(N: int, A: "List[List[int]]"):
    import numpy as np
    from scipy.sparse.csgraph import floyd_warshall
    A = np.array(A, dtype=np.float64)
    B = floyd_warshall(A, directed=True)
    if not np.array_equal(A, B):
        return -1
    delta = 1e-7
    _, pre = floyd_warshall(A-delta+np.identity(N)*delta, return_predecessors=True)
    return int(A[pre == [[i]*N for i in range(N)]].sum()) // 2


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)]  
    print(solve(N, A))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    
    main()

Solution (Python):
import copy

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

exist = 1
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]:
        exist = 0
        break
      if graph[i][j] != 0 and graph[i][k] != 0 and graph[k][j] != 0:
        if graph[i][j] == graph[i][k] + graph[k][j]:
          road[i][j] = 0
    if exist == 0:
      break
  if exist == 0:
    break

if exist == 0:
  print(-1)
else:
  ans = 0
  for row in road:
    ans += sum(row)
  print(ans//2)

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

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

ans = 0
for i in range(n):
    for j in range(i+1, n):
        ok = True
        for k in range(n):
            if i == k or j == k:
                continue
            if a[i][j] == a[i][k]+a[k][j]:
                ok = False
                break
        if ok:
            ans += a[i][j]
print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    grid = [list(map(int, input().split())) for _ in range(n)]
    flg = [[True] * n for _ in range(n)]

    for k in range(n):
        for i in range(n):
            for j in range(n):
                if grid[i][k] + grid[k][j] < grid[i][j]:
                    print(-1)
                    exit()
                elif grid[i][k] + grid[k][j] == grid[i][j] and i != k and j != k:
                    flg[i][j] = False

    res = 0
    for i in range(n):
        for j in range(n):
            if flg[i][j]:
                res += grid[i][j]
    print(res // 2)


if __name__ == '__main__':
    resolve()

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()

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

    """
    まず三角不等式が任意の３頂点に対して成り立つことを確認する。
    なりたってなければグラフは存在しない。

    なりたっている場合は与えられた最短距離と同じ長さの辺を各頂点のペアごとに張れば
    一応条件を満たすグラフは構成できている。

    あとはここから余分な辺をどう削除するかだが、これは三角不等式で統合が成り立っているもの
    として判別できる。
    """

    
    triangle = True
    used_path = [[0] * N for _ in range(N)]
    for i in range(N):
        for j in range(i + 1, N):
            minimal_dist = 10**18
            for k in range(N):
                if k == i or k == j: continue
                if A[i][k] + A[k][j] < A[i][j]:
                    triangle = False
                    break
                else:
                    minimal_dist = min(minimal_dist, A[i][k] + A[k][j])
            if A[i][j] < minimal_dist: used_path[i][j] = 1
    if not triangle:
        print(-1)
        return
    
    
    ans = 0
    for i in range(N):
        for j in range(i + 1, N):
            ans += A[i][j] * used_path[i][j]
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
import sys

icase=0
if icase==0:
    n=int(input())
    a=[[0]*n for i in range(n)]
    for i in range(n):
        a[i]=list(map(int,input().split()))
elif icase==1:
    n=3
    a=[[0, 1, 3], [1, 0, 2], [3, 2, 0]]


dp=[[0]*n for i in range(n)]
for i in range(n):
    dp[i]=a[i].copy()
    
c=[[0]*n for i 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]:
                dp[i][j]=dp[i][k]+dp[k][j]
            if dp[i][j]==dp[i][k]+dp[k][j] and i!=k and j!=k:
                c[i][j]=1                
                

icnt=0
for i in range(0,n-1):
    for j in range(i+1,n):
        if a[i][j]!=dp[i][j]:
            print(-1)
            sys.exit()
        elif c[i][j]==0:
            icnt+=dp[i][j]
print(icnt)

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

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    N = int(readline())
    A = list(list(map(int, readline().split())) for _ in range(N))
    A = np.array(A)
    D = dijkstra(A)
    if (A!=D).any():
        print(-1)
    else:
        ans = 0
        D += np.identity(N, int) * (10**10)
        for i in range(N):
            for j in range(i + 1, N):
                a = np.min(D[i] + D[j])
                if a > D[i, j]:
                    ans += D[i, j]
        print(int(ans))



if __name__ == '__main__':
    main()

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

ans = 0

for i in range(N):
    for j in range(N):
        used = True
        for k in range(N):
            if i == k or j == k:
                continue
            tmp = A[i][k] + A[k][j]
            if A[i][j] > tmp:
                print(-1)
                exit()
            if A[i][j] == tmp:
                used = False
        if used:
            ans += A[i][j]
print(ans//2)

Solution (Python):
import sys
from copy import deepcopy
import numpy as np
readline=sys.stdin.readline
read=sys.stdin.read

def main():
    n=int(readline())
    a=np.array([list(map(int,l.split())) for l in read().splitlines()])
    cost=deepcopy(a)
    for k in range(n):
        arr=np.stack([cost,[cost[k]]+np.transpose([cost[k]])])
        cost=np.amin(arr,axis=0)
    f=np.sum(cost<a)
    if f:
        print(-1)
        return
    filt=np.sum([([cost[k]]+np.transpose([cost[k]]))==cost for k in range(n)],axis=0)==2
    print(np.sum(a[filt])//2)

if __name__=='__main__':
    main()

Solution (Python):
import sys
from copy import deepcopy
import numpy as np
readline=sys.stdin.readline
read=sys.stdin.read

def main():
    n=int(readline())
    a=np.array([list(map(int,l.split())) for l in read().splitlines()])
    cost=deepcopy(a)
    for k in range(n):
        arr=np.stack([cost,[cost[k]]+np.transpose([cost[k]])])
        cost=np.amin(arr,axis=0)
    cost2=deepcopy(a)
    f=np.sum(cost<a)
    if f:
        print(-1)
        return
    filt=np.sum([([cost[k]]+np.transpose([cost[k]]))==cost for k in range(n)],axis=0)==2
    print(np.sum(a[filt])//2)

if __name__=='__main__':
    main()

Solution (Python):


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

total = 0
for n in range(N):
    for m in range(n + 1, N):
        total += A[n][m]

flag = False
for n in range(N):
    for m in range(n + 1, N):
        for k in range(N):
            if k != n and k != m:
                if A[n][m] > A[n][k] + A[k][m]:
                    flag = True
                    break
                elif A[n][m] == A[n][k] + A[k][m]:
                    
                    total -= A[n][m]
                    break
        if total < 0 or flag:
            break
    if total < 0 or flag:
        break

if flag:
    print(-1)
else:
    print(total)

Solution (Python):
def print_dp(dp):
    i_len = len(dp)
    j_len = len(dp[0])
    tmp_dp = [[0]*i_len for _ in range(j_len)]
    for i in range(i_len):
        for j in range(j_len):
            tmp_dp[j][i] = dp[i][j]
    for i in range(j_len):
        print(tmp_dp[i])

import copy
n = int(input())
grid = [[float('inf')]*n for _ in range(n)]
for i in range(n):
    lis = list(map(int, input().split()))
    for j in range(n):
        if i == j:
            grid[i][j] = 0
        else:
            grid[i][j] = lis[j]
grid_m = copy.deepcopy(grid)

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

ok = True
for i in range(n):
    for j in range(n):
        if not grid[i][j] == grid_m[i][j]:
            ok = False
if not ok:
    print(-1)
else:
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if i == k or j == k:
                    continue
                if grid[i][j] == grid[i][k] + grid[k][j] and grid[i][k] != 0 and grid[k][j] != 0:
                    grid[i][j] = 0
    res = 0
    for i in range(n):
        res += sum(grid[i])
    print(res//2)

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

Solution (Python):
from copy import deepcopy
def solve():
  ans = 0
  N = int(input())
  A = [list(map(int, input().split())) for _ in range(N)]
  d = deepcopy(A)
  D = deepcopy(A)
  
  for k in range(N):
    for i in range(N):
      if i==k:
        continue
      for j in range(N):
        if j==k:
          continue
        if d[i][k]+d[k][j]<=d[i][j]:
          d[i][j] = d[i][k]+d[k][j]
          D[i][j] = float('inf')
  for i in range(N): 
    for j in range(N):
      if D[i][j]<float('inf') and i>j:
        ans += A[i][j]
  
  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])
  for i in range(N):
    for j in range(N):
      if D[i][j] != A[i][j]:
        return -1
  return ans
print(solve())

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

    ans = 0
    for i in range(n):
        for j in range(n):
            if i == j:
                continue
            flag = True
            for k in range(n):
                if k == i or k == j:
                    continue
                if d[i][j] > d[i][k]+d[k][j]:
                    print(-1)
                    exit()
                elif d[i][j] == d[i][k]+d[k][j]:
                    flag = False
                else:
                    pass
            if flag:
                ans += d[i][j]
    
    print(ans//2)

if __name__ == '__main__':
    main()

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

np.fill_diagonal(A, 10**9+1)

ans = 0
for i in range(N-1):
  for j in range(i+1,N):
    d = np.min(A[i]+A[j])
    if d > A[i][j]:
      ans+=A[i][j]
    elif d < A[i][j]:
      print(-1)
      exit()

print(ans)

Solution (Python):
import heapq

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

ans = 0
for i in range(N):
    for j in range(N):
        via_k = float('inf')
        for k in range(N):
            if A[i][j] > A[i][k] + A[k][j]:
                print(-1)
                exit()
            if k == i or k == j:
                continue
            via_k = min(via_k, A[i][k] + A[k][j])
        if i <= j:
            continue
        if A[i][j] < via_k:
            ans += A[i][j]
print(ans)

Solution (Python):
import sys
from copy import deepcopy

N = int(input())
A = [[int(x) for x in input().split()] for _ in range(N)]
B = deepcopy(A)
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][k] + A[k][j] < A[i][j]:
                print(-1)
                sys.exit()
            elif A[i][k] + A[k][j] == A[i][j]:
                B[i][j] = 0

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

Solution (Python):

import copy
N = int(input())

A = []
for _ in range(N):
  A.append(list(map(int, input().split())))
  
D = copy.deepcopy(A)
for i in range(N):
  D[i][i] = 0
  
for k in range(N):
  for i in range(N):
    for j in range(N):
      D[i][j] = min(D[i][j], D[i][k] + D[k][j])
      



ans = 0
for i in range(N):
  for j in range(i+1,N):
    if D[i][j] < A[i][j]:
      print(-1)
      exit(0)
      
for i in range(N):
  for j in range(i+1,N):
    flg = True
    for k in range(N):
      if i == k or j == k:
        continue
      if D[i][j] == D[i][k] + D[k][j]:
        flg = False
    if flg:
      ans += D[i][j]
      
print(int(ans))

Solution (Python):
import sys

N = int(sys.stdin.readline())

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

grid_min_path = [[True for _ in range(N)] for _ in range(N)]

def warshall_floyd(d, n, grid_min_path):
    changed = False
    path_length = 0
    
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if d[i][j] > d[i][k] + d[k][j]:
                    changed = True
                if d[i][j] == d[i][k] + d[k][j] and i != k and k != j:
                    
                    grid_min_path[i][j] = False
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d, changed, grid_min_path

d, changed, grid_min_path = warshall_floyd(d, N, grid_min_path)

if changed:
    print(-1)
else:
    length = 0
    for i in range(N):
        for j in range(i+1, N):
            if grid_min_path[i][j]:
                length += d[i][j]
    print(length)

Solution (Python):


import copy

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

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

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

result = 0
for i in range(N):
    for j in range(N):
        flag = True
        if i == j:
            continue
        for k in range(N):
            if i == k or j == k:
                continue
            if A2[i][j] == A[i][k]+A[k][j]:
                flag = False
                break
        if flag:
            result += A[i][j]

print(result//2)

Solution (Python):
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

import copy

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

flag = True

for i in range(n):
    if root[i][i] != 0:
        flag = False
        break

search_distance = copy.deepcopy(root)

search_distance = warshall_floyd(search_distance)

ans = 0

for i in range(n):
    for j in range(n):
        if search_distance[i][j] != root[i][j]:
            flag = False
            break
        else:
            judge = 1
            for h in range(n):
                if h != i and h != j and root[i][h]+root[h][j] == root[i][j]:
                    judge = -1
            if judge == 1:
                ans += root[i][j]
if flag:
    print(ans//2)
else:
    print(-1)

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

import copy
d = copy.deepcopy(As)
for i in range(n):
    for k in range(n):
        for j in range(n):
            d[i][j] = min(d[i][j], d[i][k]+d[k][j])
cnt = 0
routes = set()
for i in range(n):
    for j in range(i+1,n):
        routes.add(i*n+j)


for i in range(n):
    for k in range(n):
        for j in range(n):
            x = (i-j)*(j-k)*(k-i)
            
            if d[i][j] == d[i][k]+d[k][j] and x != 0:
                try:
                    routes.remove(i*n+j)
                except:
                    pass
cnt = 0
for r in routes:
    i,j = divmod(r,n)
    cnt += d[i][j]

if As != d:
    print(-1)
else:
    print(cnt)

Solution (Python):
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
import numpy as np
N = int(input())
A = np.array([list(map(int, input().split())) for _ in [0]*N], dtype=np.int)
D = csgraph_from_dense(A)
D = floyd_warshall(D, directed=False)

if (A == D).all():
    ans = 0
    D += np.identity(N, int) * (1 << 60)
    for i in range(N):
        for j in range(i+1, N):
            a = np.min(D[i]+D[j])
            if a > D[i, j]:
                ans += D[i, j]
    print(int(ans))
else:
    print(-1)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()

def warshall_floyd(v_count: int, matrix: list) -> list:
    for i in range(v_count):
        for j, c2 in enumerate(row[i] for row in matrix):
            for k, (c1, c3) in enumerate(zip(matrix[j], matrix[i])):
                if c1 > c2+c3:
                    matrix[j][k] = c2+c3
    return matrix

A = [LIST() for _ in range(N)]
dist_matrix = warshall_floyd(N, deepcopy(A))

ans = 0
for i, j in combinations(range(N), 2):
    if A[i][j] != dist_matrix[i][j]:
        print(-1)
        break
    for k in range(N):
        if i == k or j == k:
            continue
        if A[i][k] + A[k][j] == A[i][j]:
            break
    else:
        ans += A[i][j]
else:
    print(ans)

Solution (Python):
from collections import defaultdict
from heapq import heappop, heappush
from itertools import combinations

class Graph:
    def __init__(self, n, edges, weight=False):
        self.n = n
        self.adj = [[] for _ in range(n)]
        self.degree = [0] * n
        self.weight = defaultdict(lambda: 10**18)
        if weight:
            for u, v, weight in edges:
                self.adj[u].append(v)
                self.adj[v].append(u)
                self.degree[v] += 1
                self.weight[(u, v)] = weight
                self.weight[(v, u)] = weight
        else:
            for u, v in edges:
                self.adj[u].append(v)
                self.adj[v].append(u)
                self.degree[v] += 1
                self.weight[(u, v)] = 1
                self.weight[(v, u)] = 1

    def dijkstra(self, start, goal=None):  
        INF = 10**18
        dist = [INF] * self.n
        dist[start] = 0
        heap = [(0, start)]  
        sp_prev = [None] * self.n  
        while heap:
            dist_v, v = heappop(heap)
            if dist[v] < dist_v:
                continue
            for adj in self.adj[v]:
                edge_weight = self.weight[(v, adj)]
                if dist[v] + edge_weight < dist[adj]:
                    dist[adj] = dist[v] + edge_weight
                    sp_prev[adj] = v
                    heappush(heap, (dist[adj], adj))

        if goal is not None:
            if dist[goal] == INF:
                return dist, []
            else:
                path = [goal]
                v = goal
                while v != start:
                    v = sp_prev[v]
                    path.append(v)
                path.reverse()
                return dist, path
        else:
            return dist, sp_prev

    def warshall_floyd(self):  
        
        INF = 10**18
        dist = [[INF] * self.n for _ in range(self.n)]
        for u in range(self.n):
            dist[u][u] = 0
            for v in self.adj[u]:
                dist[u][v] = self.weight[(u, v)]
        for k in range(self.n):
            for u in range(self.n):
                for v in range(self.n):
                    dist[u][v] = min(dist[u][v], dist[u][k] + dist[k][v])
        return dist



n = int(input())
A = [tuple(int(x) for x in input().split()) for _ in range(n)]
dist = []
for i in range(n):
    for j in range(n):
        if i < j:
            dist.append((i, j, A[i][j]))

G = Graph(n, dist, weight=True)
wf = G.warshall_floyd()

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

ans = 0
for i, j in combinations(range(n), 2):
    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)