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: Runtime Error

Solution code:
n = int(input())
INF = 10**12

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

B = [[1]*n for _ in range(n)]
G = A.copy()

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])
      if not (i==j or j==k or k==i):
        if G[i][j] == G[i][k]+G[k][j]:
          B[i][j] = 0
      
if A==G:
  ans = 0
  for i in range(n):
    for j in range(i+1,n):      
      ans += G[i][j] * B[i][j]
  print(ans)
else:
  print(-1)

Submission status: Runtime Error

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

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

Submission status: Runtime Error

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

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix

import numpy as np

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

a = np.array(a)

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

bl = dist == a

if bl.all():
    sm = dist.sum()
    for u in range(n):
        for v in range(n):
            if u == v:
                continue
            rmv = [u, v]
            i_rmv = np.ones(n, dtype=bool)
            i_rmv[rmv] = False

            mn = np.min(dist[u, i_rmv] + dist[v, i_rmv])
            if mn == dist[u, v]:
                sm -= dist[u, v]

    ans = int(sm) // 2
    print(ans)

else:
    print(-1)

Submission status: Runtime Error

Solution code:
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
input=sys.stdin.readline.rstrip()
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)

Submission status: Runtime Error

Solution code:
import sys
inf = float('inf')
N = int(input())
d = [list(map(int, input().split())) for _ in range(N)]
edges = []
for i in range(N):
    for j in range(i+1, N):
        edges.append((A[i][j], i, j))
edges.sort()
for i in range(N):
    d[i][i] = 0
ans=0
for a in range(N):
    for b in range(N):
        flag = True
        for i in range(N):
            if i == a or i == b:
                continue
            if d[a][i]+d[i][b]<d[a][b]:
                print(-1)
                sys.exit()
            if d[a][i]+d[i][b]==d[a][b]:
                flag = False
                break
        if flag:
            ans+=d[a][b]
            
print(ans//2)

Submission status: Runtime Error

Solution code:
def main():
    import numpy as np
    import scipy.sparse.csgraph as sp
    n=int(input())
    p=np.array([np.array(list(map(int,input().split()))) for _ in [0]*n])
    ans=0
    d=np.full((n,n),0)
    for i in range(n):
        for j in range(i+1,n):
            b=p[i][j]
            if b!=np.sort(p[i]+p[j])[2]:
                d[i][j],d[j][i]=b,b
                ans+=b
    s=sp.shortest_path(d)
    if (s==p).all():
        print(ans)
    else:
        print(-1)
main()

Submission status: Runtime Error

Solution code:
from scipy.sparse.csgraph import dijkstra

n=int(input())
arr=[list(map(int,input().split())) for _ in range(n)]
edge=[]
for i in range(n):
  for j in range(n):
    if i>=j:
      continue
    edge.append((arr[i][j],(i,j)))
edge=sorted(edge,key=lambda x:x[0])
g=[[float('inf')]*n for _ in range(n)]
ans=0
for i in range(n-1):
  w,(a,b)=edge[i]
  g[a][b]=w
  g[b][a]=w
  ans+=w
for i in range(n-1,(n*(n-1))//2):
  w,(a,b)=edge[i]
  cost=int(dijkstra(g,indices=a)[b])
  if w==cost:
    continue
  elif w<cost:
    g[a][b]=w
    g[b][a]=w
    ans+=w
  elif w>cost:
    print(-1)
    break
else:
  print(ans)

Submission status: Runtime Error

Solution code:
for k in range(n):
    for i in range(n):
        for j in range(n):
            if a[i][k] + a[k][j] < a[i][j]:
                print(-1)
                exit()
            elif a[i][k] + a[k][j] == a[i][j] and i!=k!=j:
                b[i][j] = 0

ans = 0
for i in range(n):
    for j in range(n):
        if b[i][j]:
            ans += a[i][j]
print(ans//2)

Submission status: Runtime Error

Solution code:
inf = float("inf")
N = int(input())
A = []
for _ in range(N):
    a = [int(s) for s in input().split()]
    A.append(a)
d = [a[:] for a in A]
ans = 0
for i in range(N - 1):
    for j in range(i + 1, N):
        dmin = min([d[i][k] + d[k][j] for k in range(N) if k not in (i, j)])
        if d[i][j] > dmin:
            print(-1)
            exit()
        if d[i][j] != dmin:
            ans += d[i][j]
print(ans)

Submission status: Runtime Error

Solution code:
N=int(input())
MP=[list(map(int,input().split())) for i in range(N)]
MP2=[]
for li in MP:
    MP2.append(li.copy())

Submission status: Runtime Error

Solution code:
N= int(input())
MP=[list(map(int,input().split())) for i in range(N)]
MP2=[]
for li in MP:
    MP2.append(li.copy())

Submission status: Runtime Error

Solution code:
N= int(input())
MP=[list(map(int,input().split())) for i in range(N)]
MP2=[]
for li in MP:
    MP2.append(li.copy())

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

Submission status: Runtime Error

Solution code:
N= int(input())
MP=[list(map(int,input().split())) for i in range(N)]
MP2=[]
for li in MP:
    MP2.append(li.copy())

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

# ワーシャルフロイド
for k in range(N):
    for i in range(N):
        for j in range(N):
            cand = MP2[i][k] + MP2[k][j]
            if cand <= MP2[i][j]:
                MP2[i][j] = cand
                if (i != k and j != k):
                    MP3[i][j] = k

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

checked=set()

Submission status: Runtime Error

Solution code:
from scipy.sparse.csgraph import floyd_warshall as wf
n=int(input())
s=[list(map(float,input().split()))for i in range(n)]
a=wf(s,directed=False).tolist()
if s!=a:
    print(-1)
else:
    c=0
    for i in range(n-1):
        for j in range(i+1,n):
            for d in range(n):
                if d!=i and d!=j:
                    if s[i][j]>=s[i][d]+s[d][j]:
                        break
            else:
                c+=int(s[i][j])
else:
    print(c)

Submission status: Runtime Error

Solution code:
from scipy.sparse.csgraph import floyd_warshall as wf
n=int(input())
s=[list(map(float,input().split()))for i in range(n)]
a=wf(s,directed=False).tolist()
if s!=a:
    print(-1)
else:
    c=0
    for i in range(n-1):
        for j in range(i+1,n):
            for d in range(n):
                if d!=i and d!=j:
                    if s[i][j]>=s[i][d]+s[d][j]:
                        break
            else:
                c+=int(s[i][j])
print(c)

Submission status: Runtime Error

Solution code:
N=int(input())
dist=[list(map(int,input().split())) for i in range(N)]
ans=sum([sum(dist[i]) for i in range(N)])
ans//=2
for i in range(N):
    if ans<0:break
    for j in range(i+1,N):
        if ans<0:break
        for k in range(j+1,N):
            S=sum([dist[i][j],dist[i][k],dist[j][k]])/2
            M=max([dist[i][j],dist[i][k],dist[j][k]])
            if S==M:ans-=max(a,b,c)
            elif S<M:
                ans=-1*float('inf')
                break
if ans<0:ans=-1
print(ans)

Submission status: Runtime Error

Solution code:
INF = 10 ** 20
n = int(input())
edges = [list(map(int, input().split())) for _ in range(n)]
dist = [[INF] * n for _ in range(n)]

edgeList = []
for i in range(n):
    for j in range(i, n):
        edgeList.append((edges[i][j], i, j))
edgeList.sort()

for k in range(n):
    for i in range(n):
        for j in range(n):
            dist[i][j] = min(dist[i][j], edges[i][k] + edges[k][j])
ans = 0
for c, i, j in edgeList:
    minCost = min([dist[i][k] + dist[k][j] for k in range(n) if (k != i and k != j)])
    if c > minCost:
        print(-1)
        break
    if c < minCost:
        ans += c

else:
    print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

n = int(input())

a = []

for i in range(n):
    a_list = list(map(int, input().split()))
    a_dict = {i:e for i,e in enumerate(a_list[:i])}
    a.append(a_dict)

if n == 1:
    print("-1")
    exit()

elif n == 2:
    print(a[0][1])
    exit()

# Minimam total path length
min_total = 0

for i in range(n):
    dim = i+1
    if dim == 1:
        continue
    elif dim == 2:
        min_total += a[1][0]
        continue

    paths_to_subgraph = []
    a_sorted = sorted(a[i].items(), key=lambda e:e[1])

    dest, path = a_sorted.pop(0)
    paths_to_subgraph.append((dest, path))
    min_total += path

    for dest, path in a_sorted:
        create_path = True
        for detour in paths_to_subgraph:
            detour_path = detour[1] + a[max([dest,detour[0]])][min([dest,detour[0]])]
            if path > detour_path:
                print("-1")
                exit()
            elif path == detour_path:
                create_path = False

        if create_path:
            for detour in paths_to_subgraph:
                detour_path = detour[1] + path
                minpath = a[max([dest,detour[0]])][min([dest,detour[0]])]
                if minpath > detour_path:
                    print("-1")
                    exit()
                elif minpath == detour_path:
                  # Delete path
                  min_total -= minpath
            paths_to_subgraph.append((dest, path))
            min_total += path

print(min_total)

Submission status: Runtime Error

Solution code:
G=[]
for _ in range(n):
    tmp=list(map(int,input().split()))
    G.append(tmp)

Dij=Dijkstra()
for i in range(n):
    result=Dij.dijkstra(G,i)
    dis=result[0]
    pre=result[1]
    for j in range(n):
        if(dis[j] < G[i][j]):
            print(-1)
            sys.exit()
        if(dis[j] == G[i][j] and pre[j]!=i):
            G[i][j]=float("inf")

ans=0
for i in range(n):
    for j in range(n):
        if(G[i][j]!=float("inf")):
            ans+=G[i][j]
print(ans//2)

Submission status: Runtime Error

Solution code:
n = int(input())

dp = [[int(x) for x in input().split()] for _ in range(n)]

if n == 1:
    print(0)
    exit()

ans = 0
for i in range(n - 1):
    for j in range(i + 1, n):
        temp = []
        for k in range(n):
            if k != i and k != j:
                temp.append(dp[i][k] + dp[k][j])
        if min(temp) < dp[i][j]:
            print(-1)
            exit()
        if min(temp) > dp[i][j]:
            ans += dp[i][j]

print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse.csgraph import floyd_warshall
n = int(input())
a = np.array([[int(i) for i in input().split()] for i in range(n)])
d,ans = floyd_warshall(a,directed=False),0
if any(a[i][j]!=d[i][j] for i in range(n) for j in range(n)): ans = -1
else:
	inf = float("inf")
	for i in range(n): a[i][i] = inf
	for i in range(n):
		for j in range(i+1,n):
			num = np.min(a[i]+a[j])
			if num>a[i][j]: ans+=a[i][j]
print(int(ans))

Submission status: Runtime Error

Solution code:
from scipy.sparse.csgraph import floyd_warshall
import numpy as np

file = open("ABC074D.txt", "r")

n = int(file.readline())
graph = np.array([[0 for _ in range(n)] for _ in range(n)], dtype=float)
for i in range(n):
    graph[i] = np.array(list(map(int, file.readline().split())))
    
# ワーシャルフロイドで最短距離出す
shortest = floyd_warshall(graph, directed=False)


if any([graph[i,j] != shortest[i,j] for i in range(n) for j in range(n)]):
    print(-1)
    
else:
    total = 0
    INF = float("inf")
    
    for i in range(n):
        graph[i,i] = INF
    
    for i in range(n):
        for j in range(i+1,n):
            via_k = np.min(graph[i] + graph[j])
            
            if via_k > graph[i,j]:
                total += graph[i,j]
                
    print(int(total))

Submission status: Runtime Error

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

ans = 0
for u in range(n):
    for v in range(u + 1, n): 
        dist = a[u][v]
        cd = min([a[u][i] + a[i][v] for i in [x for x in range(0, n) if x != u and x != v]])
        if dist > cd:
            print(-1)
            exit(0)
        if dist < cd:
            ans += dist

print(ans)

Submission status: Runtime Error

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

if a != at: 
    print(-1)
    exit(0)

import itertools
from array import array

aa = array('L', itertools.chain(*a))

ans = 0
for u in range(n):
    un = u * n
    for v in range(u + 1, n): 
        dist = aa[un + v]
        cd = min([aa[un + i] + aa[i * n + v] for i in range(n) if i != u and i !=v])
        if dist > cd:
            print(-1)
            exit(0)
        if dist < cd:
            ans += dist

print(ans)

Submission status: Runtime Error

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

if a != at: 
    print(-1)
    exit(0)

import itertools
from array import array

aa = array('L', itertools.chain(*a))

ans = 0
for u in range(n):
    un = u * n
    for v in range(u + 1, n): 
        dist = aa[un + v]
        cd = min([aa[un + i] + aa[i * n + v] for i in range(n) if i != u and i !=v])        if dist > cd:
            print(-1)
            exit(0)
        if dist < cd:
            ans += dist

print(ans)

Submission status: Runtime Error

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

if a != at: 
    print(-1)
    exit(0)

import itertools
from array import array

aa = array('L', itertools.chain(*a))

ans = 0
for u in range(n):
    un = u * n
    for v in range(u + 1, n): 
        dist = aa[un + v]
        cd = min([aa[un + i] + aa[i * n + v] for i in range(n) if i != u and i !=v]))])
        if dist > cd:
            print(-1)
            exit(0)
        if dist < cd:
            ans += dist

print(ans)

Submission status: Runtime Error

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

if a != at: 
    print(-1)
    exit(0)

dr = list()
for u in range(n):
    for v in range(u + 1, n): 
        dist = a[u][v]
        cd = min([a[u][i] + a[i][v] for i in [x for x in range(0, n) if x != u and x != v]])
        if dist > cd:
            print(-1)
            exit(0)
        if dist < cd:
            dr.append(a[u][v])

print(sum(dr))

Submission status: Runtime Error

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

if a != at: 
    print(-1)
    exit(0)

for u in range(0, n): 
    for v in range(u + 1, n): 
        for i in range(0, n): 
            if a[u][v] > a[u][i] + a[i][v]:
                print(-1)
                exit(0)

dr = list()
for u in range(0, n): 
    for v in range(u + 1, n): 
        if a[u][v] < min([a[u][i] + a[i][v] for i in [x for x in range(0, n) if x != u and x != v]]):
            dr.append(a[u][v])

print(sum(dr))

Submission status: Runtime Error

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

def calc(N, A):
    r = 0
    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: Runtime Error

Solution code:
import numpy as np

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



MAX = 10000000000

raw_data = read_data()
tarray = []
for each in raw_data:
    tarray.append(each.split())
A = np.array(tarray, dtype='int32')
B = np.zeros(A.shape, dtype='int32')

N = A.shape[0]

def distance2(i, j, done=[]):
    if(i == j):
        return 0

    min_dis = MAX
    min_index = -1
    for n in range(N):
        if((B[i][n] == 1)and(n not in done)and(n != j)):
            temp_dis = distance2(i, n, [i, j]) + distance2(n, j, [i, j])

            if(temp_dis < min_dis):
                min_index = n
                min_dis = temp_dis

    if(B[i][j] == 1)and(A[i][j] < min_dis):
        return A[i][j]
    else:
        return min_dis


def Restoring_Road_Network():

        # todo = list(range(N))
    min_dis_all = A[A.nonzero()].min()
    try:
        LOCAL_FLAG
        print("min value is", min_dis_all)
    except:
        pass

    for i in range(0, N):
        row = A[i]
        np.argmin(A[i])
        # print(row)
        min = MAX
        min_index = -1

        for j in range(0, N):
            if(row[j] == 0):
                continue
            elif(row[j] < min_dis_all*2):
                B[i][j] = 1
                B[j][i] = 1

            if(row[j] < min):
                min = row[j]
                min_index = j
        #
        # print(min)
        # print(min_index)
        B[i][min_index] = 1
        B[min_index][i] = 1


    distance_array = A*B
    not_available = False
    for i in range(N):
        for j in range(N):
            temp = distance2(i,j)
            # print(temp, " ", end='')
            if(temp != A[i][j]):
                not_available = True
        # print()

    try:
        LOCAL_FLAG
        print(B)
    except:
        pass

    if(not_available):
        print(-1)
    else:
        print(int(distance_array.sum(dtype=np.int64)/2))



# Sugar_water()
Restoring_Road_Network()

Submission status: Runtime Error

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)
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: Runtime Error

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)], dtype = 'int32')

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

if np.any(G != G2):
    print(-1)
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: Runtime Error

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)], dtype = 'int64')

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

if np.any(G != G2):
    print(-1)
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: Runtime Error

Solution code:
def Warshall_Floyd(edges,N):
  """頂点N個のグラフ上の隣接行列edgesが与えられたとき, 
  2点間の最短距離距離を隣接行列で返す"""
  for k in range(N):
    for i in range(N):
      for j in range(N):
        edges[i][j]=min(edges[i][j],edges[i][k]+d[k][j])
  return edges
 
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
    if need: ans+=A[i][j]
print(ans)

Submission status: Runtime Error

Solution code:
import sys
from sys import stdin
input = stdin.readline
N=int(input())
edges=[list(map(int,input().split())) for i in range(N)]
for k in range(N):
  for i in range(N):
    for j in range(i):
      if edges[i][j]>edges[i][k]+edges[k][j]:
        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 and A[i][j]==A[i][k]+A[k][j]:
        need=0
        break
    if need:ans+=A[i][j]
print(ans-1)

Submission status: Runtime Error

Solution code:
import sys
from sys import stdin
input = stdin.readline
N=int(input())
edges=[list(map(int,input().split())) for i in range(N)]
for k in range(N):
  for i in range(N):
    for j in range(i):
      if edges[i][j]>edges[i][k]+edges[k][j]:
        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 and A[i][j]==A[i][k]+A[k][j]:
        need=0
        break
    if need:ans+=A[i][j]
print(ans)

Submission status: Runtime Error

Solution code:
def Warshall_Floyd(edges,N):
  """頂点N個のグラフ上の隣接行列edges(空欄はinfとせよ)が与えられたとき, 
  2点間の最短距離距離を隣接行列で返す"""
  for k in range(0:N:2):
    for i in range(N):
      for j in range(i):
        if edges[i][j]>edges[i][k]+edges[k][j]: return 1
  return 0
 
import sys
from sys import stdin
input = stdin.readline
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
print(ans)

Submission status: Runtime Error

Solution code:
import copy
INF = float('inf')
N = int(input())
a = []
for i in range(N):
    a.append(list(map(int, input().split())))
flag = 0
length = 0


for i in range(N):
    for j in range(N):
        muda = 0
        for k in range(N):
            if k == i or k == j:
                continue
            mix = b[i][k] + b[k][j]
            if a[i][j] > mix:
                flag = 1
            elif a[i][j] == mix:
                muda = 1
        if muda == 1:
            continue
        length += a[i][j]

if (flag == 0):
    length = int(length/2)
else:
    length = -1
print(length)

Submission status: Runtime Error

Solution code:
import sys

sys.stdin = open('d1.in')


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


def read_str_list():
    return input().split()


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


def read_str():
    return input()


def solve():
    n = read_int()
    d = [read_int_list() for i in range(n)]
    res = 0
    for i in range(n):
        for j in range(i+1, n):
            ok = True
            for k in range(n):
                if k != i and k != j:
                    ok &= d[i][j] < d[i][k] + d[k][j]
                    if d[i][j] > d[i][k] + d[k][j]:
                        return -1
            if ok:
                res += d[i][j]
    return res


def main():
    res = solve()
    print(res)


main()

Submission status: Runtime Error

Solution code:
n = int(input())
a_all = []
for i in range(n):
    a_list = input().split()
    a_list = [int(a) for a in a_list]
    a_all.append(a_list)

a_array = np.array(a_all)
for i in range(n):
    a_array[i][:i] = 0

a_goukeiyou = np.copy(a_array)
    
huseiritsu = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        for k in range(j+1,n):
            hen1 = a_array[i][j]
            hen2 = a_array[j][k]
            hen3 = a_array[i][k]
            if hen1 <= hen2 + hen3 and hen2 <= hen1+hen3 and hen3 <= hen1 + hen2:
                if hen1 == hen2 + hen3:
                    a_goukeiyou[i][j]=0
                elif hen2 == hen3 + hen1:
                    a_goukeiyou[j][k]=0
                elif hen3 == hen1 + hen2:
                    a_goukeiyou[i][k]=0
            else:
                huseiritsu = 1
                break

if huseiritsu == 1:
    print("-1")
else:
    print(a_goukeiyou.sum())

Submission status: Runtime Error

Solution code:
def print_path(prev, cost):
    for i in range(len(prev)):
        print("%d, prev = %d, cost = %d" %  (i, prev[i], cost[i]))

def get_path(start, goal, prev):
    path = []
    now = goal
    path.append(now)
    while True:
        path.append(prev[now])
        if prev[now] == start: break
        now = prev[now]
    path.reverse()
    return path


def search(glaph, start, goal):
    MAX_VAL = 0x10000000
    g_size = len(glaph)
    visited = [False] * g_size
    cost = [MAX_VAL] * g_size
    prev = [None] * g_size
    cost[start] = 0
    prev[start] = start
    now = start
    while True:
        min = MAX_VAL
        next = -1
        visited[now] = True
        for i in range(g_size):
            if visited[i]: continue
            if glaph[now][i]:
                tmp_cost = glaph[now][i] + cost[now]
                if cost[i] > tmp_cost:
                    cost[i] = tmp_cost
                    prev[i] = now
            if min > cost[i]:
                min = cost[i]
                next = i
        if next == -1: break
        now = next
    return cost[goal]

def solve():
    N = int(input())
    A = []
    for _ in range(N):
        tmp = list(map(int, input().split()))
        A.append(tmp)
        
    cnt = 0
    min_v = 1e10
    for i in range(N):
        for j in range(N):
            if i == j:
                pass
            elif A[i][j] == search(A, i, j):
                B = search(A, i, j)
                if B <= min_v:
                  min = B
                 cnt += 1
             else:
                break
    
    if cnt == N**2 - N:
        print(min)
    else:
        print(-1)
        
solve()