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: Wrong Answer

Solution code:
import itertools
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall, minimum_spanning_tree

N, *Z = [int(_) for _ in open(0).read().split()]
A = []
B = []
C = []
for z in range(N * N):
    x, y = divmod(z, N)
    A += [x]
    B += [y]
    C += [Z[z]]
G = csr_matrix((C, (A, B)), (N, N))
F = np.array(floyd_warshall(G, directed=1), dtype=np.int64)
Z = np.array(Z).reshape(N, N)
if np.all(F==Z):
    ans=np.sum(Z)
    for i,j in itertools.product(range(N),repeat=2):
        if i==j:
          continue
        ans-=Z[i,j]*(np.sum(Z[i]+Z[j]==Z[i,j])-2)
    ans //= 2
    print(ans)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import itertools
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall, minimum_spanning_tree

N, *Z = [int(_) for _ in open(0).read().split()]
A = []
B = []
C = []
for z in range(N * N):
    x, y = divmod(z, N)
    A += [x]
    B += [y]
    C += [Z[z]]
G = csr_matrix((C, (A, B)), (N, N))
F = np.array(floyd_warshall(G, directed=1), dtype=np.int64)
Z = np.array(Z).reshape(N, N)
if np.all(F==Z):
    ans=np.sum(Z)
    for i,j in itertools.product(range(N),repeat=2):
      ans-=Z[i,j]*(np.sum(Z[i]+Z[j]==Z[i,j])-2)
    ans //= 2
    print(ans)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())
a = list(map(int,read().split()))

ans = sum(a)//2
for i in range(n-2):
    for j in range(i+1,n-1):
        for k in range(j+1,n):
            x = [a[i*n+j], a[i*n+k], a[j*n+k]]
            x.sort()
            if(x[2] > x[0]+x[1]):
                print(-1)
                exit()
            elif(x[2] == x[0]+x[1]):
                ans -= x[2]

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
d = [[10**16]*n for i in range(n)]
L = []
ans = 0
for i in range(n):
    d[i][i] = 0
for i in range(n):
    L = list(map(int,input().split()))
    for j in range(i+1):
        d[i][j] = L[j]
        d[j][i] = L[j]
        ans += L[j]
flag = True
for i in range(n):
  for j in range(i+1):
    for k in range(n):
      if d[i][j] > d[i][k]+d[k][j]:
        flag = False
        break
      else:
        if d[i][j] == d[i][k]+d[k][j] and i != k and k != j:
          ans -= d[i][j]
if flag:
  print(ans)
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
n = int(input())
d = [[float('inf')]*n for i in range(n)]
L = []
ans = 0
for i in range(n):
    d[i][i] = 0
for i in range(n):
    L = list(map(int,input().split()))
    for j in range(i+1):
        d[i][j] = L[j]
        d[j][i] = L[j]
        ans += L[j]
flag = True
for i in range(n):
  for k in range(n):
    for j in range(i+1):
      if i != k and k != j:
        if d[i][j] > d[i][k]+d[k][j]:
          flag = False
          break
        else:
          if d[i][j] == d[i][k]+d[k][j]:
            ans -= d[i][j]
if flag:
  print(ans)
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
n = int(input())
d = [[10**16]*n for i in range(n)]
L = []
ans = 0
for i in range(n):
    d[i][i] = 0
for i in range(n):
    L = list(map(int,input().split()))
    for j in range(i+1):
        d[i][j] = L[j]
        d[j][i] = L[j]
        ans += L[j]
flag = True
for i in range(n):
  for k in range(n):
    for j in range(i+1):
      if i != k and k != j:
        if d[i][j] > d[i][k]+d[k][j]:
          flag = False
          break
        else:
          if d[i][j] == d[i][k]+d[k][j]:
            ans -= d[i][j]
if flag:
  print(ans)
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
n = int(input())
d = [[10**16]*n for i in range(n)]
L = []
for i in range(n):
    d[i][i] = 0
for i in range(n):
    L = list(map(int,input().split()))
    for j in range(n):
        d[i][j] = L[j]
        d[j][i] = L[j]
flag = True
for i in range(n):
  for k in range(n):
    for j in range(n):
      cur = d[i][j]
      if i != k and k!= j:
        d[i][j] = min(d[i][j],d[i][k]+d[k][j])
        if cur != d[i][j]:
          flag = False
          break
if not flag:
  print(-1)
else:
  ans = 0
  for i in range(n):
    for k in range(n):
      for j in range(n):
        if i != k and k != j:
          if d[i][j] == d[i][k]+d[k][j]:
            ans += d[i][j]
  t = 0
  for i in range(n):
    t += sum(d[i])
  print((t-ans)//2)

Submission status: Wrong Answer

Solution code:
n = int(input())
d = [[10**18]*n for i in range(n)]
L = []
for i in range(n):
    d[i][i] = 0
for i in range(n):
    L = list(map(int,input().split()))
    for j in range(n):
        d[i][j] = L[j]
        d[j][i] = L[j]
flag = True
for i in range(n):
  for k in range(n):
    for j in range(n):
      cur = d[i][j]
      d[i][j] = min(d[i][j],d[i][k]+d[k][j])
      if cur != d[i][j]:
        flag = False
        break
if not flag:
  print(-1)
else:
  ans = 0
  for i in range(n):
    for k in range(n):
      for j in range(n):
        if i != k and k != j:
          if d[i][j] == d[i][k]+d[k][j]:
            ans += d[i][j]
  t = 0
  for i in range(n):
    t += sum(d[i])
  print((t-ans)//2)

Submission status: Wrong Answer

Solution code:
n = int(input())
d = [[10**14]*n for i in range(n)]
L = []
dist = []
for i in range(n):
    d[i][i] = 0
for i in range(n):
    L = list(map(int,input().split()))
    dist.append(L)
    for j in range(n):
        d[i][j] = L[j]
        d[j][i] = L[j]
flag = True
for i in range(n):
  for k in range(n):
    for j in range(n):
      cur = d[i][j]
      d[i][j] = min(d[i][j],d[i][k]+d[k][j])
      if cur != d[i][j]:
        flag = False
        break
if not flag:
  print(-1)
else:
  ans = 0
  for i in range(n):
    for k in range(n):
      for j in range(n):
        if i != k and k != j:
          if d[i][j] == d[i][k]+d[k][j]:
            ans += d[i][j]
  t = 0
  for i in range(n):
    t += sum(d[i])
  print((t-ans)//2)

Submission status: Wrong Answer

Solution code:
n = int(input())
d = [[10**14]*n for i in range(n)]
L = []
dist = []
for i in range(n):
    d[i][i] = 0
for i in range(n):
    L = list(map(int,input().split()))
    dist.append(L)
    for j in range(n):
        d[i][j] = L[j]
        d[j][i] = L[j]
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])
flag = True
for i in range(n):
  for j in range(n):
    if d[i][j] < dist[i][j]:
      flag = False
      break
if not flag:
  print(-1)
else:
  ans = 0
  for i in range(n):
    for k in range(n):
      for j in range(n):
        if i != k and k != j:
          if d[i][j] == d[i][k]+d[k][j]:
            ans += d[i][j]
  t = 0
  for i in range(n):
    t += sum(d[i])
  print((t-ans)//2)

Submission status: Wrong Answer

Solution code:
from scipy.sparse.csgraph import floyd_warshall
n = int(input())
d = [[10**14]*n for i in range(n)]
L = []
dist = []
for i in range(n):
    d[i][i] = 0
for i in range(n):
    L = list(map(int,input().split()))
    dist.append(L)
    for j in range(n):
        d[i][j] = L[j]
        d[j][i] = L[j]
d = floyd_warshall(d)
flag = True
for i in range(n):
  for j in range(n):
    if d[i][j] < dist[i][j]:
      flag = False
      break
if not flag:
  print(-1)
else:
  print(82)

Submission status: Wrong Answer

Solution code:
N, = map(int, input().split())
X = []
for _ in range(N):
    X.append(list(map(int, input().split())))
Y = []
for i in range(N):
    for j in range(i+1, N):
        Y.append((i, j, X[i][j]))
#Y.sort(key=lambda x:x[2])
r = 0
for i, j, x in Y:
    mn = 10**18
    for k in range(N):
        if k == i or k == j:
            continue
        mn = min(mn, X[i][k] + X[j][k])
    if mn < x:
        break
    if mn > x:
        r += x
print(r)

Submission status: Wrong Answer

Solution code:

def solve():
  n  = int(input())
  a = []
  for i in range(n):
    tp = list(int(i) for i in input().split())
    a.append(tp)
  a2 = []
  #warshall
  for k in range(n):
    for i in range(n):
      for j in range(n):
        if not k in [i,j]:
         if a[i][j] > a[i][k] + a[k][j]:
          #距離短縮可能
           print(i,j,k)
           print(-1)
           exit()
         elif a[i][j] ==  a[i][k] + a[k][j]:
          a2.append((i,j))
  for i,j in a2:
    a[i][j] = 0
  ans = 0
  for i in range(n):
    for j in range(n):
      if i < j:
        ans += a[i][j]
  print(ans)
solve()

Submission status: Wrong Answer

Solution code:
import collections
N = int(input())
A = [[int(_) for _ in input().split()] for _ in range(N)]
B = [[b for b in a] for a in A]
d_ij = collections.defaultdict(set)
for i in range(N - 1):
    for j in range(i + 1, N):
        d_ij[A[i][j]].add((i, j))
connected = collections.defaultdict(set)
ans = 0
for k in sorted(d_ij.keys()):
    for i, j in d_ij[k]:
        if i not in connected[j]:
            for p in connected[j]:
                if i in connected[p]:
                    continue
                elif A[p][i] > A[p][j] + A[j][i]:
                    print(-1)
                    exit()
                elif A[p][i] == A[p][j] + A[j][i]:
                    B[p][i] = B[i][p] = 0
                    connected[p].add(i)
                    connected[i].add(p)
            for q in connected[i]:
                if j in connected[q]:
                    continue
                elif A[q][j] > A[q][i] + A[i][j]:
                    print(-1)
                    exit()
                elif A[q][j] == A[q][i] + A[i][j]:
                    B[q][j] = B[j][q] = 0
                    connected[q].add(j)
                    connected[j].add(q)
            connected[i].add(j)
            connected[j].add(i)
print(sum(sum(_) for _ in B) // 2)

Submission status: Wrong Answer

Solution code:
import itertools
N = int(input())
A = [[int(_) for _ in input().split()] for _ in range(N)]
ans = sum(sum(a) for a in A)
seen = set()
for i, j, k in itertools.product(range(N), repeat=3):
    if A[i][j] > A[i][k] + A[j][k]:
        print(-1)
        exit()
    elif k == i or i == j or j == k:
        continue
    elif A[i][j] == A[i][k] + A[j][k]:
        ans -= A[i][j]
print(ans // 2)

Submission status: Wrong Answer

Solution code:
import itertools
N = int(input())
A = [[int(_) for _ in input().split()] for _ in range(N)]
ans = sum(sum(a) for a in A)
seen = set()
for k, i, j in itertools.product(range(N), repeat=3):
    if A[i][j] > A[i][k] + A[j][k]:
        print(-1)
        exit()
    elif (i * 1000 + j) in seen or k == i or i == j or j == k:
        continue
    elif A[i][j] == A[i][k] + A[j][k]:
        ans -= A[i][j]
        seen.add(i * 1000 + k)
        seen.add(k * 1000 + i)
        seen.add(j * 1000 + k)
        seen.add(k * 1000 + j)
    seen.add(i * 1000 + j)
    seen.add(j * 1000 + i)
print(ans // 2)

Submission status: Wrong Answer

Solution code:
import itertools
N = int(input())
A = [[int(_) for _ in input().split()] for _ in range(N)]
ans = sum(sum(a) for a in A)
seen = set()
for k, i, j in itertools.product(range(N), repeat=3):
    if (i, j) in seen or k == i or i == j or j == k:
        continue
    elif A[i][j] > A[i][k] + A[j][k]:
        print(-1)
        exit()
    elif A[i][j] == A[i][k] + A[j][k]:
        ans -= A[i][j]
        seen.add((i, k))
        seen.add((k, i))
        seen.add((j, k))
        seen.add((k, j))
    seen.add((i, j))
    seen.add((j, i))
print(ans // 2)

Submission status: Wrong Answer

Solution code:
import itertools
N = int(input())
A = [[int(_) for _ in input().split()] for _ in range(N)]
ans = sum(sum(a) for a in A)
for k, i, j in itertools.product(range(N), repeat=3):
    if k == i or i == j or j == k:
        continue
    elif A[i][j] > A[i][k] + A[j][k]:
        print(-1)
        exit()
    elif A[i][j] == A[i][k] + A[j][k]:
        ans -= A[i][j]
print(ans // 2)

Submission status: Wrong Answer

Solution code:
import itertools
N = int(input())
A = [[int(_) for _ in input().split()] for _ in range(N)]
ans = sum(sum(a) for a in A)
for k, i, j in itertools.product(range(N), repeat=3):
    if k == i or i == j or j == k:
        continue
    elif A[i][j] > A[i][k] + A[j][k]:
        print(-1)
        exit()
    elif A[i][j] == A[i][k] + A[j][k]:
        ans -= A[k][i]
print(ans // 2)

Submission status: Wrong Answer

Solution code:
import itertools
N = int(input())
A = [[int(_) for _ in input().split()] for _ in range(N)]
ans = sum(sum(a) for a in A)
for k, i, j in itertools.product(range(N), repeat=3):
    if k == i or i == j or j == k:
        continue
    elif A[k][i] > A[i][j] + A[j][k]:
        print(-1)
        exit()
    elif A[k][i] == A[i][j] + A[j][k]:
        ans -= A[k][i]
print(ans // 2)

Submission status: Wrong Answer

Solution code:
import collections
N = int(input())
A = [[int(_) for _ in input().split()] for _ in range(N)]
B = [[b for b in a] for a in A]
d_ij = collections.defaultdict(set)
for i in range(N - 1):
    for j in range(i + 1, N):
        d_ij[A[i][j]].add((i, j))
connected = collections.defaultdict(set)
ans = 0
for k in sorted(d_ij.keys()):
    for i, j in d_ij[k]:
        if i not in connected[j]:
            for p in connected[j]:
                if A[p][i] > A[p][j] + A[j][i]:
                    print(-1)
                    exit()
                elif A[p][i] == A[p][j] + A[j][i]:
                    B[p][i] = B[i][p] = 0
                    connected[p].add(i)
                    connected[i].add(p)
            for q in connected[i]:
                if A[q][j] > A[q][i] + A[i][j]:
                    print(-1)
                    exit()
                elif A[q][j] == A[q][i] + A[i][j]:
                    B[q][j] = B[j][q] = 0
                    connected[q].add(j)
                    connected[j].add(q)
            connected[i].add(j)
            connected[j].add(i)
print(sum(sum(_) for _ in B) // 2)

Submission status: Wrong Answer

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

use = [[0]*N for _ in range(N)]

for k in range(N):
    for i in range(N):
        for j in range(N):
            if mat[i][k] > mat[i][k]+mat[k][j]:
                print("-1")
                exit()
            if mat[i][j] == mat[i][k]+mat[k][j] and i != k and k != j:
                use[i][j] = 1
ans = 0
for i in range(N):
    for j in range(N):
        if use[i][j] == 0:
            ans += mat[i][j]
print(ans//2)

Submission status: Wrong Answer

Solution code:
N=int(input())
import sys
input=sys.stdin.readline
A=[[int(j) for j in input().split()] for _ in range(N)]

ans=0
bridge=[[False]*(N) for i in range(N)]
for k in range(N):
  for i in range(N):
    for j in range(N):
      if i>=j: continue
      if A[i][j]>A[i][k]+A[k][j]:
        print(-1)
        exit(0)
      elif A[i][j]<A[i][k]+A[k][j]:
        if not bridge[i][j]:
          ans+=A[i][j]
          bridge[i][j]=True
          bridge[j][i]=True
      else: 
        if not bridge[i][k]:
          ans+=A[i][k]
          bridge[i][k]=True
          bridge[k][i]=True
        if not bridge[k][j]:
          ans+=A[k][j]
          bridge[k][j]=True
          bridge[j][k]=True
          
print(ans)

Submission status: Wrong Answer

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

ans=0
for k in range(N):
  for i in range(N):
    for j in range(N):
      if i>=j: continue
      if A[i][j]>A[i][k]+A[k][j]:
        print(-1)
        exit(0)
      elif A[i][j]<A[i][k]+A[k][j]:
        ans+=A[i][j]
print(ans)

Submission status: Wrong Answer

Solution code:
def warshall_floyd(d):
    #d[i][j]: 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])
 
n = int(input())
a = [[] for i in range(n)]
war = [[] for i in range(n)]
for i in range(n):
    a[i] = list(map(int,input().split()))
    war[i] = a[i]
for i in range(n):
    if a[i][i] != 0:
        print(-1)
        exit()
 
warshall_floyd(war)
 
res = 0
for i in range(n):
    for j in range(n):
        if war[i][j] < a[i][j]:
            print(-1)
            exit()
        elif war[i][j] == a[i][j]:
            judge = 1
            for h in range(n):
                if h != i and h != j and war[i][h]+war[h][j] == war[i][j]:
                    judge = -1
            if judge == 1:
                res += war[i][j]
print(res//2)

Submission status: Wrong Answer

Solution code:
N=int(input())
inf=float("inf")
Graph=[[inf]*N for i in range(N)]
ans=0
for i in range(N):
  a=[int(m) for m in input().split()]
  for j in range(i+1):
    Graph[i][j]=a[j]
    Graph[j][i]=a[j]
    ans+=a[j]

for k in range(N):
  for i in range(N):
    for j in range(i+1):
      if Graph[i][j]>Graph[i][k]+Graph[k][j]:
        print(-1)
        exit()
      elif Graph[i][j]==Graph[i][k]+Graph[k][j] and i!=k and j!=k:
        ans-=Graph[i][j]

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
N=int(input())
len = [list(map(int,input().split())) for t in range (N)]
a=0
n=0
while n < N:
    m=n+1
    while m < N:
        for i in range (N-1):
            if i!=n and i!=m:
                if len[n][i]+len[i][m]==len[n][m]:
                    a+=len[n][m] 
                    break
                elif len[n][i]+len[i][m]<len[n][m]:  
                    print(-1)
                    sys.exit()
            i+=1
        m+=1
    n+=1

sum=0
n=0
m=0
while n < N:
    m=n+1
    while m < N:
        sum+=len[n][m]
        m+=1
    n+=1

print(sum-a)

Submission status: Wrong Answer

Solution code:
import sys
N=int(input())
len = [list(map(int,input().split())) for t in range (N)]
a=0
n=0
while n < N:
    m=n+1
    while m < N:
        for i in range (N-1):
            if i!=n and i!=m:
                if len[n][i]+len[i][m]==len[n][m]:
                    a+=len[n][m] 
                    break
                elif len[n][i]+len[i][m]<len[n][m]:  
                    print(-1)
                    sys.exit()
            i+=1
        m+=1
    n+=1

sum=0
n=0
while n < N:
    m=n+1
    while m < N:
        sum+=len[n][m]
        m+=1
    n+=1

print(sum-a)

Submission status: Wrong Answer

Solution code:
import sys
N=int(input())
len = [list(map(int,input().split())) for t in range (N)]
a=0
n=0
while n < N:
    m=n+1
    while m < N:
        for i in range (N-1):
            if i!=n and i!=m:
                if len[n][i]+len[i][m]==len[n][m]:
                    a+=len[n][m] 
                    break
                elif len[n][i]+len[i][m]<len[n][m]:  
                    sys.exit()
            i+=1
        m+=1
    n+=1

sum=0
n=0
while n < N:
    m=n+1
    while m < N:
        sum+=len[n][m]
        m+=1
    n+=1

print(sum-a)

Submission status: Wrong Answer

Solution code:
import sys
N=int(input())
A=[[int(i) for i in input().split()] for i in range(N)]
L=[]
for i in range(N):
    for j in range(N):
        if i==j:
            continue
        for k in range(N):
            if i==k or j==k:
                continue
            a=A[i][j]
            b=A[i][k]
            c=A[k][j]
            if a+b<c:
                print(-1)
                sys.exit()
            if a+b==c:
                L.append(c)
sa=0
for i in range(N):
    for j in range(i,N):
        sa+=A[i][j]
print(sa-sum(L)//2)

Submission status: Wrong Answer

Solution code:
import sys
import copy

N = int(input())
table = []
for i in range(N):
    A = [int(j) for j in input().split()]
    table.append(A)
tas = copy.deepcopy(table)
for k in range(N):
    for i in range(N):
        for j in range(N):
            tas[j][i] = min(tas[j][i], tas[j][k] + tas[k][i])

for y in range(N):
    for x in range(i + 1, N):
        if A[y][x] != tas[y][x]:
            print(-1)
            sys.exit()
ans = 0
for i in range(N):
    for j in range(i + 1, N):
        flag = True
        for k in range(N):
            if i == k or j == k:
                continue
            if table[j][i] >= table[j][k] + table[k][i]:
                flag = False
        if flag:
            ans += table[j][i]
print(ans)

Submission status: Wrong Answer

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

ans = 0
muri = 0
for i in range(n - 1):
	for j in range(i + 1, n):
		max_length = 0
		for k in range(n):
			if k == i or k == j:
				continue
			if a[i][k] + a[k][j] == a[i][j]:
				max_length = float("inf")
				break
			if a[i][k] + a[k][j] > max_length:
				max_length = a[i][k] + a[k][j]
		if max_length < a[i][j]:
			muri += 1
		elif max_length < 10 ** 10:
			ans += a[i][j]

if n == 2:
	print(a[0][1])
elif muri != 0:
	print(-1)
else:
	print(ans)

Submission status: Wrong Answer

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

ans = 0
muri = 0
for i in range(n):
	for j in range(i + 1, n):
		max_length = 0
		for k in range(n):
			if k == i or k == j:
				continue
			if a[i][k] + a[k][j] == a[i][j]:
				max_length = float("inf")
				break
			if a[i][k] + a[k][j] > max_length:
				max_length = a[i][k] + a[k][j]
		if max_length < a[i][j]:
			muri += 1
		elif max_length < 10 ** 10:
			ans += a[i][j]

if n == 2:
	print(a[0][1])
elif muri != 0:
	print(-1)
else:
	print(ans)

Submission status: Wrong Answer

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

ans = 0
muri = 0
for i in range(n):
	for j in range(i + 1, n):
		max_length = 0
		for k in range(n):
			if k == i or k == j:
				continue
			if a[i][k] + a[k][j] == a[i][j]:
				max_length = float("inf")
				break
			if a[i][k] + a[k][j] > max_length:
				max_length = a[i][k] + a[k][j]
		if max_length < a[i][j]:
			muri += 1
		elif max_length < 10 ** 10:
			ans += a[i][j]

if muri != 0:
	print(-1)
else:
	print(ans)

Submission status: Wrong Answer

Solution code:
def arc84_d(n,A):
    road = 0
    
    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]:
                    return -1
                elif A[i][j] == A[i][k] + A[k][j]:
                    if k not in {i,j} and i < j:
                        road += A[i][j]
    return road

n = int(input())
A = [list(map(int, input().split())) for _ in range(n)]
road = arc84_d(n,A)
print(road)

Submission status: Wrong Answer

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

    ans = sum([sum(_A) for _A in A])
    for k in range(n) :
        for i in range(n) :
            for j in range(n) :
                if i == k :
                    break
                elif j == k :
                    continue
                
                d = A[i][k] + A[k][j]
                if d == A[i][j] :
                    ans -= d
                elif d < A[i][j] :
                    print(-1)
                    exit()

    print(ans//2)

main()

Submission status: Wrong Answer

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

    ans = 0
    for k in range(n) :
        for i in range(n) :
            for j in range(n) :
                if i == k :
                    break
                elif j == k :
                    continue
                
                d = A[i][k] + A[k][j]
                if d == A[i][j] :
                    ans += d
                elif d < A[i][j] :
                    print(-1)
                    exit()

    print(ans//2)

main()

Submission status: Wrong Answer

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

    ans = 0
    for i in range(n) :
        for j in range(i+1, n) :
            for k in range(n) :
                if i == k or j == k:
                    continue
                
                d = A[i][k] + A[k][j]
                if d == A[i][j] :
                    ans += d
                elif d < A[i][j] :
                    print(-1)
                    exit()

    print(ans)

main()

Submission status: Wrong Answer

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

ans = 0
for i in range(n) :
    for j in range(i+1, n) :
        for k in range(n) :
            if i == k or j == k:
                continue
            
            d = A[i][k] + A[k][j]
            if d == A[i][j] :
                ans += d
            elif d < A[i][j] :
                print(-1)
                exit()

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(raw_input())
A = [map(int, raw_input().split(' ')) for n in xrange(N)]

answer = 0
for i in xrange(N):
  for j in xrange(i):
    for k in xrange(N):
      if k == i or k == j: continue
      L = A[i][k] + A[k][j]
      if A[i][j] <= L:
        if A[i][j] < L:
          print -1
          exit()
        break
    else:
      answer += A[i][j]

print answer

Submission status: Wrong Answer

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

    total = sum([sum(a[i]) for i in range(n)])
    for k in range(n):
        for i in range(n):
            if k==i:
                continue
            for j in range(n):
                if i == j or k ==j:
                    continue
                if a[i][j] > a[i][k] + a[k][j]:
                    print(-1)
                    exit()
                if a[i][j] == a[i][k] + a[k][j]:
                    total -= a[i][j]
    print(total//2)
    

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

    dist = [[a[i][j] for j in range(n)] for i in range(n)]
    total = sum([sum(a[i]) for i in range(n)])
    for k in range(n):
        for i in range(n):
            if k==i:
                continue
            for j in range(n):
                if i == j or k ==j:
                    continue
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    print(-1)
                    exit()
                if dist[i][j] == dist[i][k] + dist[k][j]:
                    total -= dist[i][j]
    for i in range(n):
        for j in range(n):
            if dist[i][j] != a[i][j]:
                print(-1)
                exit()
    print(total//2)
    

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import itertools
import heapq


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


def read():
    N = II()
    matrix = [ILI() for __ in range(N)]
    return N, matrix


def check_first(matrix):
    t_matrix = list(map(list, zip(*matrix)))
    for i, (row, t_row) in enumerate(zip(matrix, t_matrix)):
        if row[i] != 0:
            return False
        for ele, t_ele in zip(row, t_row):
            if ele != t_ele:
                return False
    return True


def solve(N, matrix):
    if check_first(matrix) is False:
        return -1
    ano_matrix = [[10 ** 9] * N for __ in range(N)]
    for a, b, c in itertools.product(range(N), repeat=3):
        new_length = matrix[a][b] + matrix[b][c]
        ano_matrix[a][c] = min(ano_matrix[a][c], new_length)
    for row, ano_row in zip(matrix, ano_matrix):
        for ele, ano_ele in zip(row, ano_row):
            if ele != ano_ele:
                return -1

    # Prim 法で最小全域木を求める
    ans = 0
    s_nodes = set()
    s_nodes.add(0)
    edges = []
    for i in range(1, N):
        edges.append((matrix[0][i], i))
    heapq.heapify(edges)
    while len(s_nodes) < N:
        while True:
            l, to = heapq.heappop(edges)
            if to in s_nodes:
                continue
            else:
                ans += l
                s_nodes.add(to)
                for i in range(N):
                    if i in s_nodes:
                        continue
                    else:
                        heapq.heappush(edges, (matrix[to][i], i))
                break
    return ans


def main():
    params = read()
    print(solve(*params))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

exist = True
ans = 0
ls = []
for i in range(n - 1):
    for j in range(i + 1, n):
        ls.append((a[i][j], i, j))
ls.sort()
ds = [[1000000001 for _ in range(n)] for _ in range(n)]
for u in range(n):
    ds[u][u] = 0
for (d, u, v) in ls:
    use = True
    for w in range(n):
        if u == w or v == w:
            continue
        if a[u][v] == ds[u][w] + ds[w][v]:
            use = False
        elif ds[u][w] + ds[w][v] < a[u][v]:
            exist = False
    if use:
        ds[u][v] = d
        ds[v][u] = d
        for w in range(n):
            ds[u][w] = min(ds[u][w], d + ds[v][w])
            ds[w][u] = ds[u][w]
            ds[v][w] = min(ds[v][w], d + ds[u][w])
            ds[w][v] = ds[v][w]
        ans += d
if not exist:
    print(-1)
else:
    print(ans)