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 math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N = I()
    G = []
    for _ in range(N):
        a = LI()
        G.append(a)
    dp = copy.deepcopy(G)
    for i in range(N):
        for j in range(N):
            for k in range(N):
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])

    if dp != G:
        print(-1)
        return

    for i in range(N):
        for j in range(N):
            for k in range(N):
                if i == j or j == k or k == j:
                    continue
                if dp[i][k] == 0 or dp[i][j] == 0 or dp[j][k] == 0:
                    continue
                if dp[i][j] == dp[i][k] + dp[k][j]:
                    dp[i][j] = 0
                    dp[j][i] = 0
    cnt = 0
    for i in range(N):
        for j in range(N):
            cnt += dp[i][j]
    print(cnt // 2)
main()

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N = I()
    G = []
    for _ in range(N):
        a = LI()
        G.append(a)
    dp = copy.deepcopy(G)
    for i in range(N):
        for j in range(N):
            for k in range(N):
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])

    if dp != G:
        print(-1)
        return

    for i in range(N):
        for j in range(N):
            for k in range(N):
                if i == j:
                    continue
                if j == k:
                    continue
                if i == k:
                    continue
                if dp[i][k] == 0 or dp[i][j] == 0 or dp[j][k] == 0:
                    continue
                if dp[i][j] == dp[i][k] + dp[k][j]:
                    dp[i][j] = 0
                    dp[j][i] = 0
    cnt = 0
    for i in range(N):
        for j in range(N):
            cnt += dp[i][j]
    print(cnt // 2)
main()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
flag = [[False]*N for _ in range(N)]
ans = 0

for i in range(N):
    for j in range(i+1, N):
        for k in range(j+1, N):
            l = [A[i][j], A[j][k], A[i][k]]
            l.sort()
            
            if l[0]+l[1]<l[2]:
                print(-1)
                exit()
            
            if not flag[i][j]:
                ans += A[i][j]
                flag[i][j] = True
            
            if not flag[j][k]:
                ans += A[j][k]
                flag[j][k] = True
            
            if not flag[i][k]:
                ans += A[i][k]
                flag[i][k] = True
            
            if l[0]+l[1]==l[2]:
                ans -= l[2]
    
print(ans)

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(N):
        ans += A[i][j]

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

print(ans//2)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [tuple(map(int, input().split())) for _ in range(N)]
seen = [[False] * N for _ in range(N)]

ans = 0

for i in range(N - 1):
    for j in range(i + 1, N):
        # iからjに行くルートを考える
        path_IJ = A[i][j]
        use = [(i, j)]
        for k in range(N):
            if i == k or j == k:
                continue
            path_IKJ = A[i][k] + A[k][j]

            if path_IJ > path_IKJ:
                print(-1)
                exit()
            elif path_IJ == path_IKJ:
                use = [(i, k), (k, j)]
            else:
                pass

        for x, y in use:
            x, y = min(x, y), max(x, y)
            if not seen[x][y]:
                ans += A[x][y]
                seen[x][y] = True
print(ans)

Submission status: Wrong Answer

Solution code:
import copy


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])
    return d


n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
b = copy.deepcopy(a)
b = warshall_floyd(b)
ans = 0
for i in range(n):
    for j in range(n):
        if a[i][j] != b[i][j]:
            print(-1)
            exit()
        ans = max(ans, b[i][j])
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env pypy3
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    inf=10*20
    N=I()
    A=[[]for _ in range(N)]
    ans=0
    for i in range(N):
        A[i]=LI()
        ans+=sum(A[i])
        
    


        
    def warshall_floyd(d,ans):
        #d[i][j]: iからjへの最短距離
        for k in range(N):
            for i in range(N):
                if k==i:
                    continue
                for j in range(N):
                    if j==i or j==k:
                        continue
                    dd=d[i][k] + d[k][j]
                    #d[i][j] = min(d[i][j],d[i][k] + d[k][j])
                    
                    if dd==d[i][j]:
                        ans-=d[i][j]
                    elif dd<d[i][j]:
                        return -2
        return ans
    
    ans=warshall_floyd(A,ans)
        
    print(ans//2)
        
    

main()

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.read

import numpy as np
from scipy.sparse.csgraph import floyd_warshall

n = int(input())
A = np.array(read().split(), dtype=np.int64).reshape(n, n)
F = floyd_warshall(A)
w = np.arange(n)
ans = 0
for u in range(n):
  for v in range(n):
    if np.count_nonzero(F[u, v] == F[u, w] + F[w, v]) == 2:
      ans += F[u, v]
ans //= 2
print(int(ans))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = []
ans = 0
for i in range(n):
    k = list(map(int, input().split()))
    ans += sum(k)
    a.append(k)
for i in range(n):
    for j in range(n):
        for k in range(n):
            if a[j][i] + a[i][k] < a[j][k]:
                print(-1)
                exit()
            elif a[j][i] + a[i][k] == a[j][k] and j != i and i != k:
                ans -= a[j][k]
print(ans//2)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = []
ans = 0
for i in range(n):
    k = list(map(int, input().split()))
    ans += sum(k)
    a.append(k)
print(ans)
for i in range(n):
    for j in range(n):
        for k in range(n):
            if a[j][i] + a[i][k] < a[j][k]:
                print(-1)
                exit()
            elif a[j][i] + a[i][k] == a[j][k] and j != i and i != k:
                ans -= a[j][k]
print(ans//2)

Submission status: Wrong Answer

Solution code:
from scipy.sparse.csgraph import floyd_warshall
N = int(input())
dic = [0]*N
for i in range(N):
  dic[i] = [int(c) for c in input().split()]

d = floyd_warshall(dic)
ans = 0
for i in range(N-1):
  for j in range(i+1,N):
    if d[i][j] < dic[i][j]:
      ans = -1
      import sys
      sys.exit()
    elif dic[i][j] == d[i][j]:
      flag = False
      for k in range(N):
        if k==i or k==j:
          continue
        if d[i][j] == d[i][k]+d[k][j]:
          flag = True
          break
      if flag:
        continue
    ans += dic[i][j]

print(ans)

Submission status: Wrong Answer

Solution code:
from scipy.sparse.csgraph import floyd_warshall
N = int(input())
dic = [0]*N
for i in range(N):
  dic[i] = [int(c) for c in input().split()]

d = floyd_warshall(dic)
ans = 0
for i in range(N-1):
  for j in range(i+1,N):
    if d[i][j] < dic[i][j]:
      print(-1)
      break
    elif dic[i][j] == d[i][j]:
      flag = False
      for k in range(N):
        if k==i or k==j:
          continue
        if d[i][j] == d[i][k]+d[k][j]:
          flag = True
          break
      if flag:
        continue
    ans += dic[i][j]

print(ans)

Submission status: Wrong Answer

Solution code:
from scipy.sparse.csgraph import floyd_warshall
N = int(input())
dic = [0]*N
for i in range(N):
  dic[i] = [int(c) for c in input().split()]
  
d = floyd_warshall(dic)
ans = 0
for i in range(N-1):
  for j in range(i+1,N):
    if d[i][j] > dic[i][j]:
      print(-1)
      break
    elif dic[i][j] == d[i][j]:
      flag = False
      for k in range(N):
        if k==i or k==j:
          continue
        if d[i][j] == d[i][k]+d[k][j]:
          flag = True
          break
      if flag:
        continue
    ans += dic[i][j]

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N = int(input())
cost = [[0]*N for i in range(N)]
dist = [[0]*N for i in range(N)]
log = defaultdict(int)
for i in range(N):
  inf = [int(c) for c in input().split()]
  for j in range(N):
    cost[i][j] = inf[j]
for i in range(N):
  for j in range(i+1,N):
    m = float('inf')
    flag = False
    for k in range(N):
      if cost[i][j]>=cost[i][k]+cost[k][j]:
        m = cost[i][k]+cost[k][j]
        if k != i and k!= j:
          log[(min(i,j),max(i,j))] = 1
    dist[i][j] = m
    dist[j][i] = m
ans = 0
for i in range(N):
  for j in range(i+1,N):
    flag = False
    if dist[i][j]<cost[i][j]:
      print(-1)
      flag = True
      break
    elif log[(i,j)]==0:
      ans += cost[i][j]
  if flag:
    break
else:
  print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N = int(input())
cost = [[0]*N for i in range(N)]
for i in range(N):
  inf = [int(c) for c in input().split()]
  for j in range(N):
    cost[i][j] = inf[j]
for i in range(N):
  for j in range(i+1,N):
    m = float('inf')
    flag = False
    for k in range(N):
      if m>cost[i][k]+cost[j][k]:
        m = cost[i][k]+cost[k][j]
    if m!= cost[i][j]:
      print(-1)
      flag = True
      break
  if flag:
    break
else:
  ls = []
  for i in range(N):
    for j in range(i+1,N):
      ls += [(cost[i][j],i,j)]
  ls.sort(key=lambda x:x[0])
  dic = defaultdict(list)
  dist = defaultdict(int)
  ans = 0
  for i in range(len(ls)):
    d, a, b = ls[i]
    if dist[(min(a,b),max(a,b))] > d:
      for e, m in dic[a]:
        dist[(min(e,b), max(e,b))] = min(m+d,dist[(min(e,b), max(e,b))]) if dist[(min(e,b), max(e,b))]!=0 else m+d
      for e, m in dic[b]:
        dist[(min(e,a), max(e,a))] = min(m+d,dist[(min(e,a), max(e,a))]) if dist[(min(e,a), max(e,a))]!=0 else m+d
      dic[a] += [(b,d)]
      dic[b] += [(a,d)]
      dist[(min(a,b), max(a,b))] = d
      ans += d
  print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N = int(input())
cost = [[0]*N for i in range(N)]
for i in range(N):
  inf = [int(c) for c in input().split()]
  for j in range(N):
    cost[i][j] = inf[j]
for i in range(N):
  for j in range(i+1,N):
    m = float('inf')
    flag = False
    for k in range(N):
      if m>cost[i][k]+cost[j][k]:
        m = cost[i][k]+cost[k][j]
    if m!= cost[i][j]:
      print(-1)
      flag = True
      break
  if flag:
    break
else:
  ls = []
  for i in range(N):
    for j in range(i+1,N):
      ls += [(cost[i][j],i,j)]
  ls.sort(key=lambda x:x[0])
  used = [False]*N
  dic = defaultdict(list)
  dist = defaultdict(int)
  ans = 0
  for i in range(len(ls)):
    d, a, b = ls[i]
    if dist[(min(a,b),max(a,b))] != d:
      for e, m in dic[a]:
        dist[(min(e,b), max(e,b))] = min(m+d,dist[(min(e,b), max(e,b))]) if dist[(min(e,b), max(e,b))]!=0 else m+d
      for e, m in dic[b]:
        dist[(min(e,a), max(e,a))] = min(m+d,dist[(min(e,a), max(e,a))]) if dist[(min(e,a), max(e,a))]!=0 else m+d
      dic[a] += [(b,d)]
      dic[b] += [(a,d)]
      dist[(min(a,b), max(a,b))] = d
      ans += d
  print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import permutations
import sys
input = sys.stdin.readline
n = int(input())
dist = [list(map(int,input().split())) for i in range(n)]

for i,j,k in permutations(range(n),3):
  if dist[i][k]+dist[k][j] == dist[i][j] and dist[i][k] != 0 and dist[k][j] != 0:
    dist[i][j] = 0
  elif dist[i][k]+dist[k][j] < dist[i][j] and dist[i][k] != 0 and dist[k][j] != 0:
    print(-1)
    exit()
ans = 0
for arr in dist:
  ans += sum(arr)
ans //= 2
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
dist = [list(map(int,input().split())) for i in range(n)]

for i in range(n):
  for j in range(n):
    for k in range(n):
      if i != j and j != k and k != i:
        if dist[i][k]+dist[k][j] == dist[i][j] and dist[i][k] != 0 and dist[k][j] != 0:
          dist[i][j] = 0
        elif dist[i][k]+dist[k][j] < dist[i][j] and dist[i][k] != 0 and dist[k][j] != 0:
           print(-1)
           exit()
ans = 0
for arr in dist:
  ans += sum(arr)
ans //= 2
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
dist = [list(map(int,input().split())) for i in range(n)]
ans = 0
for arr in dist:
  ans += sum(arr)
ans //= 2
for i in range(n):
  for j in range(i+1,n):
    for k in range(n):
      if j != k and k != i:
        if dist[i][k]+dist[k][j] == dist[i][j]:
          ans -= dist[i][j]
        elif dist[i][k]+dist[k][j] < dist[i][j]:
          print(-1)
          exit()
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
dist = [list(map(int,input().split())) for i in range(n)]
ans = 0
for arr in dist:
  ans += sum(arr)
ans //= 2
for i in range(n):
  for j in range(i,n):
    for k in range(n):
      if j != k and k != i:
        if dist[i][k]+dist[k][j] == dist[i][j]:
          ans -= dist[i][j]
        elif dist[i][k]+dist[k][j] < dist[i][j]:
          print(-1)
          exit()
print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop

def prim_heap(edges, n):
    visited = [False] * n
    heap = []
    start = 0
    for e in edges[start]:
        heappush(heap, e)
    visited[start] = True

    res = 0
    while heap:
        cost, v = heappop(heap)
        if visited[v]:
            continue
        visited[v] = True
        res += cost
        for c,u in edges[v]:
            if visited[u]:
                continue
            heappush(heap, (c,u))
    # print(visited)
    return res if sum(visited) == n else -1

def warshall(d, n):
    e = copy.deepcopy(d)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                # print(d[i][k], d[k][j], d[i][j])
                if i == k or k == j:
                    continue
                if d[i][k] + d[k][j] < d[i][j]:
                    e[i][k] = 0
                    e[k][j] = 0
                    e[k][i] = 0
                    e[j][k] = 0
                if d[i][k] + d[k][j] == d[i][j]:
                    # print(d[i][k], d[k][j], d[i][j], i,j,k)
                    e[i][j] = 0
                    e[j][i] = 0
    return e
    
import copy
n = int(input())
edges = []

graph = [list(map(int, input().split())) for i in range(n)]
e = warshall(graph, n)
# print(e)
edge_list = [[] for _ in range(n)]
ans = 0
for i in range(n):
    for j in range(n):
        if e[i][j] > 0:
            edge_list[i].append((e[i][j], j))
        if j > i and e[i][j]:
            ans += e[i][j]

print(ans if prim_heap(edge_list, n) != -1 else -1)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
cnt = 0
for k in range(n):
  for i in range(n-1):
    for j in range(i+1,n):
      if a[i][j] > a[i][k] + a[k][j]:
        print(-1); exit(0)

for i in range(n-1):
  for j in range(i+1,n):
    for k in range(n):
      if k == i or k == j: continue
      elif a[i][j] == a[i][k] + a[k][j]:
        cnt += a[i][j]
tot = sum(sum(x) for x in a)//2
print(tot-cnt)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
cnt = 0
for i in range(n-1):
  for j in range(i+1,n):
    for k in range(n):
      if k == i or k == 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]:
        cnt += a[i][j]
tot = sum(sum(x) for x in a)//2
print(tot-cnt)

Submission status: Wrong Answer

Solution code:
n=int(input())
import copy

d = [[float("inf") for i in range(n+1)] for _ in range(n+1)]
dd=copy.deepcopy(d)
for i in range(1,n+1):
  dd[i][i]=0
uselist=[]
for i in range(n):
    a=list(map(int,input().split()))
    for j in range(i,n):
        p=a[j]    
        d[i+1][j+1]=p
        d[j+1][i+1]=p
        if i!=j:
        	uselist.append((i+1,j+1,p))
uselist=sorted(uselist,key=lambda x:x[2])


ans=0
for p in range(len(uselist)):
    pick=uselist[p]
    a,b,c=pick[0],pick[1],pick[2]
    dd[a][b]=c
    dd[b][a]=c
    for i in range(1,n+1):
        if dd[i][a]==float("inf"):
            pass
        else:
            dd[i][b]=min(dd[i][a]+dd[a][b],dd[i][b])
    for j in range(1,n+1):
        dd[b][j]=dd[j][b]
    ans+=c

    if dd==d:
        break
    

if dd==d:
    print(ans)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import copy
loss=0
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])
    return d
def warshall_floyd2(d):
    #d[i][j]: iからjへの最短距離
    ans=0
    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 d[i][j]<d[i][k] + d[k][j]:
                    ans+=d[i][j]
    #print(loss)
    return ans

n=int(input())
a=[list(map(int,input().split())) for _ in range(n)]
b=copy.deepcopy(a)
b=warshall_floyd(b)
#print(a)
#print(b)
flg=True
for i in range(n):
    for j in range(n):
        if a[i][j]!=b[i][j]:
            flg=False
            break
    else:
        continue
    break
if flg:
    ans=0
    for i in a:
        ans+=sum(i)
    #print(ans)
    ans=warshall_floyd2(b)
    print(ans//2)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import copy
loss=0
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])
    return d
def warshall_floyd2(d):
    #d[i][j]: iからjへの最短距離
    loss=0
    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 d[i][j]==d[i][k] + d[k][j]:
                    loss+=d[i][j]
    #print(loss)
    return loss

n=int(input())
a=[list(map(int,input().split())) for _ in range(n)]
b=copy.deepcopy(a)
b=warshall_floyd(b)
#print(a)
#print(b)
flg=True
for i in range(n):
    for j in range(n):
        if a[i][j]!=b[i][j]:
            flg=False
            break
    else:
        continue
    break
if flg:
    ans=0
    for i in a:
        ans+=sum(i)
    #print(ans)
    loss=warshall_floyd2(b)
    print(ans//2-loss//2)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
N = int(input())

matrix = [list(map(int, input().split(' '))) for _ in range(N)]
buf = [list(m) for m in matrix]

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

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

diff = 0
for k in range(N):
    for i in range(N):
        for j in range(N):
            if k != i and k != j:
                if matrix[i][k] + matrix[k][j] == matrix[i][j]:
                    diff += matrix[i][j]


ans = (sum([sum(b) for b in matrix]) - diff) // 2
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [list(map(int,input().split())) for i in range(n)]
dp = [[10**10 for _ in range(n)] for _ in range(n)]
for i in range(n):
    dp[i][i] = 0
ans = 0
for k in range(n):
    for i in range(n):
        for j in range(i+1,n):
            if a[i][j]>a[i][k]+a[k][j]:
                print(-1)
                exit()
l = []
for i in range(n):
    for j in range(n):
        l.append((a[i][j],i,j))
l.sort()
for t in l:
    i,j = t[1],t[2]
    if dp[i][j]>a[i][j]:
        ans+=a[i][j]
        dp[i][j] = a[i][j]
        for k in range(n):
            dp[k][j] = min(dp[k][j],dp[k][i]+dp[i][j])
            dp[i][k] = min(dp[i][k],dp[i][j]+dp[j][k])

print(int(ans//2))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [list(map(int,input().split())) for i in range(n)]
dp = [[10**10 for _ in range(n)] for _ in range(n)]
for i in range(n):
    dp[i][i] = 0
ans = 0
for k in range(n):
    for i in range(n):
        for j in range(i+1,n):
            if a[i][j]>a[i][k]+a[k][j]:
                print(-1)
                exit()
l = []
for i in range(n):
    for j in range(n):
        l.append((a[i][j],i,j))
l.sort()
for t in l:
    i,j = t[1],t[2]
    if dp[i][j]>a[i][j]:
        ans+=a[i][j]
        dp[i][j] = a[i][j]
        for k in range(n):
            dp[k][j] = min(dp[k][j],dp[k][i]+dp[i][j])
            dp[i][k] = min(dp[i][k],dp[i][j]+dp[j][k])

print(ans//2)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

read = sys.stdin.read

N, *A = map(int, read().split())
A = np.array(A, np.int64).reshape(N, N)
'''
answer = 0
for i, j in product(range(N), repeat=2):
    if i < j:
        continue
    edge = A[i][j]
    for k in range(N):
        if i == k or j == k:
            continue

        tmp = A[i][k] + A[k][j]
        if tmp < edge:
            print(-1)
            exit()
        elif tmp == edge:
            break
    else:
        answer += edge
'''

useless = 0

for i in range(N):
    grid = A[i] + A[i, None].T
    if np.any(grid < A):
        print(-1)
        exit()
    grid[i] = np.inf
    grid[:, i] = np.inf

    useless += A[A == grid].sum() // 2

print(A.sum() // 2 - useless)

Submission status: Wrong Answer

Solution code:
import sys
from heapq import heappop, heapify, heappush

read = sys.stdin.readline

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

answer = 0
for i in range(N - 1):
    for j in range(i + 1, N):
        edge = A[i][j]
        for k in range(N):
            if i == k or j == k:
                continue

            tmp = A[i][k] + A[k][j]
            if tmp < edge:
                print(i, j, k, tmp, edge)
                print(-1)
                exit()
            elif tmp == edge:
                break
        else:
            answer += edge

print(answer)

Submission status: Wrong Answer

Solution code:
import sys
from heapq import heappop, heapify, heappush

read = sys.stdin.readline

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

edges = []
for i in range(N - 1):
    for j in range(i + 1, N):
        edges.append((A[i][j], (i, j)))

edges.sort()
answer = 0

for edge, (i, j) in edges:
    for k in range(N):
        if i == k or j == k:
            continue

        tmp = A[i][k] + A[k][j]
        if tmp < edge:
            print(i, j, k, tmp, edge)
            print(-1)
            exit()
        elif tmp == edge:
            break
    else:
        answer += edge

print(answer)

Submission status: Wrong Answer

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def warshall_floyd(N: int, graph: list) -> list:
    """ ワーシャルフロイド(頂点数, 隣接行列(0-indexed)) """
    from copy import deepcopy

    res = deepcopy(graph)
    for i in range(N):
        # 始点 = 終点、は予め距離0にしておく
        res[i][i] = 0
    # 全頂点の最短距離
    for k in range(N):
        for i in range(N):
            for j in range(N):
                res[i][j] = min(res[i][j], res[i][k] + res[k][j])
    # 負の閉路(いくらでもコストを減らせてしまう場所)がないかチェックする
    for i in range(N):
        if res[i][i] < 0:
            return []
    return res

def build_grid(H, W, intv, _type, space=True, padding=False):
    # 入力がスペース区切りかどうか
    if space:
        _input = lambda: input().split()
    else:
        _input = lambda: input()
    _list = lambda: list(map(_type, _input()))
    # 余白の有無
    if padding:
        offset = 1
    else:
        offset = 0
    grid = list2d(H+offset*2, W+offset*2, intv)
    for i in range(offset, H+offset):
        row = _list()
        for j in range(offset, W+offset):
            grid[i][j] = row[j-offset]
    return grid

def check1(A, B):
    for i in range(N):
        for j in range(N):
            # 1つでも最短経路が更新されていればNG
            if A[i][j] != B[i][j]:
                return False
    return True

def check2(G):
    res = 0
    for k in range(N):
        for i in range(N):
            for j in range(N):
                # 3頂点が異なってかつ、経由のが近い場合は直接の辺は不要
                if i != j and j != k and k != i \
                        and G[i][k] + G[k][j] == G[i][j]:
                    res += G[i][j]
    return res

N = INT()
G = build_grid(N, N, 0, int)

# 妥当性の確認
wf = warshall_floyd(N, G)
if not check1(G, wf):
    print(-1)
    exit()

# 全体から不要な辺のコストを引く
total = 0
for i in range(N):
    for j in range(N):
        total += wf[i][j]
ans = (total - check2(wf)) // 2
print(ans)

Submission status: Wrong Answer

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

n = int(sys.stdin.readline().rstrip())
A = np.array(sys.stdin.read().split(), dtype=np.float64).reshape(n, n)

def main():
    B = floyd_warshall(csr_matrix(A), directed=False)
    if np.any(B < A):
        return -1
        
    np.fill_diagonal(B, np.inf)
    
    total_length = 0
    for v in range(n-1):
        for u in range(v+1, n):
            detours = B[v] + B[u]
            if np.all(detours > B[v, u]):
                total_length += B[v, u]

    return total_length

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

Submission status: Wrong Answer

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

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


print(ans)

Submission status: Wrong Answer

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

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


print(ans)

Submission status: Wrong Answer

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

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


print(int(ans))

Submission status: Wrong Answer

Solution code:
import copy
ans=0
n=int(input())
l=[list(map(int,input().split())) for _ in [0]*n]
o=copy.deepcopy(l)

for k in range(n):
  for i in range(n):
    for j in range(n):
      if l[i][j]>l[i][k]+l[k][j]:
        print(-1)
        exit()
        if i==j or j==k or k==i :
            continue
        if o[i][j]==o[i][k]+o[k][j]:
            o[i][j]=float("inf")
for i in range(n):
    for j in range(n):
        if o[i][j] != float("inf") :
            ans+=o[i][j]
print(int(ans/2))