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: Accepted

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)

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]))
    R[via] = np.inf
    R[:, via] = np.inf
    useless |= R == A
    impossible |= R < A
if impossible.sum():
    print(-1)
else:
    print(int(A[~useless].sum() // 2))

Submission status: Accepted

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**18
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: Accepted

Solution code:
N = int(input())
li = [ [ int(it) for it in input().split() ]  for i in range(N) ]
iru = [[1]*N for i in range(N)] 

Flag = True
s = 0
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 ( li[i][j] > li[i][k] + li[k][j] ):
        Flag = False
      if ( li[i][j] == li[i][k] + li[k][j] ):
        iru[i][j]=0
for i in range(N):
  for j in range(N):
    if (i<j):
      s += iru[i][j] * li[i][j]

print ( s if Flag else -1 )

Submission status: Accepted

Solution code:
n = int(input())
import numpy as np
a = np.array([list(map(int,input().split())) for _ in range(n)])
ans = 0
for i in range(n):
    a[i][i] = 10**9+1
for i in range(n):
    for j in range(i,n):
        if i==j:
            continue
        dp = np.min(a[i]+a[j])
        if a[i][j]<dp:
            ans += a[i][j]
        elif a[i][j]>dp:
            print(-1)
            exit()
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
from math import*
from collections import deque
from collections import defaultdict
from itertools import permutations
from heapq import*
from collections import Counter
from itertools import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = 10**18
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

n = int(input())
l = [list(map(int,input().split())) for _ in range(n)]
ans = 0
for j in range(n):
    for i in range(n):
        f = True
        for k in range(n):
            if l[i][j] > l[i][k]+l[k][j]:
                print(-1)
                exit()
            if l[i][j] == l[i][k] + l[k][j] and i !=k and k != j:
                f = False
        if f:
            ans += l[i][j]
print(ans//2)

Submission status: Accepted

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: Accepted

Solution code:
from functools import reduce
import math
import copy

def main():
    # 文字列の2進数を数値にする
    # '101' → '5'
    # 文字列の頭に'0b'をつけてint()にわたす
    # binary = int('0b'+'101',0)

    # 2進数で立っているbitを数える
    # 101(0x5) → 2
    # cnt_bit = bin(5).count('1')
    
    # N! を求める
    # f = math.factorial(N)

    # N の逆元
    # N_inv = pow(N,MOD-2,MOD)

    # nCr
    # Nの階乗 * rの階乗の逆元 * n-rの階乗の逆元
    
    # 切り捨て
    # 4 // 3
    # 切り上げ
    #-(-4 // 3)
    
    # 初期値用:十分大きい数(100億)
    INF = float("inf")

    # 大きな素数
    MOD = 10**9+7
    
    # 1文字のみを読み込み
    # 入力:2
    # a = input().rstrip()
    # 変数:a='2'
    
    # スペース区切りで標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a, b, c, d = (int(_) for _ in input().split())  
    # 変数:a=2 b=4 c=5 d =7
    
    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a = list(int(_) for _ in input().split())
    # 変数:a = [2, 4, 5, 7]    

    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2457
    # a = list(int(_) for _ in input())
    # 変数:a = [2, 4, 5, 7]    
    N = int(input())
    a = []
    ans = 0
    for i in range(N):
        a.append(list(int(_) for _ in input().split()))
    d = copy.deepcopy(a)
    
    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()
                elif a[i][j] == a[i][k]+a[k][j] and a[i][j] != 0 and k!=i and k!=j:
                    d[i][j] = 0
          
    for i in range(N):
        ans += sum(d[i])
    print(ans//2)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq
INF = 10**10
n = int(input())
a = [[int(item) for item in input().split()] for _ in range(n)]
b = [[INF for _ in range(n)] for _ in range(n)]

ans = 0
for i in range(n):
    ans += sum(a[i])
    a[i][i] = INF
ans //= 2

for i in range(n):
    for j in range(i):
        bipas = min(map(sum, zip(a[i], a[j])))
        if a[i][j] > bipas:
            print(-1)
            exit()
        if a[i][j] == bipas:
            ans -= a[i][j]
print(ans)

Submission status: Accepted

Solution code:
import itertools, sys

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

exists = [[True] * n for _ in range(n)]
for k, i, j in itertools.product(range(n), repeat=3):
    if a[i][k] + a[k][j] == a[i][j] and i != k and k != j:
        exists[i][j] = False
    elif a[i][k] + a[k][j] < a[i][j]:
        print(-1)
        sys.exit()

ans = 0
for i in range(n):
    for j in range(i + 1, n):
        if exists[i][j]:
            ans += a[i][j]
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
from scipy.sparse.csgraph import floyd_warshall as wf
n=int(input())
s=np.array([list(map(int,input().split()))for i in range(n)])
if np.any(s!=wf(s,directed=False)):
    print(-1)
else:
    c=0
    for i in range(n):
        s[i][i]=10**10
    for i in range(n):
        for j in range(i+1,n):
            d=np.min(s[i]+s[j])
            if s[i,j]!=d:
                c+=s[i,j]
    else:
        print(c)

Submission status: Accepted

Solution code:
import numpy as np
N=int(input())
A=[np.array(list(map(int,input().split()))) for i in range(N)]
ans=sum([sum(A[i]) for i in range(N)])
ans//=2
for i in range(N):
    A[i][i]=10**10
def main(ans):
    for i in range(N):
        for j in range(i+1,N):
            Min=min(A[i]+A[j])
            if Min<A[i][j]:
                return -1
            if Min==A[i][j]:
                ans-=A[i][j]
    return ans
print(main(ans))

Submission status: Accepted

Solution code:
import numpy as np
N=int(input())
A=[np.array(list(map(int,input().split()))) for i in range(N)]
ans=sum([sum(A[i]) for i in range(N)])
ans//=2
for i in range(N):
    A[i][i]=10**10
def main(ans):
    for i in range(N):
        for j in range(i+1,N):
            Min=np.min(A[i]+A[j])
            if Min<A[i][j]:
                return -1
            if Min==A[i][j]:
                ans-=A[i][j]
    return ans
print(main(ans))

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
N=int(input())
dist=[list(map(int,input().split())) for i in range(N)]
ans=sum([sum(dist[i]) for i in range(N)])
for i in range(N):
    dist[i][i]=float('inf')
ans//=2
def main(ans):
    for i in range(N):
        for j in range(i+1,N):
            Min=min(map(sum,zip(dist[i],dist[j])))
            if Min<dist[i][j]:
                return -1
            if Min==dist[i][j]:
                ans-=dist[i][j] 
    return ans
print(main(ans))

Submission status: Accepted

Solution code:
import sys

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

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

            if A[i][j] > bipas:
                print(-1)
                return 0
            elif A[i][j] < bipas:
                ans += A[i][j]

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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:
                print(-1)
                return 0
            elif A[i][j] < bipas:
                ans += A[i][j]

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

ans = 0
for i in range(n):
  ans += sum(a[i])

memo = {}
for i in range(n):
  memo[i] = {}
for k in range(n):
  for i in range(n):
    for j in range(n):
      if k != i and i != j and j != k :
        if a[i][j] > a[i][k]+a[k][j]:
          print(-1)
          exit()
        elif a[i][j] == a[i][k]+a[k][j]:
          if j not in memo[i]:
            ans -= a[i][j]
            memo[i][j] = 1
                  
print(ans//2)

#プリム法
#mincost = [float("inf")]*n
#used = [False]*n
#mincost[0] = 0
#res = 0
#
#while True:
#  v = -1
#  for u in range(n):
#    if (not used[u]) and (v == -1 or mincost[u] < mincost[v]):
#      v = u
#  if v == -1:
#    break
#  used[v] = True
#  res += mincost[v]
#  for u in range(n):
#    mincost[u] = min(mincost[u],a[v][u])

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A

#B

#C
"""
a,b,c,d,e,f = LI()
a *= 100
b *= 100
ans = [a,0]
for i in range(f//a+1):
    for j in range((f-a*i)//b+1):
        for k in range((f-a*i-b*j)//c+1):
            for l in range((f-a*i-b*j-c*k)//d+1):
                if i or j or k or l:
                    s = c*k+d*l
                    w = a*i+b*j
                    q = w*e//100
                    if s <= q:
                        if w+s <= f:
                            if ans[1]/ans[0] < s/(s+w):
                                ans = [w+s,s]
print(*ans)
"""

#D
n = I()
d = LIR(n)
l = [[1 for j in range(n)] for i in range(n)]
for k in range(n):
    for i in range(n):
        for j in range(n):
            if d[i][j] > d[i][k]+d[k][j]:
                print(-1)
                quit()
            if d[i][j] == d[i][k]+d[k][j]:
                l[i][j] = l[i][k]+l[k][j]

ans = 0
for i in range(n):
    for j in range(n):
        if l[i][j] == 4:
            ans += d[i][j]
ans //= 2
print(ans)
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A

#B

#C
"""
a,b,c,d,e,f = LI()
a *= 100
b *= 100
ans = [a,0]
for i in range(f//a+1):
    for j in range((f-a*i)//b+1):
        for k in range((f-a*i-b*j)//c+1):
            for l in range((f-a*i-b*j-c*k)//d+1):
                if i or j or k or l:
                    s = c*k+d*l
                    w = a*i+b*j
                    q = w*e//100
                    if s <= q:
                        if w+s <= f:
                            if ans[1]/ans[0] < s/(s+w):
                                ans = [w+s,s]
print(*ans)
"""

#D
n = I()
a = LIR(n)
d = [[a[i][j] for i in range(n)] for j in range(n)]
l = [[1 for j in range(n)] for i in range(n)]
for k in range(n):
    for i in range(n):
        for j in range(n):
            if d[i][j] >= d[i][k]+d[k][j]:
                d[i][j] = d[i][k]+d[k][j]
                l[i][j] = l[i][k]+l[k][j]

if a != d:
    print(-1)
    quit()
ans = 0
for i in range(n):
    for j in range(n):
        if l[i][j] == 4:
            ans += d[i][j]
ans //= 2
print(ans)
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = [list(map(int, input().split())) for _ in range(N)]
    ans = 0
    for i in range(N):
        for j in range(N):
            if i == j:
                continue
            direct = True
            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][j] == A[i][k] + A[k][j] and i != k and j != k:
                    direct = False
            if direct:
                ans += A[i][j]
    print(ans // 2)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

def calc():
    ans=sum(map(sum,A))
    for i in range(N):
        for j in range(N):
            used=True
            for k in range(N):
                if i==k or k==j:continue
                if A[i][j]>A[i][k]+A[k][j]:
                    return -1
                elif A[i][j]==A[i][k]+A[k][j]:
                    used=False
            if not used:
                ans-=A[i][j]
    return ans//2
                
print(calc())

Submission status: Accepted

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

def calc():
    ans=0
    for i in range(N):
        for j in range(N):
            used=True
            for k in range(N):
                if i==k or k==j:continue
                if A[i][j]>A[i][k]+A[k][j]:
                    return -1
                elif A[i][j]==A[i][k]+A[k][j]:
                    used=False
            if used:
                ans+=A[i][j]
    return ans//2
                
print(calc())

Submission status: Accepted

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

def calc():
    ans=0
    for i in range(N):
        for j in range(N):
            used=True
            for k in range(N):
                if A[i][j]>A[i][k]+A[k][j]:
                    return -1
                if i==k or k==j:continue
                if A[i][j]==A[i][k]+A[k][j]:
                    used=False
            if used:
                ans+=A[i][j]
    return ans//2
                
print(calc())

Submission status: Accepted

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

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

for k in range(n):
    edgesk = edges[k]
    for i in range(n):
        disti = dist[i]
        edgesik = edges[i][k]
        for j in range(n):
            if disti[j] > edgesik + edgesk[j]:
                disti[j] = edgesik + edgesk[j]

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

Submission status: Accepted

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

n = int(input())

a = []

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

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

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

# Minimam total path length
min_total = 0

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

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

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

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

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

print(min_total)

Submission status: Accepted

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

from copy import deepcopy

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

# ワーシャルフロイドで全頂点の最短距離
B = deepcopy(A)
for k in range(N):
    for i in range(N):
        for j in range(N):
            # 最短 > 経由 があればNG
            if A[i][j] > A[i][k] + A[k][j]:
                print(-1)
                exit()
            # 最短 = 経由 があるなら、経由を使えば全長を減らせる
            elif A[i][j] == A[i][k] + A[k][j] and j != k and i != k and i < j:
                # 最短経路(仮)から直行ルートをなくす
                B[i][j] = 0

# 削減された最短経路の全長
sm = 0
for i in range(N):
    for j in range(i+1, N):
        sm += B[i][j]
print(sm)

Submission status: Accepted

Solution code:
N = int(input())
A = [list(map(int, input().split())) for i in range(N)]  # 最短距離らしきもの

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()

ans = sum([sum(a) for a in A])
for i in range(N):
    for j in range(N):
        for k in range(N):  # どの頂点を中継するかを、(i, j)について全探索
            if i == k or k == j:
                continue

            if A[i][j] == A[i][k] + A[k][j]:
                # A[i][j]となる辺はいらない
                ans -= A[i][j]
                break

print(ans // 2)

Submission status: Accepted

Solution code:
N = int(input())
graph = [[float("inf") for _ in range(N)] for _ in range(N)]
for i in range(N):
    a_list = list(map(int, input().split()))
    for j in range(N):
        if i == j:
            continue
        graph[i][j] = a_list[j]
import numpy as np
from scipy.sparse.csgraph import floyd_warshall
w_graph = floyd_warshall(graph, directed=False)
for i in range(N):
    w_graph[i][i] = float("inf")
result = 0
for i in range(N):
     w_graph[i][i] = float("inf")
for i in range(N):
    for j in range(i):
        if w_graph[i][j] != graph[i][j]:
            print(-1)
            exit()
        if w_graph[i][j] < np.min(w_graph[i] + w_graph[j]):
            result += w_graph[i][j]
print(int(result))

Submission status: Accepted

Solution code:
def warshall_floyd(graph):
    num_v = len(graph)

    for k in range(num_v):
        for i in range(num_v):
            for j in range(num_v):
                if graph[i][j] > graph[i][k] + graph[k][j]:
                    graph[i][j] = graph[i][k] + graph[k][j]
    return graph

N = int(input())
graph = [[float("inf") for _ in range(N)] for _ in range(N)]
for i in range(N):
    a_list = list(map(int, input().split()))
    for j in range(N):
        if i == j:
            continue
        graph[i][j] = a_list[j]
# import copy
# a_list = copy.deepcopy(graph)
import numpy as np
from scipy.sparse.csgraph import floyd_warshall
w_graph = floyd_warshall(graph, directed=False)
result = 0
for i in range(N):
     w_graph[i][i] = float("inf")
for i in range(N):
    for j in range(i):
        if i == j:
            continue
        if w_graph[i][j] != graph[i][j]:
            print(-1)
            exit()
        if w_graph[i][j] < np.min(w_graph[i] + w_graph[j]):
            result += w_graph[i][j]
print(int(result))

Submission status: Accepted

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

from scipy.sparse.csgraph import floyd_warshall as fw
import numpy as np
a = fw(A)
ans = 0
for i in range(N):
    a[i][i] = np.inf
for i in range(N):
    for j in range(i):
        if A[i][j]!=a[i][j]:
            print(-1)
            exit()
        else:
            if a[i][j] < np.min(a[i]+a[j]):
                ans += a[i][j]
print(int(ans))

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

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

n = ni()
g = np.zeros((n,n))
for i in range(n):
    g[i,:] = np.array(list(li()))
    
    
dist = floyd_warshall(g, directed=False)

consis = True
for i in range(n):
    for j in range(n):
        if g[i,j] != dist[i,j]:
            consis = False
            break
        
if not consis:
    print(-1)
    
else:
    total = 0
    INF = float("inf")
    
    for i in range(n):
        dist[i,i] = INF
        
    for i in range(n):
        for j in range(i+1,n):
            via_k = np.min(dist[i] + dist[j])
            
            if via_k > dist[i,j]:
                total += dist[i,j]
                
    print(int(total))

Submission status: Accepted

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

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

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 src[i][j] == src[i][k] + src[k][j]:
                break
        else:
            ans += src[i][j]
print(ans)

Submission status: Accepted

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

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

for i in range(N-1):
    for j in range(i+1,N):
        use = True
        for k in range(N):
            if k==i or k==j: continue
            if src[i][j] == src[i][k] + src[k][j]:
                use = False
                break
        if use:
            ans += src[i][j]
print(ans)

Submission status: Accepted

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

ans = 0
for k in range(N):
    for i in range(N):
        for j in range(N):
            if src[i][j] > src[i][k] + src[k][j]:
                print(-1)
                exit()
            src[i][j] = min(src[i][j], src[i][k] + src[k][j])

for i in range(N-1):
    for j in range(i+1,N):
        use = True
        for k in range(N):
            if k==i or k==j: continue
            if src[i][j] == src[i][k] + src[k][j]:
                use = False
                break
        if use:
            ans += src[i][j]
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
from scipy.sparse.csgraph import floyd_warshall
INF = 10**9

n = int(input())
a = np.array([list(map(int, input().split())) for _ in range(n)])
a_opt = floyd_warshall(a)
# for i in range(n): print(a[i], a_opt[i])

for i in range(n):
    a[i][i] = INF
    
ans = 0
for i in range(n):
    for j in range(i+1, n):
        if a_opt[i][j] < a[i][j]:
            print(-1)
            exit()
        else:
            d = a[i][j]
            if d < np.min(a[i]+a[j]):
                ans += d
                
            # Straight solution, but TLE in python
            # for k in range(n):
            #     if k in [i, j]:
            #         continue
            #     elif a[i][k]+a[k][j] == d:
            #         d = 0
            # ans += d
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import numpy as np
n=int(input())
l=[np.array(input().split(), dtype=np.int64) for _ in [0]*n]
l+=np.diag([10**10]*n)

v=0
for i in range(n-1):
  for j,d1 in enumerate(l[i][i+1:]):
    d2=np.min(l[i]+l[j+i+1])
    if d1>=d2:
      if d1>d2:
        print(-1)
        exit()
    else:
      v+=d1
print(v)

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import floyd_warshall
import numpy as np
import sys
sdin = sys.stdin.readline

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


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

Submission status: Accepted

Solution code:
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
def Warshall_Floyd(edges,N):
  ans = 0
  for j in range(N):
    for i in range(N):
      flag = 0
      for k in range(N):
        if edges[i][j]> edges[i][k]+edges[k][j]:
          print(-1)
          exit()
        if (edges[i][k] + edges[k][j] == edges[i][j] and i != k and k != j):
          flag = 1
      if flag == 0:
        ans += edges[i][j]
  return edges,ans
x,ans = Warshall_Floyd(a,n)
print(ans//2)

Submission status: Accepted

Solution code:
from sys import exit
n = input()
arr = []
for i in range(n):
	t = map(int,raw_input().split())
	arr.append(t)
ans = 0
for i in range(n):
	for j in range(n):
		flag = False
		for k in range(n):
			if k == j or k == i:
				continue
			elif arr[i][k]+arr[k][j] < arr[i][j]:
				print "-1"
				exit(0)
			elif arr[i][k]+arr[k][j] == arr[i][j]:
				flag = True
				continue
		if flag == False:
			ans += arr[i][j]
print ans//2

Submission status: Accepted

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

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

if np.any(A != floyd_warshall(A)):
    print(-1)
else:
    ans = 0
    A += np.diag([float('inf')] * N)
    for i in range(N):
        for j in range(i + 1, N):
            if np.min(A[i] + A[j]) != A[i, j]:
                ans += int(A[i, j])
    print(ans)