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:
# ABC074 D - Restoring Road Network
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()
"""
a[i][j]が、i,kを除く全てのkについて
a[i][j]<a[i][k]+a[k][j]なら
a[i][j]は最短経路となる。
"""
ans=0
for i in range(n):
    for j in range(i+1,n):
        # iとjの間に辺が存在する場合True
        flg=True
        for k in range(n):
            if i==k or j==k:
                continue
            if a[i][j]==a[i][k]+a[k][j]:
                flg=False
                break
        if flg:
            ans+=a[i][j]
print(ans)

Submission status: Accepted

Solution code:

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

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


"""
Aの要素について、全てに辺が貼られているような状態を考えて、
あるA[i][j]が、i,kを除く全てのkについて A[i][j] < A[i][k] + A[k][j]であれば、
A[i][j]は最短の経路であるといえる

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


        flag = True # i,jの間に辺があるか
        for k in range(N):
            if i == k or j == k:
                continue
            
            # i -> j 間に辺がない
            if A[i][j] == A[i][k] + A[k][j]:
                flag = False
                break
        if flag:
            ans += A[i][j]

        
print(ans)

Submission status: Accepted

Solution code:
from copy import deepcopy

def warshall_floyd(n,a):
    d = deepcopy(a)
    is_via = [[False] * n for _ in range(n)]
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if i == j:
                    continue
                # 経由する場合
                if (d[i][k] != 0 and d[k][j] != 0) and (d[i][j] == d[i][k] + d[k][j]):
                    is_via[i][j] = True
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    flag = a == d
    return flag, is_via

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

flag, is_via = warshall_floyd(N,A)

if not flag:
    print(-1)
    exit()

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

print(ans)

Submission status: Accepted

Solution code:
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):
        ans += A[i][j]

m = set()
for k in range(N):
    for i in range(N):
        if k==i: continue
        for j in range(i+1,N):
            if k==j: continue
            a = A[i][j]
            b = A[i][k] + A[k][j]
            if b == a: m.add((i,j))
            elif b < a:
                print(-1)
                exit()

for i,j in m:
    ans -= A[i][j]

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env pypy3
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    inf=10*20
    N=I()
    A=[[]for _ in range(N)]
    A2=[[1]*N for _ in range(N)]
    ans=0
    for i in range(N):
        A[i]=LI()
        ans+=sum(A[i])
        
    


        
    def warshall_floyd(d):
        #d[i][j]: iからjへの最短距離
        for k in range(N):
            for i in range(N):
                if k==i:
                    continue
                for j in range(N):
                    if j==i or j==k:
                        continue
                    dd=d[i][k] + d[k][j]
                    #d[i][j] = min(d[i][j],d[i][k] + d[k][j])
                    
                    if dd==d[i][j]:
                        A2[i][j]=0
                    elif dd<d[i][j]:
                        return -1
        return 1
    
    if warshall_floyd(A)==-1:
        ans=-2
    else:
        ans=0
        for i in range(N):
            for j in range(N):
                ans+=A[i][j]*A2[i][j]
        
        
    print(ans//2)
        
    

main()

Submission status: Accepted

Solution code:
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n = inn()
a = []
for i in range(n):
    a.append(inl())
c = [[True]*n for i in range(n)]
for i in range(n-2):
    for j in range(i+1,n-1):
        for k in range(j+1,n):
            if a[i][j] > a[i][k]+a[k][j] or \
               a[i][k] > a[i][j]+a[j][k] or \
               a[k][j] > a[k][i]+a[i][j]:
                print(-1)
                exit()
            elif a[i][j] == a[i][k]+a[k][j]:
                c[i][j] = False
            elif a[i][k] == a[i][j]+a[j][k]:
                c[i][k] = False
            elif a[k][j] == a[k][i]+a[i][j]:
                c[j][k] = False
sm = 0
for i in range(n-1):
    for j in range(i+1,n):
        if c[i][j]:
            sm += a[i][j]
print(sm)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    a = [[int(x) for x in input().split()] for _ in range(n)]

    for i in range(n):
        for j in range(n):
            for k in range(n):
                if a[i][j] > a[i][k] + a[k][j]:
                    print(-1)
                    return

    ret = 0
    for i in range(n):
        for j in range(i):
            for k in range(n):
                if k == i or k == j: continue
                if a[i][j] == a[i][k] + a[k][j]: break  # 辺ではない
            else:
                ret += a[i][j]

    print(ret)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    from heapq import heappush, heappop

    n = int(input())
    a = [[int(x) for x in input().split()] for _ in range(n)]

    for i in range(n):
        for j in range(n):
            if a[i][j] != min(a[i][k] + a[k][j] for k in range(n)):
                print(-1)
                return

    h = []
    for r, row in enumerate(a):
        for c, cell in enumerate(row):
            if r == c: break
            heappush(h, (cell, r, c))  # dist,r,c

    pathes = []
    while h:
        dist, r, c = heappop(h)

        is_path = True
        for k in range(n):
            if k == r or k == c: continue
            if dist >= a[r][k] + a[k][c]:
                is_path = False
                break

        if is_path:
            pathes.append(dist)

    print(sum(pathes))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())

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

Submission status: Accepted

Solution code:
n = int(input())
a = []
ans = 0
for i in range(n):
    k = list(map(int, input().split()))
    a.append(k)
flag = [[True for i in range(n)] for j in range(n)]
for i in range(n):
    for j in range(n):
        for k in range(n):
            if a[j][i] + a[i][k] < a[j][k]:
                print(-1)
                exit()
            elif a[j][i] + a[i][k] == a[j][k] and j != i and i != k:
                flag[j][k] = flag[k][j] = False
for i in range(n):
    for j in range(n):
        if flag[i][j]:
            ans += a[i][j]
print(ans//2)

Submission status: Accepted

Solution code:
n = int(input())
wf = []
for _ in range(n):
  wf.append(list(map(int,input().split())))
cnt = [[0 for _ in range(n)] for _ in range(n)]
for k in range(n):
  for i in range(n):
    for j in range(n):
      if wf[i][j] > wf[i][k] + wf[k][j]:
        print(-1)
        exit()
      elif wf[i][j] == wf[i][k] + wf[k][j]:
        cnt[i][j] += 1
#print(cnt)
ans = 0
for i in range(n):
  for j in range(n):
    if cnt[i][j] <= 2:
      ans += wf[i][j]
print(ans//2)

Submission status: Accepted

Solution code:
def examD():
    # https://juppy.hatenablog.com/entry/2019/02/18/ARC83_-D_Restoring_Road_Network-_Python_%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0_Atcoder
    def warshall_floyd(n, 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
    N = I()
    A = [LI() for _ in range(N)]
    Dist = [[0]*N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            a, b, r = i, j, A[i][j]
            Dist[a][b] = r
    D = warshall_floyd(N,Dist)
    ans = 0
    for i in range(N):
        for j in range(N):
            cur = D[i][j]
            if i==j:
                continue
            if cur<A[i][j]:
                print(-1)
                return
            if cur==A[i][j]:
                flag = True
                for k in range(N):
                    if k==i or k==j:
                        continue
                    if cur==D[i][k]+D[k][j]:
                        flag = False
                if flag:
                    ans += cur
    print(ans//2)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examD()

"""

"""

Submission status: Accepted

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

for k in range(n):
    for i in range(n):
        if i == k:
            continue
        for j in range(n):
            if j == i or j == k:
                continue

            if edges[i][j] > edges[i][k] + edges[k][j]:
                print(-1)
                exit()
            elif edges[i][j] == edges[i][k] + edges[k][j]:
                need_of_routes[i][j] = False

count = 0
for i in range(n):
    for j in range(n):
        if need_of_routes[i][j]:
            count += edges[i][j]

print(count//2)

Submission status: Accepted

Solution code:
N = int(input())
dic = [0]*N
dist = [[0]*N for i in range(N)]
for i in range(N):
  dic[i] = [int(c) for c in input().split()]
  for j in range(N):
    dist[i][j] = dic[i][j]
  dic[i][i] = float('inf')

ans = 0
for i in range(N):
  for j in range(i):
    d = min(a+b for a, b in zip(dic[i],dic[j]))
    if d<dic[i][j]:
      print(-1)
      exit()
    elif d>dic[i][j]:
      ans += dic[i][j]
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
dic = [0]*N
dist = [[float('inf')]*N for i in range(N)]
for i in range(N):
  dic[i] = [int(c) for c in input().split()]
  for j in range(N):
    dist[i][j] = dic[i][j]
ans = 0
log = []
for k in range(N):
  for i in range(N-1):
    for j in range(i+1,N):
      dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])
for i in range(N-1):
  for j in range(i+1,N):
    if dist[i][j]<dic[i][j]:
      print(-1)
      import sys
      sys.exit()
    flag = False
    for k in range(N):
      if k==i or k==j:
        continue
      if dist[i][j] == dist[i][k]+dist[k][j]:
        flag = True
    if flag:
      continue
    ans += dic[i][j]
print(ans)

Submission status: Accepted

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

def main():
    N = int(input())
    edge = [list(map(int,input().split())) for _ in range(N)]
    for i in range(N):
        edge[i][i] = 10**10
        
    ans = 0
    for i in range(N):
        for j in range(i):
            d = min(a+b for a,b in zip(edge[i],edge[j]))
            if edge[i][j] > d:
                print(-1)
                exit()
            elif edge[i][j] < d:
                ans += edge[i][j]

    print(ans)    

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
N = int(input())
cost = [[0]*N for i in range(N)]
dist = [[0]*N for i in range(N)]
log = defaultdict(int)
for i in range(N):
  inf = [int(c) for c in input().split()]
  for j in range(N):
    cost[i][j] = inf[j]
for i in range(N):
  for j in range(i+1,N):
    m = float('inf')
    for k in range(N):
      if cost[i][j]>=cost[i][k]+cost[k][j]:
        m = min(m,cost[i][k]+cost[k][j])
        if k != i and k!= j:
          log[(min(i,j),max(i,j))] = 1
    dist[i][j] = m
    dist[j][i] = m
ans = 0
for i in range(N):
  for j in range(i+1,N):
    flag = False
    if dist[i][j]<cost[i][j]:
      print(-1)
      flag = True
      break
    elif log[(i,j)]==0:
      ans += cost[i][j]
  if flag:
    break
else:
  print(ans)

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    # ワーシャルフロイド
    def warshall_floyd(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])
    
    N=I()
    A=LLIN(N)
    d=deepcopy(A)
    warshall_floyd(d, N)

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

    ans = 0
    for a,i,j in edge:
        if d[i][j]<a:
            print(-1)
            return
        need = True
        for k in range(N):
            if k in (i,j):
                continue
            if a==d[i][k]+d[k][j]:
                need = False
                break
        if need:
            ans += a
    print(ans)
        
if __name__ == '__main__':
    main()

Submission status: Accepted

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

n = int(readline())
lst1 = [list(map(int,readline().split())) for i in range(n)]

def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d
st = deepcopy(lst1)
st = warshall_floyd(st)
ans = 0
for i in range(n):
    for j in range(i+1,n):
        if lst1[i][j] > st[i][j]:
            print(-1)
            exit()
        elif lst1[i][j]==st[i][j]:
            #他に最短距離がある場合はcontinue
            res = [0]*n
            for k in range(n):
                res[k] += lst1[i][k] + lst1[j][k]
            res[i] = -1
            res[j] = -1
            if any([res[k]==lst1[i][j] for k in range(n)]):
                continue
            else:
                ans += lst1[i][j]
        else:
            ans += lst1[i][j]

print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
INF = 10 ** 9
A = np.array([lr() for _ in range(N)])
np.fill_diagonal(A, INF)
answer = 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]:
            answer += A[i, j]
        elif detour < A[i, j]:
            print(-1)
            exit()

print(answer)
# 38

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 = 0
for arr in dist:
  ans += sum(arr)

for i in range(n):
  for j in range(n):
    for k in range(n):
      if i != j and j != k and k != i:
        if dist[i][k]+dist[k][j] == dist[i][j] and dist[i][k] != 0 and dist[k][j] != 0:
          ans -= dist[i][j]
          break
        elif dist[i][k]+dist[k][j] < dist[i][j] and dist[i][k] != 0 and dist[k][j] != 0:
          print(-1)
          exit()
print(ans//2)

Submission status: Accepted

Solution code:
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
cnt = 0
for k in range(n):
  for i in range(n-1):
    for j in range(i+1,n):
      if a[i][j] > a[i][k] + a[k][j]:
        print(-1); exit(0)

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
      elif a[i][j] == a[i][k] + a[k][j]:
        cnt += a[i][j]
        break
tot = sum(sum(x) for x in a)//2
print(tot-cnt)

Submission status: Accepted

Solution code:
N = int(input())
A = [list(map(int,input().split())) for _ in range(N)]
cnt = 0
for i in range(N-1):
    for j in range(i+1,N):
        amin = 10**10
        for k in range(N):
            if k!=i and k!=j:
                amin = min(amin,A[i][k]+A[k][j])
        if A[i][j]>amin:
            cnt = -1
            break
        elif A[i][j]<amin:
            cnt += A[i][j]
    if cnt==-1:break
print(cnt)

Submission status: Accepted

Solution code:
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = np.array([lr() for i in range(N)])
INF = 10 ** 9
np.fill_diagonal(A, INF)
answer = 0
for i in range(N):
    for j in range(i+1, N):
        detour = np.min(A[i] + A[j])
        if A[i, j] < detour:
            # 最短距離としてこの道路は必要
            answer += A[i, j]
        elif A[i, j] > detour:
            print(-1)
            exit()

print(answer)
# 05 hint

Submission status: Accepted

Solution code:
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = np.array([lr() for i in range(N)])
INF = 10 ** 10
np.fill_diagonal(A, INF)
answer = 0
for i in range(N):
    for j in range(i+1, N):
        detour = np.min(A[i] + A[j])
        if A[i, j] < detour:
            # 最短距離としてこの道路は必要
            answer += A[i, j]
        elif A[i, j] > detour:
            print(-1)
            exit()

print(answer)
# 05 hint

Submission status: Accepted

Solution code:
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = np.array([lr() for i in range(N)])
INF = 10 ** 10
np.fill_diagonal(A, INF)
answer = 0
for i in range(N):
    for j in range(i+1, N):
        detour = np.min(A[i] + A[j])
        if A[i, j] < detour:
            # 最短距離としてこの道路は必要
            answer += A[i, j]
        elif A[i, j] > detour:
            print(-1)
            exit()

print(answer)
# 05 hint

Submission status: Accepted

Solution code:
import copy
loss=0
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
def warshall_floyd2(d):
    #d[i][j]: iからjへの最短距離
    ans=0
    for i in range(n):
        for j in range(n):
            flg=0
            for k in range(n):
                if i==j or j==k or k==i:
                    continue
                if d[i][j]==d[i][k] + d[k][j]:
                    flg=1
            if flg==0:
                ans+=d[i][j]
    #print(loss)
    return ans

n=int(input())
a=[list(map(int,input().split())) for _ in range(n)]
b=copy.deepcopy(a)
b=warshall_floyd(b)
#print(a)
#print(b)
flg=True
for i in range(n):
    for j in range(n):
        if a[i][j]!=b[i][j]:
            flg=False
            break
    else:
        continue
    break
if flg:
    ans=warshall_floyd2(b)
    print(ans//2)
else:
    print(-1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N = int(input())

matrix = [list(map(int, input().split(' '))) for _ in range(N)]
buf = [list(m) for m in matrix]

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

for i in range(N):
    for j in range(N):
        if buf[i][j] != matrix[i][j]:
            print(-1)
            exit()

is_used = [[True for _ in range(N)] for m in matrix]
for k in range(N):
    for i in range(N):
        for j in range(N):
            if k != i and k != j:
                if matrix[i][k] + matrix[k][j] == matrix[i][j]:
                    is_used[i][j] = False

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

# ans = (sum([sum(b) for b in matrix]) - diff) // 2
print(ans)

Submission status: Accepted

Solution code:
import copy

def warshal_floyd(d):
    # d[i][j] := iからjへの最短距離
    global 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])
    # "今現在求まっているiからjへの最短距離"と"今現在求まっているiからkへの最短距離 + 今現在求まっているkからjへの最短距離 の和"を比較する
    return d


N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
graph = copy.deepcopy(A)
# for a in A:
#     print(a)
# 余分な辺を消去する問題
A = warshal_floyd(A)
for i in range(N):
    for j in range(N):
        if A[i][j] != graph[i][j]:
            print(-1)
            exit()

# 最短経路であることは分かった
flag = [[True]*N for _ in range(N)]
for k in range(N):
    for i in range(N):
        for j in range(N):
            if graph[i][j] == graph[i][k] + graph[k][j] and i != k and k != j:
                flag[i][j] = False

ans = 0
for i in range(N):
    for j in range(i+1, N):
        if flag[i][j] == True:
            ans += graph[i][j]
print(int(ans))

Submission status: Accepted

Solution code:
import sys
from itertools import combinations
  
def solve():
    input = sys.stdin.readline
    N = int(input())
    A = dict()
    for i in range(N):
        A[i] = dict()
        for j, a in enumerate(list(map(int, input().split()))): A[i][j] = a

    length = 0
    possible = True
    for a, b in combinations(range(N), 2):
        Lab = A[a][b]
        for k in range(N):
            if k != a and k != b:
                if Lab < A[a][k] + A[k][b]: continue
                if Lab >  A[a][k] + A[k][b]: possible = False
                break
        else: length += Lab
        if possible: continue
        print(-1)
        break
    else: print(length)
    
    return 0
 
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import sys
from itertools import permutations, combinations
  
def solve():
    input = sys.stdin.readline
    N = int(input())
    A = dict()
    for i in range(N):
        A[i] = dict()
        ain = [int(j) for j in input().split()]
        for j in range(N): A[i][j] = ain[j]

    length = 0
    possible = True
    for a, b in combinations(range(N), 2):
        Lab = A[a][b]
        create_pass = True
        for k in range(N):
            if k != a and k != b:
                if Lab >  A[a][k] + A[k][b]:
                    possible = False
                    break
                elif Lab ==  A[a][k] + A[k][b]:
                    create_pass = False
                    break
        if create_pass: length += Lab
        if not possible:
            print(-1)
            break
    else: print(length)
    
    return 0
  
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import sys
from itertools import permutations, combinations
  
def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [[int(a) for a in input().split()] for _ in range(N)]

    length = 0
    possible = True
    for a, b in combinations(range(N), 2):
        Lab = A[a][b]
        for k in range(N):
            if k != a and k != b:
                if Lab >  A[a][k] + A[k][b]:
                    possible = False
                    break
                elif Lab ==  A[a][k] + A[k][b]:
                    break
        else: length += Lab
        if not possible:
            print(-1)
            break
    else: print(length)
    
    return 0
  
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import sys
from itertools import permutations, combinations
  
def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [[int(a) for a in input().split()] for _ in range(N)]

    length = 0
    possible = True
    for a in range(N):
        for b, l in enumerate(A[a]):
            for k in range(N):
                if k != a and k != b:
                    if l >  A[a][k] + A[k][b]:
                        possible = False
                        break
                    elif l ==  A[a][k] + A[k][b]:
                        break
            else: length += l
        if not possible:
            print(-1)
            break
    else: print(length // 2)
    
    return 0
  
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import sys
from itertools import permutations, combinations
  
def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [[int(a) for a in input().split()] for _ in range(N)]

    length = 0
    possible = True
    for a, b in combinations(range(N), 2):
        Lab = A[a][b]
        create_pass = True
        for k in range(N):
            if k != a and k != b:
                if Lab >  A[a][k] + A[k][b]:
                    possible = False
                    break
                elif Lab ==  A[a][k] + A[k][b]:
                    create_pass = False
                    break
        if create_pass: length += Lab
        if not possible:
            print(-1)
            break
    else: print(length)
    
    return 0
  
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import sys
import numpy as np

read = sys.stdin.read

N, *A = map(int, read().split())
A = np.array(A, np.int64).reshape(N, N)
'''
answer = 0
for i, j in product(range(N), repeat=2):
    if i < j:
        continue
    edge = A[i][j]
    for k in range(N):
        if i == k or j == k:
            continue

        tmp = A[i][k] + A[k][j]
        if tmp < edge:
            print(-1)
            exit()
        elif tmp == edge:
            break
    else:
        answer += edge
'''

useless = np.zeros_like(A)

for i in range(N):
    grid = A[i] + A[i, None].T
    if np.any(grid < A):
        print(-1)
        exit()
    grid[i] = np.inf
    grid[:, i] = np.inf

    useless |= (A == grid)

print(A[useless != 1].sum() // 2)