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 time
#import copy
from collections import deque, Counter, defaultdict
#from fractions import gcd
#import bisect
import heapq
import time

start = time.time()
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
inf = 10**18
MOD = 1000000007
ri = lambda : int(input())
rs = lambda : input().strip()
rl = lambda : list(map(int, input().split()))

n = ri()
a=[rl() for _ in range(n)]
c=[[0]*n for _ in range(n)]



for k in range(n):
    for i in range(n):
        for j in range(n):
            if k==i or k==j or i==j:
                continue
            if a[i][j]==a[i][k]+a[k][j]:
                c[i][j]+=1
            if a[i][j]>a[i][k]+a[k][j]:
                print(-1)
                sys.exit()
            a[i][j]=min(a[i][j], a[i][k]+a[k][j])
ans=0
for i in range(n):
    for j in range(i+1,n):
        if c[i][j]==0:
            ans+=a[i][j]
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=[list(map(int,input().split()))for _ in range(n)]
b=[[j for j in i]for i in a]
c=[n*[1]for _ in range(n)]
for k in range(n):
  for i in range(n):
    for j in range(n):
      b[i][j]=min(b[i][j],b[i][k]+b[k][j])
      if a[i][j]==a[i][k]+a[k][j]:
        if i!=j and i!=k and j!=k:
          c[i][j]=0
if a!=b:exit(print(-1))
ans=0
for i in range(n):
  for j in range(i):
    if c[i][j]:ans+=a[i][j]
print(ans)

Submission status: Accepted

Solution code:
import sys


def main():
    N = int(input())
    A = [list(map(int, input().split())) for i in range(N)]
    ans = 0
    for i in range(N):
        for j in range(i+1, N):
            dij = A[i][j]
            res = True
            for k in range(N):
                if k in [i, j]:
                    continue
                dikj = A[i][k] + A[k][j]
                if dij > dikj:
                    print(-1)
                    sys.exit()
                elif dij == dikj:
                    res = False
            if res:
                ans += dij
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from heapq import heappop, heappush
input = sys.stdin.readline

def main():
    n = int(input())
    a = [list(map(int,input().split())) for _ in range(n)]
    g = [[] for _ in range(n)]
    for i in range(n-1):
        for j in range(i+1,n):
            g[i].append((j,a[i][j]))
            g[j].append((i,a[i][j]))
    ans = 0
    for i in range(n):
        ans += sum(a[i])
    ans //= 2
    w = []
    for i in range(n):
        que = []
        d = [10**15 for _ in range(n)]
        d[i] = 0
        heappush( que,(0,i) )
        while que:
            p =  heappop(que)
            v = p[1]
            if d[v] < p[0]:
                continue
            for k in range(len(g[v])):
                edge = g[v][k]
                if d[edge[0]] > d[v] + edge[1]:
                    d[edge[0]] = d[v] + edge[1]
                    heappush( que,(d[edge[0]] , edge[0]) )
        w.append(d)
    for i in range(n-1):
        for j in range(i+1,n):
            if w[i][j] < a[i][j]:
                print(-1)
                return
            flag = 0
            for k in range(n):
                if i == k or j == k:
                    continue
                if w[i][k] + w[k][j] == w[i][j]:
                    flag = 1
            if flag:
                ans -= w[i][j]
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 998244353

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def main():
    N = int(input())
    A = read_lists(N)
    
    res = 0
    for i in range(N):
        for j in range(i + 1, N):
            if i == j:
                continue

            for k in range(N):
                if k in (i, j):
                    continue

                if A[i][j] == A[i][k] + A[k][j]:
                    break

                if A[i][j] > A[i][k] + A[k][j]:
                    print(-1)
                    return
            else:
                res += A[i][j]
    
    print(res)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n=int(input())
a=[]
for _ in range(n):
	a.append(list(map(int,input().split())))
from copy import deepcopy
b=deepcopy(a)
for i in range(n):
	for j in range(n):
		for k in range(n):
			b[j][k]=min(b[j][i]+b[i][k],b[j][k])
if a!=b:
	print(-1)
	exit()
ans=0
for i in range(n):
	b[i][i]=10**18
for i in range(n):
	for j in range(n):
		f=1
		for k in range(n):
			if b[i][j]>=b[i][k]+b[k][j]:
				f=0
				break
		if f:
			ans+=b[i][j]
print(ans//2)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def main():
    n = int(input())
    a = [list(map(int, input().split())) for _ in range(n)]
    #print(a)

    for k in range(n-1,-1,-1):
        for i in range(n-1,-1,-1):
            for j in range(n-1,-1,-1):            
                #print(k,i,j,a)
                if (i==j or k==i or k==j):
                    continue
                if (a[i][k]!=-1 and a[k][j]!=-1 and a[i][j] == a[i][k]+a[k][j]):
                    a[i][j] = -1
                elif (a[i][k]!=-1 and a[k][j]!=-1 and a[i][j] > a[i][k]+a[k][j]):
                    print(-1)
                    exit()
            
    #print(a)

    ans = 0
    for i in range(0,n-1):
        for j in range(i,n):
            if (a[i][j]!=-1):
                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):
  for j in range(i+1, N):
    dij = A[i][j]
    res = True
    for k in range(N):
      if k in [i, j]:
        continue
      dikj = A[i][k] + A[k][j]
      if dij > dikj:
        print(-1)
        quit()
      elif dij == dikj:
        res = False
    if res:
      ans += dij

print(ans)

Submission status: Accepted

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

import sys
# import time
# import math
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)



def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1             # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())


    def warshall_floyd(adj_mat_with_weight):
        '''
        Warshall-Floyd 法 (O(V^3), 1 sec だと v~500 とかが限界)
        全点対間の最短経路を三次元 DP で求める
            - 定式化
            - dp[k+1][i][j] を 0...k, i, j なる頂点を使用できる時の i~j 最短距離とする (k+1=0 の時は e(i,j))
            - dp[k+1][i][j] = min(dp[k][i][j], dp[k][i][k+1]+dp[k][k+1][j])
            - 最後に必要なのは dp[V][i][j] 。上の漸化式をみるに 2 次元 array があれば使いまわしてメモリ節約できる。
        Args:
            adj_mat_with_weight (list): 重みを記録した隣接行列 (非接続頂点は inf)
        Returns:
            dp (list): dp[i][j] を見れば全頂点を使用可能な時の i j 最短距離がわかる。最後に dp[i][i] が負になっていたら負サイクルが存在するということ
        '''
        V = len(adj_mat_with_weight)
        # テーブル初期化
        dp = deepcopy(adj_mat_with_weight)
        for i in range(V):
            dp[i][i] = 0
        # 漸化式を解く
        for k in range(1, V+1):
            for i in range(V):
                for j in range(V):
                    # new 2d-table # old 2d-table
                    dp[i][j] = min(dp[i][j], dp[i][k-1]+dp[k-1][j])
        return dp

    def check_possible_structure(dp, adj_mat):
        n = len(adj_mat)
        for i in range(n):
            for j in range(i+1, n):
                if dp[i][j] < adj_mat[i][j]:
                    return False
        return True

    def calc_minimum_street(dp, adj_mat):
        n = len(adj_mat)
        total_dist = 0
        for i in range(n):
            for j in range(i+1, n):
                total_dist += adj_mat[i][j]
        # 削除していく
        for i in range(n):
            for j in range(i+1, n):
                # (i, j) の距離について
                dist = adj_mat[i][j]
                for k in range(n):
                    if k != i and k != j and dp[i][k] + dp[k][j] == dist:
                        total_dist -= dist
                        break
        return total_dist
    
    
    n = ii()
    adj_mat = [lmi() for _ in range(n)]
    dp = warshall_floyd(adj_mat)

    if not check_possible_structure(dp, adj_mat):
        print(-1)
    else:
        print(calc_minimum_street(dp, adj_mat))


if __name__ == "__main__":
    main()

Submission status: Accepted

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


def main():
    N = int(input())
    matr = np.array([tuple(map(int, input().split())) for _ in range(N)], dtype=np.int64)
    way = floyd_warshall(matr).astype(int)
    if np.any(way < matr):
        print(-1)
        exit()

    ans = 0
    for a, b in itertools.combinations(range(N), 2):
        eq = (matr[a, b] == (matr[a] + matr[:, b]))
        eq[a] = eq[b] = False
        if not np.any(eq):
            ans += matr[a, b]
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
INF = 10**12
A = []

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

def check():
    c = [[0]*N for i in range(N)]
    ans = 0
    for i in range(N):
        for j in range(N):
            flag = True
            for k in range(N):    
                if k == i or k == j:
                    continue
                if A[i][j] == A[i][k] + A[k][j]:
                    flag = False
                    break
                elif A[i][j] > A[i][k] + A[k][j]:
                    return -1
            if flag:
                c[i][j] = A[i][j]
    for i in range(N):
        ans += sum(c[i])
    return ans // 2

print(check())

Submission status: Accepted

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


def main():
    INF = 10**12
    N = int(input())
    A = [list(map(int, input().split(' '))) for _ in range(N)]
    wf = floyd_warshall(A)
    for i in range(N):
        A[i][i] = INF
        wf[i][i] = INF
    ans = 0
    for i in range(N):
        for j in range(N):
            if A[i][j] != wf[i][j]:
                print(-1)
                return
            if wf[i][j] < np.min(wf[i] + wf[j]):
                ans += wf[i][j]
    print(int(ans // 2))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

def main():
    N = int(input())
    A = [None for _ in range(N)]
    INF = 10**12
    for i in range(N):
        A[i] = list(map(int, input().split()))

    adj = [[0]*N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            flag = True
            for k in range(N):
                if k == i or k == j:
                    continue
                if A[i][j] > A[i][k] + A[k][j]:
                    print(-1)
                    exit()
                elif A[i][j] == A[i][k] + A[k][j]:
                    flag = False
                    break
            if flag:
                adj[i][j] = A[i][j]
    ans = 0
    for i in range(N):
        ans += sum(adj[i])
    print(ans//2)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

dp = copy.deepcopy(graph)
for k in range(N):
  for i in range(N):
    for j in range(N):
      dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j])

res = 0

for i in range(N):
  for j in range(N):
    if dp[i][j] < graph[i][j]:
      print(-1)
      exit()
    elif dp[i][j] == graph[i][j]:
      flg = True
      for k in range(N):
        if k!=i and k!=j and dp[i][j] == dp[i][k]+dp[k][j]:
          flg = False
      if flg:
        res += dp[i][j]

print(res//2)

Submission status: Accepted

Solution code:







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

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


"""
存在する道路の長さの和が最小となるようなもの
→ Aについて、i<->jを結ぶ最短の辺（間に他のノードがない辺）だけ足し合わせる
"""
ans = 0
for i in range(N):
    for j in range(i+1, N):
        has_other_edges = False
        for k in range(N):
            if i == k or j == k: continue
            if A[i][j] == A[i][k] + A[k][j]:
                has_other_edges = True

        if not has_other_edges:
            ans += A[i][j]



print(ans)

Submission status: Accepted

Solution code:
import heapq
import sys
N = int(input())

r = [[1]*N for _ in range(N)]
g = [[]*N for _ in range(N)]
all = 0
for i in range(N):
  temp = list(map(int,(input().split())))
  g[i] = temp
  all += sum(temp)
#print(g,all)

for k in range(N):
  for i in range(N):
    for j in range(N):
      if g[i][j] > g[i][k] + g[k][j]:
        print("-1")
        sys.exit()
      elif g[i][j] == g[i][k] + g[k][j] and i != j and j != k and k != i:
        r[i][j] = 0
ans = 0
for i in range(N):
  for j in range(N):
    ans += g[i][j]*r[i][j]

ans = ans//2
print(ans)

Submission status: Accepted

Solution code:
import copy

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

B = copy.deepcopy(A)
for i in range(N):
    for j in range(i, N):
        for k in range(N):
            if not (i != j and j != k and k != i):
                continue
            if A[i][j] > A[i][k] + A[k][j]:
                print(-1)
                exit()
            if A[i][j] == A[i][k] + A[k][j]:
                B[i][j] = 0

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

print(ans)

Submission status: Accepted

Solution code:
# ABC074D
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")



def main():
    n = int(input())
    d = [None]*n

    for i in range(n):
        d[i] = list(map(int, input().split()))
    ans = 0
    for i in range(n):
        for j in range(i+1, n):
            for k in range(n):
                if k in (i,j):
                    continue
                if (d[i][j]>d[i][k]+d[j][k]) or (d[i][k]>d[i][j]+d[j][k]) or (d[k][j]>d[i][k]+d[j][i]):
                    print(-1)
                    return
                if d[i][j]==d[i][k]+d[j][k]:
                    break
            else:
                ans += d[i][j]
    print(ans)
main()

Submission status: Accepted

Solution code:
import numpy as np

N = int(input())
A = np.array([input().split() for _ in range(N)], dtype=np.int64).reshape(N,N)

INF = 10**15
np.fill_diagonal(A, INF)

ans = 0
for i in range(N-1):
    for j in range(i+1,N):
        detour = np.min(A[i]+A[j])
        if detour > A[i][j]:
            ans+=A[i][j]
        elif detour < A[i][j]:
            print(-1)
            exit()
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n = inp()
a = [inpl() for _ in range(n)]
res = 0
fin = set()
for k in range(n):
    for i in range(n):
        for j in range(n):
            d = a[i][k] + a[k][j]
            if a[i][j] > d:
                print(-1)
                quit()
            if a[i][j] == d and i != k and j != k:
                fin.add((i,j))

for i in range(n):
    for j in range(i+1,n):
        if (i,j) in fin: continue
        res += a[i][j]
print(res)

Submission status: Accepted

Solution code:
N = int(input())

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

def warshall_floyd(d):
    global SUM
    ans = 0
    aroad = set()
    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]:
                    return -1
                if d[i][j]==d[i][k]+d[k][j] and not (i==k or k==j):
                    aroad.add((min(i, j), max(i, j)))
    for i, j in list(aroad):
        ans -= d[i][j]
    return SUM+ans

SUM = 0
for i in range(N):
    As = list(map(int, input().split()))
    SUM += sum(As)
    for j in range(N):
        d[i][j] = As[j] 
SUM //= 2
print(warshall_floyd(d))

Submission status: Accepted

Solution code:
N = int(input())

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

ans = sum(sum(a) for a in A) // 2
removeable = set()

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

for i in range(N):
    for j in range(i + 1, N):
        if (i, j) in removeable:
            ans -= A[i][j]

print(ans)

Submission status: Accepted

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

ans = 0
def warshall_floyd(d):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if i == k or j == k:
                    continue
                elif d[i][j] > d[i][k] + d[k][j]:
                    return -1
                elif d[i][j] == d[i][k] + d[k][j]:
                    blist[i][j] = 0
    return sum([sum(l) for l in blist])//2

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


ans = warshall_floyd(alist)
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)


def road():
    N = int(input())
    A = tuple(tuple(map(int, input().split())) for _ in range(N))

    res = 0
    for s in range(N - 1):
        for t in range(s + 1, N):
            # s-t間に辺を張るかを決める
            dist = A[s][t]
            is_connect = True
            for m in range(N):
                if m in [s, t]:
                    continue
                d = A[s][m] + A[m][t]
                if d < dist:
                    return -1
                elif d == dist:
                    is_connect = False
            if is_connect:
                res += dist
    return res


if __name__ == "__main__":
    print(road())

Submission status: Accepted

Solution code:
n=int(input())

mat=[[0 for i in range(n)] for j in range(n)]
data=[[0 for i in range(n)] for j in range(n)]
for _ in range(n):
    x=list(map(int,input().split()))
    for j in range(n):
        mat[_][j]=x[j]
        data[_][j]=x[j]
def warshall_floyd(d):
    #d[i][j]=i番目の頂点からj番目の頂点までの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

newmat=warshall_floyd(mat)
if newmat==data:
    ans=0
    for i in range(n):
        for j in range(i+1,n):
            ans+=data[i][j]*int(all(data[i][j]<data[i][k]+data[k][j] for k in range(i))&all(data[i][j]<data[i][k]+data[k][j] for k in range(i+1,j))&all(data[i][j]<data[i][k]+data[k][j] for k in range(j+1,n)))     
    print(ans)      
else:
    print(-1)

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


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(i + 1, N):
            if any(A[i][j] > A[i][k] + A[k][j] for k in range(N) if k != i and k != j):
                print(-1)
                return
            if all(A[i][j] < A[i][k] + A[k][j] for k in range(N) if k != i and k != j):
                ans += A[i][j]

    print(ans)

    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


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

    ans = 0
    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)
                    return

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

    print(ans)

    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import copy

def warshall_floyd(d,n):
    D = copy.deepcopy(d) 
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if i == k  or k == j:
                    continue
                if d[i][k] + d[k][j] < d[i][j]:
                    return -1 
                elif d[i][k] + d[k][j] == d[i][j]:
                    D[i][j] = 0
    ans = sum([sum(i) for i in D])
    assert not (ans % 2)
    return ans // 2
  
n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
ans = warshall_floyd(a,n)
print(ans)

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
import bisect
from collections import deque
from fractions import gcd
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def bit_count(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#############
# Main Code #
#############

N = inputI()
A = inputILL(N)

class WarshallFloyd():
  def __init__(self, N):
    self.N = N
    self.d = [[float("inf") for i in range(N)] for i in range(N)]

  def add(self, u, v, c, directed=False):
    if directed is False:
      self.d[u][v] = c
      self.d[v][u] = c
    else:
      self.d[u][v] = c

  def WarshallFloyd_search(self):
    for k in range(self.N):
      for i in range(self.N):
        for j in range(self.N):
          self.d[i][j] = min(self.d[i][j], self.d[i][k] + self.d[k][j])
    hasNegativeCycle = False
    for i in range(self.N):
      if self.d[i][i] < 0:
        hasNegativeCycle = True
        break
    for i in range(self.N):
      self.d[i][i] = 0
    return hasNegativeCycle, self.d
  
graph = WarshallFloyd(N)
for i in range(N):
  for j in range(N):
    graph.add(i,j,A[i][j])
    
hasNegativeCycle, d = graph.WarshallFloyd_search()

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

ans = 0
for i in range(N):
  for j in range(i+1,N):
    flag = 1
    for k in range(N):
      if k!=i and k!=j:
        if d[i][k]+d[k][j] <= A[i][j]:
          flag = 0
    if flag:
      ans += A[i][j]
print(ans)

Submission status: Accepted

Solution code:

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

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


max_cost = 0
for i in range(N):
    for j in range(i + 1, N):

        flag = True
        for k in range(N):
            if k == i or k == j:
                continue
            if nums[i][j] == nums[i][k] + nums[k][j]:
                flag = False
                break

        if flag:
            max_cost += nums[i][j]


print(max_cost)

Submission status: Accepted

Solution code:


N = int(input())
A = [list(map(int, input().split())) for _ 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 = 0
for i in range(N):
    for j in range(i+1,N):

        f = True
        for k in range(N):
            if k == i or k == j:
                continue
            if A[i][j] == A[i][k] + A[k][j]:
                f = False
                break
        
        if f:
            #辺i->jを足す
            ans += A[i][j]


print(ans)