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:
#!/usr/bin/env python3
#ABC74 D

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = [LI() for _ in range(n)]
ans = 0
for i in range(n):
    for j in range(i+1,n):
        ans += a[i][j]

for i in range(n):
    for j in range(i+1,n):
        for k in range(n):
            if i == k or j == k:
                continue
            if a[i][j] > a[i][k] + a[k][j]:
                print(-1)
                quit()
            if a[i][j] == a[i][k] + a[k][j]:
                ans -= a[i][j]
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
#ABC74 D

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = [LI() for _ in range(n)]
ans = 0
for i in range(n):
    for j in range(i,n):
        ans += a[i][j]

for k in range(n):
    for i in range(n):
        for j in range(i,n):
            if i == k or j == k:
                continue
            if a[i][j] > a[i][k] + a[k][j]:
                print(-1)
                quit()
            if a[i][j] == a[i][k] + a[k][j]:
                ans -= a[i][j]
print(ans)

Submission status: Wrong Answer

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

nA = [line[:] for line in A]
cnt = 0

for k in range(N):
    for i in range(N):
        for j in range(N):
            if nA[i][j] > nA[i][k] + nA[k][j]:
                nA[i][j] = nA[i][k] + nA[k][j]
            elif not(i == j or j == k or k == i) and nA[i][j] == nA[i][k] + nA[k][j]:
                cnt += nA[i][j]

if A != nA:
    print(-1)
else:
    ans = sum(sum(line) for line in A) - cnt
    ans //= 2
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys,bisect as bs,collections as cl
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
n = onem()

ans = 0
a = []

for i in range(n):
    a.append(l())

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]:
                print(-1)
                exit()
for i in range(n-1):
    for j in range(1,n):
        for k in range(n):
            if i == k or 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:
INF = float('inf')

def warshall_floyd(d,n):
    max_d = 0
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if(i==j or j==k or i==k):continue
                if(d[i][j]!=INF):
                    max_d = max(max_d,d[i][j])
                if(d[i][j]>=d[i][k] + d[k][j]):
                    d[i][j] = INF
                    d[j][i] = INF
    return max_d

N = int(input())
gp = [[int(x) for x in input().split()]for _ in range(N)]
max_d = warshall_floyd(gp,N)
ans = 0
for d in gp:
    ans += sum([i if i!=INF else 0 for i in d])
print(ans//2 if ans//2 >= max_d else -1)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
def main():
    INF = float('inf')
    N = int(input())
    d = [[int(x) for x in input().split()]for _ in range(N)]
    ans = 0
    for i in d:
        ans += sum(i)
    ans //= 2
    max_d = 0
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if(i==j or j==k or i==k or d[i][j]==INF):continue
                max_d = max(max_d,d[i][j])
                if(d[i][j]>=d[i][k] + d[k][j]):
                    ans -= d[i][j]
                    d[i][j] = INF
                    d[j][i] = INF
    print(ans if ans >= max_d else -1)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

def judge() :
    s = 0
    for k in range(N) :
        for i in range(N) :
            if i == k :
                continue
            for j in range(i + 1, N) :
                if j == k :
                    continue
                if A[i][k] + A[k][j] < A[i][j] :
                    return -1
                elif A[i][k] + A[k][j] == A[i][j] :
                    s += A[i][j]
    tot = 0
    for i in range(N) :
        for j in range(i + 1, N) :
            tot += A[i][j]
    return tot - s
    
print(judge())

Submission status: Wrong Answer

Solution code:
inf = float("inf")
N = int(input())
A = []
for _ in range(N):
    a = [int(s) for s in input().split()]
    A.append(a)
edges = []
for i in range(N - 1):
    for j in range(i + 1, N):
        edges.append((A[i][j], i, j))
edges.sort()
dists = [[inf] * N for _ in range(N)]
for i in range(N):
    dists[i][i] = 0
ans = 0
for d, i, j in edges:
    if dists[i][j] != inf and dists[i][j] < d:
        print(-1)
        exit()
    if dists[i][j] == d:
        continue
    ans += d
    for k in range(N):
        if dists[j][k] == inf:
            continue
        dists[i][k] = min(dists[i][k], d + dists[j][k])
        dists[k][i] = min(dists[k][i], d + dists[k][j])
    for k in range(N):
        if dists[i][k] == inf:
            continue
        dists[j][k] = min(dists[j][k], d + dists[i][k])
        dists[k][j] = min(dists[k][j], d + dists[k][i])
print(ans)

Submission status: Wrong Answer

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


def main():
    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
                if A[i][j] > A[i][k] + A[k][j]:
                    print(-1)
                    return
                if A[i][k] >= A[i][j] + A[k][j]:
                    A[i][k] = float('INF')
    ans = 0
    for i in range(N):
        for j in range(N):
            if A[i][j] == float('INF'):
                continue
            ans += A[i][j]
            A[j][i] = 0
    print(ans)


main()

Submission status: Wrong Answer

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


def main():
    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
                if A[i][j] > A[i][k] + A[k][j]:
                    print(-1)
                    return
    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
                if A[i][k] >= A[i][j] + A[k][j]:
                    A[i][k] = float('INF')
    ans = 0
    for i in range(N):
        for j in range(N):
            if A[i][j] == float('INF'):
                continue
            ans += A[i][j]
            A[j][i] = 0
    print(ans)


main()

Submission status: Wrong Answer

Solution code:
import sys
from heapq import heappush, heappop

N=input()
d=[ [ float("inf") for j in range(N+1) ] for i in range(N+1) ] 
for i in range(N+1):
	d[i][i]=0

hq=[]
for i in range(N):
	L=map(int, sys.stdin.readline().split())
	for j in range(i+1,N):
		heappush( hq, (L[j],i+1,j+1) )


ans=0
for n in range(N-1):
	cost,x,y,=heappop( hq )
	d[x][y]=cost
	d[y][x]=cost
	ans+=cost


#Warshall-Floyd
for k in range(1,N+1):
	for i in range(1,N+1):
		for j in range(1,N+1):
			d[i][j]=min(d[i][j], d[i][k]+d[k][j])


while hq:
	input_cost,x,y=heappop(hq)
	cost=d[x][y]
	if cost<input_cost:
		print -1
		quit()
	elif input_cost<cost:
		#print "x,y,input_cost,cost :::: ",x,y,input_cost,cost
		d[x][y]=input_cost
		d[y][x]=input_cost
		ans+=input_cost

print ans

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import numpy as np
#from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph)
#from scipy.sparse.csgraph import dijkstra
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix

from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul,itemgetter
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
#input=sys.stdin.readline  #危険！基本オフにしろ！
sys.setrecursionlimit(10**8)

def main():
    n=int(input())
    grid=[list(map(int,input().split()))for i in range(n)]
    p=floyd_warshall(csgraph=csr_matrix(grid))
    q=[list(i) for i in p]
    
    if q!=grid:
        print(-1)
    else:
        for i in range(n):
            p[i][i]=float("inf")
        ans=0
        for i in range(n):
            for j in range(i):
                if i==j:
                    continue
                if p[i][j]<min(np.array(p[i])+np.array(p[j])):
                    
                    ans+=p[i][j]
        print(int(ans))

Submission status: Wrong Answer

Solution code:
#from numpy import*
#from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph)
#from scipy.sparse.csgraph import dijkstra
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix

from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul,itemgetter
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
#input=sys.stdin.readline  #危険！基本オフにしろ！
sys.setrecursionlimit(10**8)


def main():
    n=int(input())
    grid=[list(map(int,input().split()))for i in range(n)]
    p=floyd_warshall(csgraph=csr_matrix(grid))
    q=[list(i) for i in p]
    
    if q!=grid:
        print(-1)
    else:
        for i in range(n):
            p[i][i]=float("inf")
        ans=0
        P=[min(p[i])for i in range(n)]
#        print(p)
        for i in range(n):
            for j in range(i):
                if i==j:
                    continue
                if p[i][j]<P[i]+P[j]:
                    
                    ans+=p[i][j]
        print(int(ans))




if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#from numpy import*
from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph)
#from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul,itemgetter
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
#input=sys.stdin.readline  #危険！基本オフにしろ！
sys.setrecursionlimit(10**8)


def main():
    n=int(input())
    grid=[list(map(int,input().split()))for i in range(n)]
    p=shortest_path(csgraph=csr_matrix(grid))
    q=[list(i) for i in p]
    
    if q!=grid:
        print(-1)
    else:
        for i in range(n):
            p[i][i]=float("inf")
        ans=0
        P=[min(p[i])for i in range(n)]
#        print(p)
        for i in range(n):
            for j in range(i):
                if i==j:
                    continue
                if p[i][j]<P[i]+P[j]:
                    
                    ans+=p[i][j]
        print(int(ans))




if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#from numpy import*
from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph)
#from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul,itemgetter
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
#input=sys.stdin.readline  #危険！基本オフにしろ！
sys.setrecursionlimit(10**8)


def main():
    n=int(input())
    grid=[list(map(int,input().split()))for i in range(n)]
    p=shortest_path(csgraph=csr_matrix(grid))
    q=[list(i) for i in p]
    
    if q!=grid:
        print(-1)
    else:
        for i in range(n):
            p[i][i]=float("inf")
        ans=0
        P=[min(p[i])for i in range(n)]
#        print(p)
        for i in range(n):
            for j in range(i):
                if i==j:
                    continue
                if p[i][j]<P[i]+P[j]:
                    
                    ans+=p[i][j]
        print(int(ans))

Submission status: Wrong Answer

Solution code:
#from numpy import*
from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph)
#from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul,itemgetter
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
#input=sys.stdin.readline  #危険！基本オフにしろ！
sys.setrecursionlimit(10**8)


def main():
    n=int(input())
    grid=[list(map(int,input().split()))for i in range(n)]
    p=shortest_path(csgraph=csr_matrix(grid))
    q=[list(i) for i in p]
    
    if q!=grid:
        print(-1)
    else:
        for i in range(n):
            p[i][i]=float("inf")
        ans=0
        P=[min(p[i])for i in range(n)]
#        print(p)
        for i in range(n):
            for j in range(i):
                if p[i][j]<P[i]+P[j]:
                    
                    ans+=p[i][j]
        print(int(ans))




if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#from numpy import*
from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph)
#from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul,itemgetter
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
#input=sys.stdin.readline  #危険！基本オフにしろ！
sys.setrecursionlimit(10**8)


def main():
    n=int(input())
    grid=[list(map(int,input().split()))for i in range(n)]
    p=shortest_path(csgraph=csr_matrix(grid))
    q=[list(i) for i in p]
    
    if q!=grid:
        print(-1)
    else:
        for i in range(n):
            p[i][i]=float("inf")
        ans=0
        P=[min(p[i])for i in range(n)]
        #print(p)
        for i in range(n):
            for j in range(i):
                if p[i][j]<P[i]+P[j]:
                    ans+=p[i][j]
        print(int(ans))




if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#from numpy import*
from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph)
#from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
#input=sys.stdin.readline  #危険！基本オフにしろ！
sys.setrecursionlimit(10**8)


class UNION_FIND(object):
    def __init__(self,n):
        self.parent=[-1 for i in range(n)]
        
    def root(self,x):
        if self.parent[x]<0:
            return x
        else:
            self.parent[x]=self.root(self.parent[x])
            return self.parent[x]
 
    def size(self,x):
        return -self.parent[self.root(x)]
    def union(self,x,y):
        x=self.root(x)
        y=self.root(y)
        if x==y:
            return False
        if self.size(x)<self.size(y):
            x,y=y,x
        self.parent[x]+=self.parent[y]
        self.parent[y]=x
        return True
def compute_mst_kruskal(max_v, edges, flip):
    edges.sort(key=lambda x: x[2],reverse=flip)
    uf = UNION_FIND(max_v)
    mst = []
    for (a,b,c) in edges:
        if uf.root(a)!= uf.root(b):
            uf.union(a,b)
            mst.append(c)
    return mst



def main():
    n=int(input())
    grid=[list(map(int,input().split()))for i in range(n)]
    p=shortest_path(csgraph=csr_matrix(grid))
    q=[list(i)for i in p]
    
    if q!=grid:
        print(-1)
    else:
        edges=[]
        for i in range(n):
            for j in range(i+1,n):
                edges.append((i,j,grid[i][j]))
#        print(edges)
        print(sum(compute_mst_kruskal(n,edges,0)))
                




if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

import numpy as np

sys.setrecursionlimit(10000)
INF = float('inf')

N = int(sys.stdin.readline())
A = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
A = np.array(A, dtype=float) + np.diag([np.inf] * N)

useless = np.zeros((N, N), dtype=bool)
impossible = np.zeros((N, N), dtype=bool)
for via in range(N):
    # R[i][j]: i -> via -> j の距離
    R = sum(np.meshgrid(A[via], A[via]))
    useless |= R == A
    impossible |= R < A

if impossible.sum():
    print(-1)
else:
    print(int(A[~useless].sum() // 2))

Submission status: Wrong Answer

Solution code:
# 小さい距離から見ていく
# 既に作った道の範囲で、任意の2点の最短距離を持っておく
# 既存の最短距離より大きい：矛盾
# 既存の最短距離と等しい：増やしても何も変わらず
# 既存の最短距離より小さい：追加する必要あり

import numpy as np
N = int(input())
A = [[int(x) for x in input().split()] for _ in range(N)]

edge = []

for i in range(N):
  for j in range(i):
    edge.append((A[i][j],j,i))
edge.sort()

INF = 10**3
dist = np.full((N,N),INF,dtype=np.int64) - np.eye(N,dtype=np.int64)*INF

answer = 0
for d,x,y in edge:
  if d > dist[x,y]:
    answer = -1
    break
  if d == dist[x,y]:
    continue
  # 追加
  answer += d
  dist[x,y] = d
  dist[y,x] = d
  # 距離行列の更新
  # (i,j) -> (i,x),(x,y),(y,j)
  dist_use_xy = np.add.outer(dist[:,x], dist[:,y]) + d
  dist = np.minimum(dist,np.minimum(dist_use_xy,dist_use_xy.T))
  
print(answer)

Submission status: Wrong Answer

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

INF = 10**9+10
E = np.zeros(((N*(N-1))//2,3),dtype=np.int64)
k = 0
for i in range(N):
    for j in range(i+1,N):
        E[k,0] = A[i][j]
        E[k,1] = i
        E[k,2] = j
        k += 1
E = E[E.argsort(0)[0]]
B = np.ones((N,N),dtype=np.int64)*INF
ans = 0
for l,i,j in E:
    l_min = np.min(B[i]+B[j])
    if l > l_min:
        ans = -1
        break
    elif l < l_min:
        ans += l
    B[i][j] = l
    B[j][i] = l
print(ans)

Submission status: Wrong Answer

Solution code:
def solve():
    N = int(input())
    A = []
    for h in range(N):
        A.append(list(map(int,input().split())))
    B = [[0 for w in range(N)] for h in range(N)]
    for i in range(N):
        for j in range(i+1,N):
            flag = True
            for k in range(N):
                if i != k and j != k:
                    if A[i][k] + A[k][j] < A[i][j]:
                        return -1
                    if A[i][k] + A[k][j] == A[i][j]:
                        B[i][k] = 1
                        B[k][i] = 1
                        B[k][j] = 1
                        B[j][k] = 1
                        flag = False
            if flag:
                B[i][j] = 1
                B[j][i] = 1
    ans = 0
    for i in range(N):
        for j in range(i+1,N):
            ans += B[i][j] * A[i][j]
        #print(*B[i])
    return ans

print(solve())

Submission status: Wrong Answer

Solution code:
# encoding:utf-8
import copy
import numpy as np
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import math

N = int(input())

A = []
for i in range(N):
    a = [int(i) for i in input().split()]
    A.append(a)

exist = True
ans = 0
for i in range(N):
    for j in range(N):
        for k in range(N):
            if A[j][k]>A[j][i]+A[i][k]:
                exist = False

if exist:
    for j in range(N):
        for k in range(N):
            tmp = 10**10
            for i in range(N):
                if j==i or i==k:
                    pass
                else:
                    tmp = min(tmp,A[j][i]+A[i][k])
            if A[j][k] < tmp:
                ans += A[j][k]
    ans = ans//2


print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
s=[list(map(int,input().split()))for i in range(n)]
c=0
h=True
for i in range(n):
    s[i][i]=10**10
for i in range(n):
    for j in range(i):
        d=min(map(sum,zip(s[i],s[j])))
        if s[i][j]>d:
            print(-1)
            h=False
            break
        elif s[i][j]<d:
            c+=s[i][j]
else:
    if h:
        print(c)

Submission status: Wrong Answer

Solution code:
n=int(input())
s=[list(map(int,input().split()))for i in range(n)]
c=0
for i in range(n):
    s[i][i]=10**10
for i in range(n):
    for j in range(i):
        d=min(map(sum,zip(s[i],s[j])))
        if s[i][j]>d:
            print(-1)
            break
        elif s[i][j]<d:
            c+=s[i][j]
else:
    print(c)

Submission status: Wrong Answer

Solution code:
from scipy.sparse.csgraph import floyd_warshall as wf
n=int(input())
s=[list(map(int,input().split()))for i in range(n)]
c=0
for i in range(n):
    s[i][i]=float("inf")
for i in range(n):
    for j in range(i):
        d=min(map(sum,zip(s[i],s[j])))
        if s[i][j]>d:
            print(-1)
            break
        if s[i][j]<d:
            c+=s[i][j]
else:
    print(c)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N=int(input())
data=[]
dist=dict()
for i in range(N):
    line=list(map(int,input().split()))
    for j in range(i+1,N):
        data.append((i,j,line[j]))
        dist[(i,j)]=float('inf')
data.sort(key=lambda x:x[2])
ans=0
for d in data:
    i,j,x=d
    if dist[(i,j)]<x:
        ans=-1
        break
    elif dist[(i,j)]>x:
        dist[(i,j)]=x
        ans+=x
        for k in range(N):
            if i==k or j==k:continue
            a,b,c=i,j,k
            if b>c:b,c=c,b
            if a>b:a,b=b,a
            dist[(a,b)]=min(dist[(a,c)]+dist[(b,c)],dist[(a,b)])
            dist[(b,c)]=min(dist[(a,b)]+dist[(a,c)],dist[(b,c)])
            dist[(a,c)]=min(dist[(a,b)]+dist[(b,c)],dist[(a,c)])
print(ans)

Submission status: Wrong Answer

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

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

for c in range(N):
    for a in range(N):
        for b in range(N):
            A[a][b]=min(A[a][b],A[a][c]+A[c][b])
            
L=[i for i in range(N)]

if A==AA:
    S=0
    G=[0]
    for i in range(N):
        if len(G)==N:
            break
        else:
            ml=10**10
            mp=-1
            for j in range(N):
                if i==j:
                    pass
                elif L[i] in G and L[j] in G:
                    pass
                elif L[i] in G:
                    if A[i][j]<ml:
                        ml=A[i][j]
                        mp=j
                elif L[j] in G:
                    if A[i][j]<ml:
                        ml=A[i][j]
                        mp=i
            S+=ml
            G.append(mp)
    print(S)
    
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

def main():
    input = sys.stdin.readline
    N = int(input())
    A = np.array([list(map(int, input().split())) for i in range(N)])
    #A = [list(map(int, input().split())) for _ in range(N)]
    #A = np.array(A)

    INF = 10**10
    for i in range(N):
        A[i, i] = INF

    ans = 0
    for i in range(N):
        for j in range(i):
            #bipas = min(map(sum, zip(A[i], A[j])))
            bipas = np.min(A[i] + A[j])

            if A[i, j] > bipas:
                ans = -1
                break
            elif A[i, j] < bipas:
                ans += A[i, j]

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

def main():
    input = sys.stdin.readline
    N = int(input())
    A = [list(map(int, input().split())) for _ in range(N)]
    A = np.array(A)

    INF = 10**10
    for i in range(N):
        A[i, i] = INF

    ans = 0
    for i in range(N):
        for j in range(i):
            #bipas = min(map(sum, zip(A[i], A[j])))
            bipas = np.min(A[i] + A[j])

            if A[i, j] > bipas:
                ans = -1
                break
            elif A[i, j] < bipas:
                ans += A[i, j]

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    A = [list(map(int, input().split())) for _ in range(N)]

    INF = float('INF')
    for i in range(N):
        A[i][i] = INF

    ans = 0
    for i in range(N):
        for j in range(i):
            #bipas = min(map(sum, zip(A[i], A[j])))
            bipas = min([a+b for a, b in zip(A[i], A[j])])

            if A[i][j] > bipas:
                ans = -1
                break
            elif A[i][j] < bipas:
                ans += A[i][j]

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    A = [list(map(int, input().split())) for _ in range(N)]

    INF = float('INF')
    for i in range(N):
        A[i][i] = INF

    ans = 0
    for i in range(N):
        for j in range(i+1):
            bipas = min(map(sum, zip(A[i], A[j])))

            if A[i][j] > bipas:
                ans = -1
                break
            elif A[i][j] < bipas:
                ans += A[i][j]

    print(ans)


if __name__ == '__main__':
    main()