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



Sample input:
3
0 1 3
1 0 2
3 2 0


Sample output:
3

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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
#print A


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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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  # should be > 2*10**9
    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]
                # print(i, j)
            elif dis_two_node < C[i,j]:
                print(-1)
                exit()

    print(total_dis)

Restoring_Road_Network()

Submission status: Accepted

Solution code:
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  # should be > 2*10**9
    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]
                # print(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])
            # print(A[i][i+1:])
            # print (i, j, d1, d2)
            if d1 >= d2:
                if d1 > d2:
                    print(-1)
                    exit()
            else:
                result += d1
    print(result)

Restoring_Road_Network3()

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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):
                # compare from-to / from-経由地点-to
                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)

Submission status: Accepted

Solution code:
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)

Submission status: Runtime Error

Solution code:
import heapq
import sys

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

T = {}
for i in range(N):
    for j in range(i, N):
        if i != j:
            T[(i, j)] = A[i][j]

T = sorted(T.items(), key = lambda x:x[1], reverse=True)

def dijkstra(V, start, Cost):
    routes = [float("inf")]*V
    routes[start] = 0
    minHeap = []
    used = [0]*V
    heapq.heappush(minHeap, (0, start))

    while minHeap:
        (c, current) = heapq.heappop(minHeap)
        if used[current] == 0:
            used[current] = 1
            for road in range(V):
                if Cost[current][road] != -1:
                    if routes[road] > c + Cost[current][road]:
                        routes[road] = c + Cost[current][road]
                        heapq.heappush(minHeap, (c + Cost[current][road], road))
    return routes

Cost = [[-1]*N for _ in range(N)]
ans = 0
for i in range(N):
    D, c = T[i]
    x, y = D
    Cost[x][y] = c
    Cost[y][x] = c
    ans += c

for i in range(N):
    P = dijkstra(N, i, Cost)
    for j in range(N):
        if P[j] != A[i][j]:
            print(-1)
            sys.exit()

for i in range(N):
    D, c = T[i]
    x, y = D
    Cost[x][y] = -1
    Cost[y][x] = -1
    P_1 = dijkstra(N, x, Cost)
    P_2 = dijkstra(N, y, Cost)
    n = 0
    for j in range(N):
        if P_1[j] != A[x][j] or P_2[j] != A[y][j]:
            Cost[x][y] = c
            Cost[y][x] = c
            n = 1
            break
    if n == 0:
        ans -= c
print(ans)

Submission status: Runtime Error

Solution code:
import heapq
import sys

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

T = {}
for i in range(N):
    for j in range(i, N):
        if i != j:
            T[(i, j)] = A[i][j]

T = sorted(T.items(), key = lambda x:x[1])

def dijkstra(V, start, Cost):
    routes = [float("inf")]*V
    routes[start] = 0
    minHeap = []
    used = [0]*V
    heapq.heappush(minHeap, (0, start))

    while minHeap:
        (c, current) = heapq.heappop(minHeap)
        if used[current] == 0:
            used[current] = 1
            for road in range(V):
                if Cost[current][road] != -1:
                    if routes[road] > c + Cost[current][road]:
                        routes[road] = c + Cost[current][road]
                        heapq.heappush(minHeap, (c + Cost[current][road], road))
    return routes

Cost = [[-1]*N for _ in range(N)]
ans = 0
for i in range(N):
    A, c = T[i]
    x, y = A
    P = dijkstra(N, x, Cost)
    if P[y] > c:
        Cost[x][y] = c
        Cost[y][x] = c
        ans += c
    elif P[y] < c:
        print(-1)
        sys.exit()
print(ans)

Submission status: Runtime Error

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

fill_diagonal(A, 10**9)

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

print(ans)

Submission status: Runtime Error

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

ans = 0
for k in range(N):
    for i in range(N):
        if i == k: continue
        for j in range(i+1,N):
            if j == k: continue
            Aikj = A[i][k][0] + A[k][j][0]
            if A[i][j][0] > Aikj:
                ans = -1
            if A[i][j][0] == Aikj:
                A[i][j][1] = False

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

Submission status: Runtime Error

Solution code:
import sys
N = int(input())
A = [[(int(x),True) for x in input().split()] for _ in range(N)]

ans = 0
for k in range(N):
    for i in range(N):
        if i == k: continue
        for j in range(i+1,N):
            if j == k: continue
            Aikj = A[i][k][0] + A[k][j][0]
            if A[i][j][0] > Aikj:
                ans = -1
            if A[i][j][0] == Aikj:
                A[i][j][1] = False

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

Submission status: Runtime Error

Solution code:
import sys
N = int(input())
A = [[(int(x),True) for x in input().split()] for _ in range(N)]

for k in range(N):
    for i in range(N):
        if i == k: continue
        for j in range(i+1,N):
            if j == k: continue
            Aikj = A[i][k][0] + A[k][j][0]
            if A[i][j][0] > Aikj:
                print(-1)
                sys.exit()
            if A[i][j][0] == Aikj:
                A[i][j][1] = False

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

Submission status: Runtime Error

Solution code:
import sys
N = int(input())
A = [[(int(x),True) for x in input().split()] for _ in range(N)]

for k in range(N):
    for i in range(N):
        if i == k: continue
        for j in range(i+1,N):
            if j == k: continue
            Aikj = A[i][k][0] + A[k][j][0]
            if A[i][j][0] > Aikj:
                print(-1)
                sys.exit()
            if A[i][j][0] == Aikj:
                A[i][j][1] = False

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

Submission status: Runtime Error

Solution code:
import sys
from copy import deepcopy
from collections import defaultdict
readline=sys.stdin.readline
read=sys.stdin.read

from collections import defaultdict
from heapq import heapify,heappop,heappush

class Graph():
    def __init__(self, vertices, edges, weighted=True, directed=False):
        self.vertices=vertices
        self.directed=directed
        self.edges=[]
        if weighted:
            self.weights=defaultdict(lambda:0)
        self.neiborhoods=defaultdict(list)
        for edge in edges:
            self.edges.append((edge[0],edge[1]))
            self.neiborhoods[edge[0]].append(edge[1])
            self.neiborhoods[edge[1]].append(edge[0])
            if weighted:
                self.weights[(edge[0],edge[1])]=edge[2]
                if not directed:
                    self.weights[(edge[1],edge[0])]=edge[2]
    
    def dijkstra(self,vertex):
        for x in iter(self.weights.values()):
            if x<0:
                return None
        inf=float('inf')
        n=len(self.vertices)
        cost=[inf]*(n)
        cost[vertex]=0
        hq=[(self.weights[(vertex,vertex)],vertex)]
        heapify(hq)
        while hq:
            cvw=heappop(hq)
            if cvw[0]>cost[cvw[1]]:
                continue
            for w in self.neiborhoods[cvw[1]]:
                cand=cvw[0]+self.weights[(cvw[1],w)]
                if cost[w]>cand:
                    cost[w]=cand
                    heappush(hq,(cand,w))
        return cost

def main():
    n=int(readline())
    a=[list(map(int,l.split())) for l in read().splitlines()]
    v=list(range(n))
    e=[(i,j,a[i][j]) for i in range(n) for j in range(i+1,n)]
    g=Graph(v,e)
    #for k in range(n):
    #    for i in range(n):
    #        for j in range(n):
    #            cost[i][j]=min(cost[i][j],cost[i][k]+cost[k][j])
    cost=[g.dijkstra(i) for i in v]
    s=0
    for i in range(n):
        for j in range(i,n):
            if cost[i][j]<a[i][j]:
                print(-1)
                return None
            p=[cost[i][k]+cost[k][j]-cost[i][j] for k in range(n) if k!=i and k!=j]
            if min(p)>0:
                s+=a[i][j]
    print(s)

if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
from copy import deepcopy
from collections import defaultdict
readline=sys.stdin.readline
read=sys.stdin.read

def main():
    n=int(readline())
    a=[list(map(int,l.split())) for l in read().splitlines()]
    cost=deepcopy(a)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                cost[i][j]=min(cost[i][j],cost[i][k]+cost[k][j])
    s=0
    for i in range(n):
        for j in range(i+1,n):
            if cost[i][j]<a[i][j]:
                print(-1)
                return None
            detour=min([cost[i][k]+cost[k][j] for k in range(n) if k!=i and k!=j])
            if detour>cost[i][j]:
                s+=a[i][j]
    print(s)

if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
import deepcopy from copy
readline=sys.stdin.readline
read=sys.stdin.read

def main():
    n=int(readline())
    a=[list(map(int,lst)) for lst in read().splitlines()]
    cost=deepcopy(a)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                cost[i][j]=min(cost[i][j],cost[i][k]+cost[k][j])
    s=0
    for i in range(i):
        for j in range(i+1,n)
        if cost[i][j]<a[i][j]:
            print(-1)
            return None
        detour=min([cost[i][k]+cost[k][j] for k in range(n) if k!=i and k!=i])
        if detour>cost[i][j]:
            s+=a[i][j]
    print(s)

if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict
readline=sys.stdin.readline
read=sys.stdin.read

def main():
    n=int(readline())
    a=[list(map(int,sys.stdin.readline().split())) for _ in range(n)]
    wts=dict(((i,j),a[i][j]) for i in range(n) for j in range(n))
    cost=defaultdict(int)
    cost.update(wts)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                cost[(i,j)]=min(cost[(i,j)],cost[(i,k)]+cost[(k,j)])
    edges=[e for e in wts.keys() if e[0]<e[1]]
    edges.sort(key=wts.get,reverse=True)
    s=0
    for e in edges:
        if cost[e]<wts[e]:
            print(-1)
            return None
        detour=min([cost[(e[0],i)]+cost[(i,e[1])] for i in range(n) if i!=e[0] and i!=e[1]])
        if detour>cost[e]:
            s+=wts[e]
    print(s)

if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict
readline=sys.stdin.readline
read=sys.stdin.read

def main():
    n=int(readline())
    a=[list(map(int,sys.stdin.readline().split())) for _ in range(n)]
    wts=dict(((i,j),a[i][j]) for i in range(n) for j in range(n))
    cost=defaultdict(int)
    cost.update(wts)
    for k in range(n):
        cost.update([((i,j),min(cost[(i,j)],cost[(i,k)]+cost[(k,j)])) \
          for i in range(n) for j in range(n)])
    edges=[e for e in wts.keys() if e[0]<e[1]]
    edges.sort(key=wts.get,reverse=True)
    s=0
    for e in edges:
        if cost[e]<wts[e]:
            print(-1)
            return None
        detour=min([cost[(e[0],i)]+cost[(i,e[1])] for i in range(n) if i!=e[0] and i!=e[1]])
        if detour>cost[e]:
            s+=wts[e]
    print(s)

if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
import numpy as np
N = int(input())
A = np.loadtxt(open(0), 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)

Submission status: Runtime Error

Solution code:
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
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall

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

Submission status: Runtime Error

Solution code:
def warshall_floyd(N, A):
    dist = A.copy()
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist


def main():
    N = int(input())
    A = [list(map(int, input().split(' '))) for _ in range(N)]
    wf = warshall_floyd(N, A)
    edges = list()
    for i in range(N):
        for j in range(i + 1, N):
            edges.append((A[i][j], i, j))  # (cost, from, to)
    edges.sort(key=lambda e: e[0])
    ans = 0
    for edge in edges:
        cost, from_node, to_node = edge
        if A[from_node][to_node] > wf[from_node][to_node]:
            print(-1)
            return
        to_be_added = True
        for via_node in range(N):
            if via_node in [from_node, to_node]:
                continue
            if wf[from_node][to_node] == wf[from_node][via_node] + wf[via_node][to_node]:
                to_be_added = False
                break
        if to_be_added:
            ans += A[from_node][to_node]
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
    def size(self, x):
        return -self.parents[self.find(x)]
        
    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())
    
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def main():
    N = int(input())
    l = []
    d = {}
    u = UnionFind(N)
    for i in range(N):
        a = list(map(int, input().split()))
        for j in range(N):
            if i < j:
                l.append((a[j], i, j))
                d[(i, j)] = a[j]
                d[(j, i)] = a[j]
    l.sort()
    r = [[0]*N for _ in range(N)]
    ans = 0
    for k, i, j in l:
        if not u.same(i,j):
            r[i][j] = k
            r[j][i] = k
            ans += k
            for w in u.members(i):
                if w == i:
                    continue
                if r[i][w] + k < d[(w,j)]:
                    return -1
                else:
                    r[w][j] = r[i][w] + k
                    r[j][w] = r[i][w] + k
            for w in u.members(j):
                if w == j:
                    continue
                if r[j][w] + k < d[(w,i)]:
                    return -1
                else:
                    r[w][i] = r[j][w] + k
                    r[i][w] = r[j][w] + k
            u.union(i,j)
            continue
        if r[i][j] < k:
            return -1
        elif r[i][j] == k:
            continue
        else:
            r[i][j] = k
            r[j][i] = k
            ans += k
            for w in u.members(i):
                r[i][w] = r[w][i] = min(r[i][w], r[j][w] + k)
                if r[i][w] < d[(i,w)]:
                    return -1
                r[j][w] = r[w][j] = min(r[j][w], r[i][w] + k)
                if r[j][w] < d[(j,w)]:
                    return -1
    return ans
print(main())

Submission status: Runtime Error

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

from scipy.sparse.csgraph import floyd_warshall
wf=floyd_warshall(a)

if not (a==wf).all() :
    print(-1)
    exit()

Submission status: Runtime Error

Solution code:
N = int(input())
INF = 10**10
cost = [[INF]*N for _ in range(N)]

for u in range(N):
    C = list(map(int, input().split()))
    for v in range(N):
        if u==v: # INFのままにする
            continue
        cost[u][u] = C[u]
 
ans = 0
for u in range(N):
    for v in range(j+1,N):
        mn = INF # u-w-vのような経路の中で最小の距離を求める
        for w in range(N):
            mn = min(mn, cost[u][w]+cost[w][v])    
        if (cost[u][v] > mn): # 与えられた行列が最短経路ではない
            print (-1)
            exit()
        elif (cost[u][v] < mn): # 等しくない場合はu-vを直接結ぶ橋が必要 
            ans += cost[u][v]                      
print (ans)

Submission status: Runtime Error

Solution code:
N = int(input())
INF = 10**10
cost = [[INF]*N for _ in range(N)]

for u in range(N):
    C = list(map(int, input().split()))
    for v in range(N):
        if u==v: # INFのままにする
            continue
        cost[u][v] = C[u]
 
ans = 0
for u in range(N):
    for v in range(j+1,N):
        mn = INF # u-w-vのような経路の中で最小の距離を求める
        for w in range(N):
            mn = min(mn, cost[u][w]+cost[w][v])    
        if (cost[u][v] > mn): # 与えられた行列が最短経路ではない
            print (-1)
            exit()
        elif (cost[u][v] < mn): # 等しくない場合はu-vを直接結ぶ橋が必要 
            ans += cost[u][v]                      
print (ans)