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:
def warshall_floyd(V):
    dbl = 0
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if i != j and i != k and j != k and d0[i][k] + d0[k][j] == d0[i][j]:
                    dbl += d0[i][j]                        #; print('d0 i, k, j =', i, k, j)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])  #; print('i,j,k dij =', i,j,k, d[i][j])
                if d[i][j] < d0[i][j]:
                    return False, dbl
    return True, dbl               

import copy                
#INF = float('inf') 
n = int(input())
d = [] ; total = 0
for _ in range(n):
    w = [int(i) for i in input().split()]
    total += sum(w)
    d.append(w)
d0 = copy.deepcopy(d)
#for i in range(n): print(d[i])
#print()

is_ans, dbl = warshall_floyd(n)   

#for i in range(n): print(d[i])
    
if is_ans:
    print((total - dbl)//2)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import sys
N = int(input())
cost_mat = [list(map(int, input().split())) for i in range(N)]
#ans = 0
for start in range(N):
    for end in range(start+1,N):
        direct = cost_mat[start][end]
        for stop in range(N):
            cut = cost_mat[start][stop]+ cost_mat[stop][end]
            if cut < direct:
                #print(cost_mat[start][stop],cost_mat[stop][end])
                #print(start,end,stop)
                print(-1)
                sys.exit()
        #ans += direct
#print(ans)
ans = 0
for new in range(N):
    for to in range(new):
        Need = True
        for stop in range(new):
            if not to == stop and cost_mat[new][to] == cost_mat[new][stop] + cost_mat[stop][to]:
                Need = False
        if Need:
            ans += cost_mat[new][to]
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

with open(0) as f:
    N = int(f.readline())
    A = [list(map(int, line.split())) for line in f.readlines()]

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

Submission status: Wrong Answer

Solution code:
import numpy as np
from scipy.sparse.csgraph import dijkstra
from itertools import count

with open(0) as f:
    N = int(f.readline())
    A = [list(map(int, line.split())) for line in f.readlines()]

A = np.array(A, dtype='int64')
shortcut = dijkstra(A, directed=False)
if not np.array_equal(A, shortcut):
    print(-1)
    exit()

ans = 0
for i in range(N):
    for j in range(i+1, N):
        for k in range(N):
            if A[i, j] < A[i,k] + A[k, j]:
                continue
            if A[i, j] == A[i, k] + A[k, j]:
                break
        else:
            ans += A[i, j]

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict, deque, Counter
from copy import deepcopy
from bisect import bisect, bisect_right, bisect_left
from heapq import heapify, heappop, heappush
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]
    
    
def main():
    N = I()
    A = [LI() for i in range(N)]

    dq = []
    heapify(dq)
    
    for i in range(N):
        for j in range(N):
            heappush(dq, (A[i][j], i, j))
    
    # dist matrix
    dist = [[float('inf') if i != j else 0 for i in range(N)] for j in range(N)]
    
    res = 0
    
    while dq:
        d, x, y = heappop(dq)
        equal = True
        for i in range(N):
            tempD = dist[x][i]+dist[i][y]
            if d > tempD:
                print(-1)
                exit()
            elif d == tempD:
                equal = False
        if equal:
            dist[x][y] = d
            dist[y][x] = d
            res+=d
                
    print(res)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop

def main():
    inf=float("inf")
    n=int(input())
    alst=[list(map(int,input().split())) for _ in range(n)]
    work=[]

    for i in range(n):
        for j in range(i+1,n):
            heappush(work,(alst[i][j],i,j))

    sm=0
    token=0
    road=[[inf]*n for _ in range(n)]

    while 1:
        try : dis,f,t=heappop(work)
        except IndexError : break
        for i in range(n):
            if road[f][i]+road[i][t]>dis:
                continue
            elif road[f][i]+road[i][t]==dis:
                break
            else:
                token=1
                break
        else:
            road[f][t]=dis
            road[t][f]=dis
            sm+=dis
        if token==1:
            sm=-1
            break
    
    print(sm)

main()

Submission status: Wrong Answer

Solution code:
import sys
import copy

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

def w_f(mtrx):
    for k in range(len(mtrx)):
        for i in range(len(mtrx)):
            for j in range(len(mtrx)):
                mtrx[i][j] = min(mtrx[i][j], mtrx[i][k]+mtrx[k][j])
    return mtrx

B = copy.deepcopy(A)
B = w_f(B)
d_sum = 0
for i in range(N):
    for j in range(N):
        d_sum += A[i][j]
        if A[i][j] > B[i][j]:
            print(-1)
            sys.exit()

for k in range(N):
    for i in range(N):
        for j in range(N):
            if k != i and k != j and i != j:
                if B[i][j] == B[i][k]+B[k][j]:
                    d_sum -= B[i][j]
                    
print(d_sum//2)

Submission status: Wrong Answer

Solution code:
import sys
import copy

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

def w_f(mtrx):
    for k in range(len(mtrx)):
        for i in range(len(mtrx)):
            for j in range(len(mtrx)):
                mtrx[i][j] = min(mtrx[i][j], mtrx[i][k]+mtrx[k][j])
    return mtrx

B = copy.deepcopy(A)
B = w_f(B)
d_sum = 0
for i in range(N):
    for j in range(N):
        d_sum += A[i][j]
        if A[i][j] > B[i][j]:
            print(-1)
            sys.exit()

for i in range(N):
    for j in range(N):
        for k in range(N):
            if k != i and k != j and i != j:
                if B[i][j] == B[i][k]+B[k][j]:
                    d_sum -= B[i][j]
                    
print(d_sum//2)

Submission status: Wrong Answer

Solution code:
import sys
import copy

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

def w_f(mtrx):
    for k in range(len(mtrx)):
        for i in range(len(mtrx)):
            for j in range(len(mtrx)):
                mtrx[i][j] = min(mtrx[i][j], mtrx[i][k]+mtrx[k][j])
    return mtrx

B = copy.deepcopy(A)
B = w_f(B)
d_sum = 0
for i in range(N):
    for j in range(N):
        d_sum += A[i][j]
        if A[i][j] != B[i][j]:
            print(-1)
            sys.exit()

e_sum = 0
for i in range(N):
    for j in range(N):
        for k in range(N):
            if k != i and k != j and i != j:
                if B[i][j] == B[i][k]+B[k][j]:
                    e_sum += B[i][j]
                    
print((d_sum-e_sum)//2)

Submission status: Wrong Answer

Solution code:
import sys
N = int(input())
A = [[int(x) for x in input().split()] for _ in range(N)]
dist = [[10e9]*N for _ in range(N)]
for i in range(N): dist[i][i] = 0

for k in range(N):
    for i in range(N):
        for j in range(i+1,N):
            dist[i][j] = min(dist[i][j], A[i][k]+A[k][j])

for i in range(N):
    for j in range(i+1,N):
        if A[i][j] > dist[i][j]:
            print(-1)
            sys.exit()

ans = sum(sum(dist[i]) for i in range(N))
for k in range(N):
    for i in range(N):
        if i == k: continue
        for j in range(i+1,N):
            if j == k: continue
            if dist[i][j] == dist[i][k] + dist[k][j]:
                ans -= dist[i][j]
print(ans)

Submission status: Wrong Answer

Solution code:
import copy

n=int(input())
a=[]
ans=0
for _ in range(n):
  b=list(map(int,input().split()))
  ans+=sum(b)
  a.append(b)
  
c=copy.deepcopy(a)
  
for i in range(n):
  for j in range(n):
    ch=0
    for k in range(n):
      if c[i][j]==c[i][k]+c[k][j] and ch==0 and i!=k and j!=k:
        ans-=c[i][j]
        ch+=1
      c[i][j]=min(c[i][j],c[i][k]+c[k][j])
      
      
print(ans//2)

Submission status: Wrong Answer

Solution code:
import sys
import math
import heapq
mod=10**9+7
inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict, OrderedDict
#すべてのkeyが用意されてる defaultdict(int)で初期化
#順序を保ったdict
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  #変換後の末尾桁を0や0.01で指定
  #Decimal((str(0.5)).quantize(Decimal('0'), rounding=ROUND_HALF_UP))
from functools import lru_cache
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########
n=int(input())
A=[]
# ans=0
for i in range(n):
    a=list(map(int,input().split()))
    A.append(a)
    # ans+=sum(a)

#ans//=2
miti=[[] for i in range(n)]
for i in range(n):
    miti[i]=A[i][:]
    
for k in range(n):
    for j in range(k):
        for i in range(j):
            q=miti[i][j]
            w=miti[j][k]
            e=miti[k][i]
            #print(i,j,k,"\t",q,w,e)
            # q,w,e=sorted([[q,i,j],[w,j,k],[e,k,i]])
            # if max(q,w,e)==inf: continue
            if q+w==A[k][i] and q!=inf and w!=inf: miti[k][i]=inf;miti[i][k]=inf;continue
            if q+w<A[k][i] and q!=inf and w!=inf: print(-1);exit()
            if w+e==A[i][j] and e!=inf and w!=inf: miti[i][j]=inf;miti[j][i]=inf;continue
            if w+e<A[i][j]  and e!=inf and w!=inf : print(-1);exit()
            if e+q==A[j][k] and q!=inf and e!=inf: miti[j][k]=inf;miti[k][j]=inf;continue
            if e+q<A[j][k] and q!=inf and e!=inf: print(-1);exit()
            
            
                
            
ans=0
for i in range(n):
    for j in range(n):
        if miti[i][j]!=inf:
            ans+=miti[i][j]

print(ans//2)

Submission status: Wrong Answer

Solution code:
import sys
import math
import heapq
mod=10**9+7
inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict, OrderedDict
#すべてのkeyが用意されてる defaultdict(int)で初期化
#順序を保ったdict
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  #変換後の末尾桁を0や0.01で指定
  #Decimal((str(0.5)).quantize(Decimal('0'), rounding=ROUND_HALF_UP))
from functools import lru_cache
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########
n=int(input())
A=[]
# ans=0
for i in range(n):
    a=list(map(int,input().split()))
    A.append(a)
    # ans+=sum(a)

#ans//=2
miti=[[] for i in range(n)]
for i in range(n):
    miti[i]=A[i][:]
for k in range(n):
    for j in range(k):
        for i in range(j):
            q=miti[i][j]
            w=miti[j][k]
            e=miti[k][i]
            #print(i,j,k,"\t",q,w,e)
            # q,w,e=sorted([[q,i,j],[w,j,k],[e,k,i]])
            # if max(q,w,e)==inf: continue
            if q+w==A[k][i]: miti[k][i]=inf;miti[i][k]=inf;continue
            if q+w<A[k][i] and q!=inf and w!=inf: print(-1);exit()
            if w+e==A[i][j]: miti[i][j]=inf;miti[j][i]=inf;continue
            if w+e<A[i][j]  and e!=inf and w!=inf : print(-1);exit()
            if e+q==A[j][k]: miti[j][k]=inf;miti[k][j]=inf;continue
            if e+q<A[j][k] and q!=inf and e!=inf: print(-1);exit()
            
            
                
            
ans=0
for i in range(n):
    for j in range(n):
        if miti[i][j]!=inf:
            ans+=miti[i][j]

print(ans//2)

Submission status: Wrong Answer

Solution code:
import sys
import math
import heapq
mod=10**9+7
inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict, OrderedDict
#すべてのkeyが用意されてる defaultdict(int)で初期化
#順序を保ったdict
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  #変換後の末尾桁を0や0.01で指定
  #Decimal((str(0.5)).quantize(Decimal('0'), rounding=ROUND_HALF_UP))
from functools import lru_cache
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########
n=int(input())
A=[]
# ans=0
for i in range(n):
    a=list(map(int,input().split()))
    A.append(a)
    # ans+=sum(a)

#ans//=2
miti=A[:]
for k in range(n):
    for i in range(k):
        for j in range(i):
            q=miti[i][j]
            w=miti[j][k]
            e=miti[k][i]
            # q,w,e=sorted([[q,i,j],[w,j,k],[e,k,i]])
            # if max(q,w,e)==inf: continue
            if q+w==A[k][i]: miti[k][i]=inf;miti[i][k]=inf;continue
            if q+w<A[k][i] and q!=inf and w!=inf: print(-1);exit()
            if w+e==A[i][j]: miti[i][j]=inf;miti[j][i]=inf;continue
            if w+e<A[i][j]  and e!=inf and w!=inf : print(-1);exit()
            if e+q==A[j][k]: miti[j][k]=inf;miti[k][j]=inf;continue
            if e+q<A[j][k] and q!=inf and e!=inf: print(-1);exit()
            
            
                
            
ans=0
for i in range(n):
    for j in range(n):
        if miti[i][j]!=inf:
            ans+=miti[i][j]

print(ans//2)

Submission status: Wrong Answer

Solution code:
import sys
import math
import heapq
mod=10**9+7
inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict, OrderedDict
#すべてのkeyが用意されてる defaultdict(int)で初期化
#順序を保ったdict
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  #変換後の末尾桁を0や0.01で指定
  #Decimal((str(0.5)).quantize(Decimal('0'), rounding=ROUND_HALF_UP))
from functools import lru_cache
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########
n=int(input())
A=[]
# ans=0
for i in range(n):
    a=list(map(int,input().split()))
    A.append(a)
    # ans+=sum(a)

#ans//=2
miti=A[:]
for k in range(n):
    for i in range(k):
        for j in range(i):
            q=miti[i][j]
            w=miti[j][k]
            e=miti[k][i]
            # q,w,e=sorted([[q,i,j],[w,j,k],[e,k,i]])
            if max(q,w,e)==inf: continue
            if q+w==e: miti[k][i]=inf;miti[i][k]=inf;continue
            if q+w<e: print(-1);exit()
            if w+e==q: miti[i][j]=inf;miti[j][i]=inf;continue
            if w+e<q : print(-1);exit()
            if e+q==w: miti[j][k]=inf;miti[k][j]=inf;continue
            if e+q<w: print(-1);exit()
            
            
                
            
ans=0
for i in range(n):
    for j in range(n):
        if miti[i][j]!=inf:
            ans+=miti[i][j]

print(ans//2)

Submission status: Wrong Answer

Solution code:
print(-1)

Submission status: Wrong Answer

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

for i in range(N):
  for j in range(N):
    for k in range(N):
      if A[i][j] > A[i][k] + A[k][j]: 
        print(-1)
        exit()

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

d = warshall_floyd(A)

for i in range(N):
  for j in range(N):
    for k in range(N):
      a, b, c = d[i][j], d[i][k], d[k][j]
      if a != 0 and b != 0 and c!= 0 and a == b + c:
        d[i][j] = 0

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

print(ans)

Submission status: Wrong Answer

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

for i in range(N):
  for j in range(N):
    for k in range(N):
      if A[i][j] > A[i][k] + A[k][j]: 
        print(-1)
        exit()

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

d = warshall_floyd(A)

for i in range(N):
  for j in range(N):
    for k in range(N):
      if i!=k and j!=k and i!=j and d[i][j] == d[i][k] + d[k][j] and d[i][k] != float('inf') and d[k][j] != float('inf') and d[i][j] != float('inf'): 
        d[i][j] = float('inf')

ans = 0
for i in range(N):
  for j in range(i+1, N):
    if d[i][j] != float('inf'):
      ans += d[i][j]

print(ans)

Submission status: Wrong Answer

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

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

d = warshall_floyd(A)

if d != A:
  print("-1")
  exit()

for i in range(N):
  for j in range(N):
    for k in range(N):
      if i!=k and j!=k and i!=j and d[i][j] == d[i][k] + d[k][j] and d[i][k] != float('inf') and d[k][j] != float('inf') and d[i][j] != float('inf'): 
        d[i][j] = float('inf')

ans = 0
for i in range(N):
  for j in range(i+1, N):
    if d[i][j] != float('inf'):
      ans += d[i][j]

print(ans)

Submission status: Wrong Answer

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

for i in range(N):
  for j in range(i+1, N):
    for k in range(N):
      if A[i][j] > A[i][k] + A[k][j]:
        print("-1")
        exit()

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

d = warshall_floyd(A)

for i in range(N):
  for j in range(N):
    if A[i][j] != d[i][j]: 
      print("-1")
      exit()
    for k in range(N):
      if i!=k and j!=k and i!=j and A[i][j] == d[i][k] + d[k][j] and d[i][k] != float('inf') and d[k][j] != float('inf'): 
        d[i][j] = float('inf')
        d[j][i] = float('inf')

ans = 0
for i in range(N):
  for j in range(i+1, N):
    if d[i][j] != float('inf'):
      ans += d[i][j]

print(ans)

Submission status: Wrong Answer

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

for i in range(N):
  for j in range(i+1, N):
    for k in range(N):
      if A[i][j] > A[i][k] + A[k][j]:
        print("-1")
        exit()

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

d = warshall_floyd(A)

for i in range(N):
  for j in range(i+1, N):
    if A[i][j] != d[i][j]: 
      print("-1")
      exit()
    for k in range(N):
      if i!=k and j!=k and A[i][j] == d[i][k] + d[k][j] and d[i][k] != float('inf') and d[k][j] != float('inf'): 
        d[i][j] = float('inf')
        d[j][i] = float('inf')

ans = 0
for i in range(N):
  for j in range(i+1, N):
    if d[i][j] != float('inf'):
      ans += d[i][j]

print(ans)

Submission status: Wrong Answer

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

for i in range(N):
  for j in range(i+1, N):
    for k in range(N):
      if A[i][j] > A[i][k] + A[k][j]:
        print("-1")
        exit()

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

d = warshall_floyd(A)

for i in range(N):
  for j in range(i+1, N):
    if A[i][j] != d[i][j]: 
      print("-1")
      exit()
    for k in range(N):
      if i!=k and j!=k and d[i][j] == d[i][k] + d[k][j] and d[i][k] != float('inf') and d[k][j] != float('inf'): 
        d[i][j] = float('inf')
        d[j][i] = float('inf')

ans = 0
for i in range(N):
  for j in range(i+1, N):
    if d[i][j] != float('inf'):
      ans += d[i][j]

print(ans)

Submission status: Wrong Answer

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

for i in range(N):
  for j in range(i+1, N):
    for k in range(N):
      if A[i][j] > A[i][k] + A[k][j]:
        print("-1")
        exit()

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

d = warshall_floyd(A)

for i in range(N):
  for j in range(i+1, N):
    if A[i][j] != d[i][j]: 
      print("-1")
      exit()
    for k in range(N):
      if i!=k and j!=k and d[i][j] == d[i][k] + d[k][j]: 
        d[i][j] = float('inf')
        d[j][i] = float('inf')

ans = 0
for i in range(N):
  for j in range(i+1, N):
    if d[i][j] != float('inf'):
      ans += d[i][j]

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
import heapq
mod=10**9+7
inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict, OrderedDict
#すべてのkeyが用意されてる defaultdict(int)で初期化
#順序を保ったdict
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  #変換後の末尾桁を0や0.01で指定
  #Decimal((str(0.5)).quantize(Decimal('0'), rounding=ROUND_HALF_UP))
from functools import lru_cache
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########
n=int(input())
A=[]
# ans=0
for i in range(n):
    a=list(map(int,input().split()))
    A.append(a)
    # ans+=sum(a)

#ans//=2
miti=A[:]
for k in range(n):
    for i in range(n):
        for j in range(n):
            # q=miti[i][j]
            # w=miti[j][k]
            # e=miti[k][i]
            if (i==j or j==k or k==i or miti[i][k]==inf or miti[k][j]==inf):
                continue
            if miti[i][k]+miti[k][j]==A[i][j]:
                miti[i][j]=inf
            elif miti[i][k]+miti[k][j]<A[i][j]:
                print(-1);exit()
ans=0
for i in range(n):
    for j in range(n):
        if miti[i][j]!=inf:
            ans+=miti[i][j]

print(ans//2)

Submission status: Wrong Answer

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

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

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

d = warshall_floyd(A)

for i in range(N):
  for j in range(i+1, N):
    for k in range(N):
      if i!=k and j!=k and d[i][j] == d[i][k] + d[k][j]: 
        d[i][j] = float('inf')
        d[j][i] = float('inf')

ans = 0
for i in range(N):
  for j in range(i+1, N):
    if d[i][j] != float('inf'):
      ans += d[i][j]

print(ans)

Submission status: Wrong Answer

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

ans//=2

for i in range(n):
    for j in range(i):
        for k in range(j):
            q=A[i][j]
            w=A[j][k]
            e=A[k][i]
            o=sorted([q,w,e])
            if o[2]> sum(o[:2]) :print(-1);exit()
            if o[2]== sum(o[:2]): ans-=o[2]

print(ans)

Submission status: Wrong Answer

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

ans//=2

for i in range(n):
    for j in range(i):
        for k in range(j):
            q=A[i][j]
            w=A[j][k]
            e=A[k][i]
            if max(q,w,e)> sum([q,w,e])-max(q,w,e):print(-1);exit()
            if max(q,w,e)== sum([q,w,e])-max(q,w,e):ans-=max(q,w,e)

print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N=int(input())
import copy
def warshall_floyd(d):
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j]=min(d[i][j],d[i][k]+d[k][j])
    return d

  
cost=[list(map(int,input().split())) for i in range(N)]
D=copy.deepcopy(cost)
E=warshall_floyd(cost)
      
if D!=E: 
  print(-1)
  exit()

for i in range(N):
  for j in range(N):
    for k in range(N):
      if E[i][j]!=0 and E[i][k]!=0 and E[k][j]!=0:
        if E[i][j]==E[i][k]+E[k][j]:
          E[i][j]=0       
ans=0
for i in range(N):
  ans+=sum(E[i]) 
print(ans//2)

Submission status: Wrong Answer

Solution code:
N=int(input())
import copy
def warshall_floyd(d):
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j]=min(d[i][j],d[i][k]+d[k][j])
    return d

  
cost=[list(map(int,input().split())) for i in range(N)]
D=copy.deepcopy(cost)
E=warshall_floyd(cost)
      
if D!=E: 
  print(-1)
  exit()

for i in range(N):
  for j in range(N):
    for k in range(N):
      a,b,c=E[i][j],E[j][k],E[i][k]
      if a+b==c and a!=0 and b!=0 and c!=0:
        E[i][k]=0       
ans=0
for i in range(N):
  ans+=sum(E[i]) 
print(ans//2)

Submission status: Wrong Answer

Solution code:
N=int(input())
import copy
def warshall_floyd(d):
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j]=min(d[i][j],d[i][k]+d[k][j])
    return d

  
cost=[list(map(int,input().split())) for i in range(N)]
D=copy.deepcopy(cost)
E=warshall_floyd(cost)
      
if D!=E: 
  print(-1)
  exit()

for i in range(N):
  for j in range(N):
    for k in range(N):
      a,b,c=D[i][j],D[j][k],D[i][k]
      if a+b==c and a!=0 and b!=0 and c!=0:
        D[i][k]=0       
ans=0
for i in range(N):
  ans+=sum(D[i]) 
print(ans//2)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
N=int(input())

def dijkstra(s,n,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
               
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d
  
cost=[list(map(int, input().split())) for i in range(N)]
ans=0
for i in range(N):
  d=dijkstra(i,N,cost)
  for j in range(N):
    if i<j:
      if d[j]!=cost[i][j]:
        print(-1)
        exit()
D=cost
for i in range(N):
  for j in range(N):
    for k in range(N):
      a,b,c=cost[i][j],cost[j][k],cost[i][k]
      if a+b==c and a!=0 and b!=0 and c!=0:
        D[i][k]=0       
ans=0
for i in range(N):
  ans+=sum(D[i]) 
print(ans//2)

Submission status: Wrong Answer

Solution code:
N=int(input())

def dijkstra(s,n,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
               
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d
  
cost=[list(map(int, input().split())) for i in range(N)]
ans=0
for i in range(N):
  d=dijkstra(i,N,cost)
  for j in range(N):
    if i<j and d[j]!=cost[i][j]:
      print(-1)
      exit()
D=cost
for i in range(N):
  for j in range(N):
    for k in range(N):
      a,b,c=cost[i][j],cost[j][k],cost[i][k]
      if a+b==c and a!=0 and b!=0 and c!=0:
        D[i][k]=0       
ans=0
for i in range(N):
  ans+=sum(D[i]) 
print(ans//2)