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: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import heapq
import math
import sys

class Dijkstra(object):
    def dijkstra(self, adj, start, goal=None):
        '''
        ダイクストラアルゴリズムによる最短経路を求めるメソッド
        入力
        adj: adj[i][j]の値が頂点iから頂点jまでの距離(頂点iから頂点jに枝がない場合，値はfloat('inf'))となるような2次元リスト(正方行列)
        start: 始点のID
        goal: オプション引数．終点のID
        出力
        goalを引数に持つ場合，startからgoalまでの最短経路を格納したリストを返す
        持たない場合は，startから各頂点までの最短距離を格納したリストを返す
        >>> d = Dijkstra()
        >>> d.dijkstra([[float('inf'), 2, 4, float('inf'), float('inf')], [2, float('inf'), 3, 5, float('inf')], [4, 3, float('inf'), 1, 4], [float('inf'), 5, 1, float('inf'), 3], [float('inf'), float('inf'), 4, 3, float('inf')]], 0)
        [0, 2, 4, 5, 8] # 例えば，始点0から頂点3までの最短距離は5となる
        >>> d.dijkstra([[float('inf'), 2, 4, float('inf'), float('inf')], [2, float('inf'), 3, 5, float('inf')], [4, 3, float('inf'), 1, 4], [float('inf'), 5, 1, float('inf'), 3], [float('inf'), float('inf'), 4, 3, float('inf')]], 0, goal=4)
        [0, 2, 4] # 頂点0から頂点4までの最短経路は0 -> 2 -> 4となる
        '''
        num = len(adj)          # グラフのノード数
        dist = [float('inf') for i in range(num)] # 始点から各頂点までの最短距離を格納する
        prev = [float('inf') for i in range(num)] # 最短経路における，その頂点の前の頂点のIDを格納する

        dist[start] = 0
        q = []                  # プライオリティキュー．各要素は，(startからある頂点vまでの仮の距離, 頂点vのID)からなるタプル
        heapq.heappush(q, (0, start)) # 始点をpush

        while len(q) != 0:
            prov_cost, src = heapq.heappop(q) # pop

            # プライオリティキューに格納されている最短距離が，現在計算できている最短距離より大きければ，distの更新をする必要はない
            if dist[src] < prov_cost:
                continue

            # 他の頂点の探索
            for dest in range(num):
                cost = adj[src][dest]
                if cost != float('inf') and dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost # distの更新
                    heapq.heappush(q, (dist[dest], dest)) # キューに新たな仮の距離の情報をpush
                    prev[dest] = src                      # 前の頂点を記録

        if goal is not None:
            return self.get_path(goal, prev)
        else:
            return dist

    def get_path(self, goal, prev):
        '''
        始点startから終点goalまでの最短経路を求める
        '''
        path = [goal]           # 最短経路
        dest = goal

        # 終点から最短経路を逆順に辿る
        while prev[dest] != float('inf'):
            path.append(prev[dest])
            dest = prev[dest]

        # 経路をreverseして出力
        return list(reversed(path))




N = int(input())

distances_dict = {}
distances = []
for i in range(N):
    tmp = input()
    As = [int(a) for a in tmp.split()]
    for j, a in enumerate(As):
        if i == j: continue
        distances_dict[(i, j)] = a
        distances_dict[(j, i)] = a
        distances.append([i, j, a])
distances = sorted(distances, key=lambda x: x[2])

adj = [[0.0 if i == j else float('inf') for i in range(N)] for j in range(N)]
sum_d = 0
dij = Dijkstra()
for i, j, d in distances:
    di = dij.dijkstra(adj, i)[j]
    if di == d:
        continue
    elif di > d:
        sum_d += d
        adj[i][j], adj[j][i] = d, d
    else:
        print(-1)
        sys.exit()
print(int(sum_d))

Submission status: Accepted

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

s=[]
for i in range(n):
  for j in range(i+1,n):
    s.append((a[i][j],i,j))
s.sort()

c=0
for i in s:
  mn=10**10
  for j in range(n):
    if i[1]==j or i[2]==j:
      continue
    mn=min(mn,a[i[1]][j]+a[i[2]][j])
  if mn>a[i[1]][i[2]]:
    c+=a[i[1]][i[2]]
  elif mn<a[i[1]][i[2]]:
    c=-1
    break
print(c)

Submission status: Accepted

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

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

Submission status: Accepted

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

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

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

for i in rem:
    ans -= a[i]

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

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

def check(n,a):
    ans = 0
    ok = 1
    for i in range(n):
        for j in range(i+1,n):
            for k in range(n):
                if k==i or k==j: continue
                if a[i][k] + a[j][k] < a[i][j]:
                    return -1
                elif a[i][k] + a[j][k] == a[i][j]:
                    break
            else:
                ans += a[i][j]
    return ans
            
print(check(n,a))

Submission status: Accepted

Solution code:
def WarshallFloyd(M):
    N = len(M)
    M = [m[:] for m in M]
    for k in range(N):
        for j in range(N):
            for i in range(N):
                M[i][j] = min(M[i][j], M[i][k] + M[k][j])
    return M

N, *A = map(int, open(0).read().split())
A = list(map(list, zip(*[iter(A)] * N)))

B = WarshallFloyd(A)

ans = 0
for i in range(N):
    for j in range(i + 1, N):
        if A[i][j] > B[i][j]:
            print(-1)
            quit()

        if A[i][j] == B[i][j] and all(B[i][j] != B[i][k] + B[k][j] for k in range(N) if k != i and k != j):
            ans += B[i][j]

print(ans)

Submission status: Accepted

Solution code:
#import numpy as np
import sys
input=sys.stdin.buffer.readline
n=int(input())
d=[list(map(int,input().split())) for _ in range(n) ]
#d=np.array(d,np.int64)
#do a floyd warshall and test if something improves 
for k in range(n):
    for i in range(n):
        for j in range(i+1,n):
            if d[i][k]+d[k][j]<d[i][j]:
                print(-1)
                exit()
ans=0
for i in range(n):
    for j in range(i+1,n):
        flag=True
        for k in range(n):
            if k!=i and k!=j and d[i][k]+d[k][j]==d[i][j]:
                flag=False
        if flag:
            ans+=d[i][j]
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import scipy.sparse.csgraph as csg
n=int(input())
g=np.array([list(map(int,input().split())) for _ in range(n)],dtype=np.uint32)
g2=csg.floyd_warshall(g,directed=False)
if np.any(g!=g2):
  print(-1)
else:
  g[g==0]=2*10**9
  t=0
  for i in range(n):
    for j in range(i+1,n):
      m=np.min(g[i]+g[j])
      if m>g[i,j]:
        t+=g[i,j]
  print(t)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
"""
ワーシャルフロイド風に全探索で-1を炙り出す

条件を満たすとき:
A→Bの経路 == A→C→Bの経路
ならA→Bを合計から引く？
残るのは隣り合ったやつだけ？？

完全グラフから不要物を取り除いていく
A→C→B == A→Bだった場合、AB間は絶対に不要

"""

import sys

N = int(input())

A = []
s = 0

for i in range(N):
    a = list(map(int,input().split()))
    s += sum(a)
    A.append(a)

s //= 2
#print (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)
                sys.exit()

for k in range(N):

    for i in range(N):
        for j in range(N):

            if i == j or i == k or j == k:
                continue
            if 0 in [ A[i][j] ,A[i][k] ,A[k][j]]:
                continue

            if A[i][j] == A[i][k] + A[k][j]:
                s -= A[i][j]
                A[i][j] = 0
                A[j][i] = 0
                #print (i,j,k)
                
#print (A)
print (s)

Submission status: Accepted

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def dijkstra(edge,st):
    # edge=[[(v_to,dist_to_v),...],[],...]
    # initialize: def: d=dist(st,i), prev=[previous vertex in minimum path], q[]
    n=len(edge)
    d=[(0 if st==i else inf,i) for i in range(n)]
    prev=[0]*n
    q=[i for i in d]
    heapify(q)
    
    # calc
    while q:
        dist,cur=heappop(q)
        for dst,dist in edge[cur]:
            alt=d[cur][0]+dist
            if alt<d[dst][0]:
                d[dst]=(alt,dst)
                prev[dst]=cur
                heappush(q,(alt,dst))
    return d,prev
    
show_flg=False
show_flg=True

ans=0
n=I()
d=[]
c=[[1]*n for i in range(n)]
for i in range(n):
    d.append(LI())


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

for i in range(n):
    for j in range(i+1,n):
        ans+=d[i][j]*c[i][j]

    
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:

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

Submission status: Accepted

Solution code:
#設定
import sys
input = sys.stdin.buffer.readline

#ライブラリインポート
from collections import defaultdict
import copy

INF = float("inf")

#入力受け取り
def getlist():
	return list(map(int, input().split()))

def build(d, n):
	cost = 0
	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] and k != i and k != j:
					d[i][j] = INF
				
	return d

def judge(d, n):
	for k in range(n):
		for i in range(n):
			for j in range(n):
				d[i][j] = min(d[i][j],d[i][k] + d[k][j])
	return d

#処理内容
def main():
	#受け取り
	N = int(input())
	d = []
	for i in range(N):
		g = getlist()
		d.append(g)

	#ワーシャルフロイド判定
	d2 = copy.deepcopy(d)
	d2 = judge(d2, N)

	if d != d2:
		print(-1)
	else:
		#構築
		X = build(d2, N)
		ans = 0
		for i in range(N):
			for j in range(N):
				if d2[i][j] != INF:
					ans += d2[i][j]
		print(ans // 2)


if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
def warshall_floyd(G):
    import copy
    ret = copy.deepcopy(G)
    for k in range(N):
        for i in range(N):
            for j in range(N):
                ret[i][j] = min(ret[i][j], ret[i][k] + ret[k][j])
    return ret


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

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

Submission status: Accepted

Solution code:
n=int(input())
table=[]
for i in range(n):
  table.append([int(_) for _ in input().split()])
T=[[1]*n for i in range(n)]
import itertools
chk,ans=True,0
for Com in itertools.combinations(range(n),3):
  a,b,c=Com[0],Com[1],Com[2]
  lab,lbc,lca=table[a][b],table[b][c],table[c][a]
  if lab>=lbc and lab>=lca:
    if lab>lbc+lca:
      chk=False
    elif lab==lbc+lca:
      T[a][b],T[b][a]=0,0
  elif lbc>=lab and lbc>=lca:
    if lbc>lab+lca:
      chk=False
    elif lbc==lab+lca:
      T[b][c],T[c][b]=0,0
  elif lca>=lab and lca>=lbc:
    if lca>lab+lbc:
      chk=False
    elif lca==lab+lbc:
      T[c][a],T[a][c]=0,0
for i in range(n):
  for j in range(i+1,n):
    if T[i][j]==1:
      ans+=table[i][j]
print(ans if chk==True else -1)

Submission status: Accepted

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

A=[]
for i in range(N):
    a=list(map(int,input().split()))
    A.append(a)
B=[[1 for i in range(N)]for i in range(N)]
#print(B)
C=copy.deepcopy(A)
for c in range(N):
    for a in range(N):
        for b in range(N):
            if a!=b and a!=c and b!=c:
                if C[a][b]==(C[a][c]+C[c][b]):
                    B[a][b]=0
                    B[b][a]=0
                A[a][b]=min(A[a][b],A[a][c]+A[c][b])
if C==A:
    ans=0
    for i in range(N):
        for j in range(N):
            if B[i][j]==1:
                ans+=A[i][j]
    print(ans//2)
else:
    print(-1)
#print(A)
#print(B)

Submission status: Accepted

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

d = [[0] * N 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()
            if A[i][j] == A[i][k] + A[k][j] and i != k and j != k:
                d[i][j] = 1

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

print(ans // 2)

Submission status: Accepted

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

# Aに対してワーシャルフロイドを適用した結果と比較して解を求める
ans = (
    -1 if any(
        A[u][v] > A[u][k] + A[k][v]
        for u in range(N)
        for v in range(u + 1, N)
        for k in range(N)
        if k != u and k != v
    ) else
    sum(sum(a) for a in A) // 2 - sum(
        A[u][v]
        for u in range(N)
        for v in range(u + 1, N)
        if any(
            A[u][v] == A[u][k] + A[k][v]
            for k in range(N)
            if k != u and k != v
        )
    )
)

# 出力
print(ans)

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

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

for i in range(N):
  for j in range(N):
    if i >=j :continue
    if all(A[i][j]<A[i][k]+A[k][j] for k in range(N) if k!=i and k!=j):
 
          if not bridge[i][j]:
            ans+=A[i][j] 
            bridge[i][j]=True
print(ans)

Submission status: Accepted

Solution code:
import copy
def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
 
n = int(input())
a = [[] for i in range(n)]
war = [[] for i in range(n)]
for i in range(n):
    a[i] = list(map(int,input().split()))
war = copy.deepcopy(a)
for i in range(n):
    if a[i][i] != 0:
        print(-1)
        exit()
 
warshall_floyd(war)


res = 0
for i in range(n):
    for j in range(n):
        if war[i][j] < a[i][j]:
            print(-1)
            exit()
        elif war[i][j] == a[i][j]:
            judge = 1
            for h in range(n):
                if h != i and h != j and war[i][h]+war[h][j] == war[i][j]:
                    judge = -1
            if judge == 1:
                res += war[i][j]
print(res//2)

Submission status: Accepted

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

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

print(ans)

Submission status: Accepted

Solution code:
def inpl(): return [int(i) for i in input().split()]
import sys
import numpy 
N = int(input())
A = numpy.array([inpl() 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):
        mindis = numpy.min(A[i] + A[j])
        if mindis > A[i][j]:
            ans += A[i][j]
            continue
        if mindis < A[i][j]:
            print(-1)
            sys.exit()
print(ans)

Submission status: Accepted

Solution code:
def inpl(): return [int(i) for i in input().split()]
import sys
import numpy 
N = int(input())
A = numpy.asarray([inpl() 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):
        mindis = numpy.min([A[i] + A[j]])
        if mindis > A[i][j]:
            ans += A[i][j]
            continue
        if mindis < A[i][j]:
            print(-1)
            sys.exit()

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
N=int(input())
dist=[[0.0 for _ in range(N)] for _ in range(N)]

for i in range(N):
    for j,x in enumerate(map(int,input().split())):
        dist[i][j]=float(x)
dist = np.array(dist)
for i in range(N):
    dist[i,i] = float('inf')
ans=0
for i in range(N):
    for j in range(i+1,N):
        min_=min(dist[i]+dist[j])
        if min_<dist[i,j]:
            ans=-1
            break
        elif min_>dist[i,j]:
            ans+=dist[i,j]
    if ans <0:
        break
print(int(ans))

Submission status: Accepted

Solution code:
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import *
from bisect import *

def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]

N = read()
A = []
for _ in range(N):
  A.append(reads())

necc = [[True] * N for _ in range(N)]

def fail():
  print(-1); exit()

for i, j, k in combinations(range(N), 3):
  if A[i][j] + A[j][k] < A[i][k] or A[i][j] + A[i][k] < A[j][k] or A[i][k] + A[j][k] < A[i][j]:
    fail()
  if A[i][j] + A[j][k] == A[i][k]:
    necc[i][k] = False
  if A[i][j] + A[i][k] == A[j][k]:
    necc[j][k] = False
  if A[i][k] + A[j][k] == A[i][j]:
    necc[i][j] = False

ans = sum(A[i][j] for i, j in combinations(range(N), 2) if necc[i][j])
print(ans)

Submission status: Accepted

Solution code:
import sys
import copy

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

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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
def inpl(): return tuple(map(int, input().split()))
from itertools import product, combinations

def main():
    N = int(input())
    adj = [inpl() for _ in range(N)]
    need = [[True]*N for _ in range(N)]
    ok = True
    res = 0
    for k, i, j in product(range(N), repeat=3):
        if adj[i][j] < adj[i][k] + adj[k][j]:
            continue
        elif i == k or j == k:
            continue
        elif adj[i][j] == adj[i][k] + adj[k][j]:
            need[i][j] = False
            need[j][i] = False
        else:
            ok = False
    if ok:
        for i, j in combinations(range(N), 2):
            if need[i][j]:
                res += adj[i][j]
        print(res)
    else:
        print(-1)

main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from itertools import combinations
 
def inpl(): return list(map(int, input().split()))
 
N = int(input())
res = 0
exist = True
A = []
 
for _ in range(N):
    A.append(inpl())
 
for i, j in combinations(range(N), 2):
    vervose = False
 
    if not exist:
        break
 
    for k in range(N):
        if i == k or j == k:
            pass
        else:
            if A[i][j] < A[i][k] + A[k][j]:
                pass
            elif A[i][j] == A[i][k] + A[k][j]:
                vervose = True
            else:
                exist = False
                break
    if vervose:
        pass
    else:
        res += A[i][j]
 
if exist:
    print(res)
else:
    print(-1)

Submission status: Accepted

Solution code:
def solve(n, tbl):
    ans = 0
    for i, row_i in enumerate(tbl):
        for j in range(i + 1, n):
            row_j = tbl[j]
            ij = row_i[j]
            mind = min((ik + kj for ik, kj in zip(row_i, row_j) if ik and kj), default=float('inf'))
            if ij > mind:
                return -1
            if ij < mind:
                ans += ij
    return ans


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

Submission status: Accepted

Solution code:
import numpy as np
import scipy.sparse.csgraph as csg

if __name__ == '__main__':
    N = int(input())
    A = [list(map(int, input().split())) for i in range(N)]

    G = np.asarray(A, dtype=np.uint32)
    G2 = csg.floyd_warshall(G, directed=False)
    # print(G)
    # print(G2)
    # print(G == G2)
    if np.any(G != G2):
        print(-1)
        exit()
    ans = 0
    G[G == 0] = 1
    for i in range(N):
        for j in range(i + 1, N):
            n = np.min(G[i] + G[j])
            if n > G[i, j]:
                ans += G[i, j]

    print(ans)

Submission status: Accepted

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

INF = 10 ** 9 + 1
for i in range(N):
    A[i][i] = INF

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

        if A[i][j] > d:
            print('-1')
            exit()
        elif A[i][j] < d:
            ans += A[i][j]

print(ans)

Submission status: Accepted

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

answer = 0
for i in xrange(N):
  Ai = A[i]
  for j in xrange(i):
    Aij = Ai[j]
    L = min(map(sum, zip(Ai, A[j])))
    if Aij < L:
      answer += Aij
    else:
      if Aij > L:
        print -1
        exit()
print answer

Submission status: Accepted

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

answer = 0
for i in range(N):
  Ai = A[i]
  for j in range(i):
    Aij = Ai[j]
    L = min(map(sum, zip(Ai, A[j])))
    if Aij < L:
      answer += Aij
    else:
      if Aij > L:
        print -1
        exit()
print answer

Submission status: Accepted

Solution code:

N = int(input())

import numpy as np

G = np.array([list(map(int,input().split())) for i in range(N)], dtype=np.uint32)

import scipy.sparse.csgraph as csg

G2 = csg.floyd_warshall(G,directed=False)

if np.any(G != G2):
  print(-1)
else:
  G[G==0] = 2*10**9
  t = 0
  for i in range(N):
    for j in range(i+1,N):
      n = np.min(G[i]+G[j])
      if n > G[i,j]:
        t += G[i,j]


  print(t)

Submission status: Accepted

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

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

Submission status: Accepted

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

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

    print(total//2)


if __name__ == '__main__':
    main()