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:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def warshall_floyd(N: int, graph: list) -> list:
    """ ワーシャルフロイド(頂点数, 隣接行列(0-indexed)) """
    from copy import deepcopy

    res = deepcopy(graph)
    for i in range(N):
        # 始点 = 終点、は予め距離0にしておく
        res[i][i] = 0
    # 全頂点の最短距離
    for k in range(N):
        for i in range(N):
            for j in range(N):
                res[i][j] = min(res[i][j], res[i][k] + res[k][j])
    # 負の閉路(いくらでもコストを減らせてしまう場所)がないかチェックする
    for i in range(N):
        if res[i][i] < 0:
            return []
    return res

def build_grid(H, W, intv, _type, space=True, padding=False):
    # 入力がスペース区切りかどうか
    if space:
        _input = lambda: input().split()
    else:
        _input = lambda: input()
    _list = lambda: list(map(_type, _input()))
    # 余白の有無
    if padding:
        offset = 1
    else:
        offset = 0
    grid = list2d(H+offset*2, W+offset*2, intv)
    for i in range(offset, H+offset):
        row = _list()
        for j in range(offset, W+offset):
            grid[i][j] = row[j-offset]
    return grid

def check1(A, B):
    for i in range(N):
        for j in range(N):
            # 1つでも最短経路が更新されていればNG
            if A[i][j] != B[i][j]:
                return False
    return True

def check2(G):
    res = 0
    S = set()
    for k in range(N):
        for i in range(N):
            for j in range(N):
                # 3頂点が異なってかつ、経由のが近い場合は直接の辺は不要
                if i != j and j != k and k != i \
                        and G[i][k] + G[k][j] == G[i][j]:
                    if (i, j) not in S:
                        S.add((i, j))
                        res += G[i][j]
    return res

N = INT()
G = build_grid(N, N, 0, int)

# 妥当性の確認
wf = warshall_floyd(N, G)
if not check1(G, wf):
    print(-1)
    exit()

# 全体から不要な辺のコストを引く
total = 0
for i in range(N):
    for j in range(N):
        total += wf[i][j]
ans = (total - check2(wf)) // 2
print(ans)

Submission status: Accepted

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

INF = 10 ** 15
B = [[INF for _ in range(N)] 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], A[i][k] + A[k][j])
#print("B:", B)

for i in range(N):
  if A[i] != B[i]:
    print(-1)
    exit()
    
C = [[1 for _ in range(N)] for _ in range(N)]
for i in range(N):
  for j in range(i + 1, N):
    for k in range(N):
      if i != k and j != k:
        if A[i][k] + A[k][j] == A[i][j]:
          C[i][j] = 0
#print("C:", C)   

answer = 0
for i in range(N):
  for j in range(i + 1, N):
    answer += C[i][j] * A[i][j]
print(answer)

Submission status: Accepted

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

'''
Aが最短距離を表す、というのはSnukeの推測でしかない。
なので、Aを、A[v, u]が辺の重みを表しているgraphとして捉え、floyd_warshallで実際に最短距離を求め、Bとする。

B[v, u] < A[v, u]が存在したらAが最短距離を表すという推測は間違っていたことになる。
もしB[v, u] == B[v, w] + B[w, u](ただし w ≠ v, w ≠ u)となるようなwが存在したら、
Aのgraphでedge(v, u)はなくても良いことになるので、A[v, u] = A[u, v] = 0として辺を消す。(仮に辺を消しても、shortest_dist(v, u)には影響しないため)

最後に残った辺々だけをつなげてできるグラフの合計の辺の重みが答えとなる
'''

n = int(sys.stdin.readline().rstrip())
A = np.array(sys.stdin.read().split(), dtype=np.int64).reshape(n, n)

def main():
    B = floyd_warshall(csr_matrix(A), directed=False).astype(np.float64)
    if np.any(B < A):
        return -1
        
    np.fill_diagonal(B, np.inf)
    
    for v in range(n-1):
        for u in range(v+1, n):
            detours = B[v] + B[u]
            if np.any(detours == B[v, u]):
                A[v, u] = A[u, v] = 0

    return np.sum(A) // 2

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

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

n = int(sys.stdin.readline().rstrip())
A = np.array(sys.stdin.read().split(), dtype=np.int64).reshape(n, n)

def main():
    B = floyd_warshall(csr_matrix(A), directed=False).astype(np.float64)
    if np.any(B < A):
        return -1
        
    np.fill_diagonal(B, np.inf)
    
    for v in range(n-1):
        for u in range(v+1, n):
            detours = B[v] + B[u]
            if np.any(detours == B[v, u]):
                A[v, u] = A[u, v] = 0
                
    return np.sum(A) // 2

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

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

n = int(sys.stdin.readline().rstrip())
A = np.array(sys.stdin.read().split(), dtype=np.float64).reshape(n, n)

def main():
    B = floyd_warshall(csr_matrix(A), directed=False)
    if np.any(B < A):
        return -1
        
    np.fill_diagonal(B, np.inf)
    
    total_length = 0
    for v in range(n-1):
        for u in range(v+1, n):
            detours = B[v] + B[u]
            if np.all(detours > B[v, u]):
                total_length += B[v, u]

    return int(total_length)

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

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

n = int(sys.stdin.readline().rstrip())
A = np.array(sys.stdin.read().split(), dtype=np.float64).reshape(n, n)

def main():
    B = floyd_warshall(csr_matrix(A), directed=False).astype(np.int64)
    if np.any(B < A):
        return -1
        
    np.fill_diagonal(A, np.inf)
    
    total_length = 0
    for v in range(n-1):
        for u in range(v+1, n):
            detours = A[v] + A[u]
            if np.all(detours > B[v, u]):
                total_length += B[v, u]

    return total_length

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

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

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

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

print (ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [[int(i) for i in input().split()] for _ in range(N)]
roads = [[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[j][k]:
                print(-1)
                exit()
            if i == j:
                roads[i][j] = False
            if i != k and j != k and A[i][j] == A[i][k]+A[j][k]:
                roads[i][j] = False


ans = 0
for i in range(N):
    for j in range(i+1, N):
        if roads[i][j] is True:
            ans += A[i][j]
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

N = I()
A = []
for i in range(N):
    A.append(III())

l = 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
            now = A[i][k] + A[k][j]
            if now < A[i][j]:
                print(-1)
                exit()
            if now == A[i][j]:
                flag = False
        if flag:
            l += A[i][j]

print(l)

Submission status: Accepted

Solution code:
import sys
import copy

def solve(N: int, A: "List[List[int]]"):
    B = copy.deepcopy(A)
    for start_node in range(0,N):
        for end_node in range(start_node+1,N):
            min_dist = 10**12
            for transit in range(N):
                if transit == start_node or transit == end_node:
                    continue
                min_dist = min(min_dist,A[start_node][transit]+A[transit][end_node])

            ## impossible
            if A[start_node][end_node] > min_dist:
                print(-1)
                return 
            elif A[start_node][end_node] == min_dist:
                B[start_node][end_node] = 0
            else:
                continue
    answer =0
    for i in range(N):
        for j in range(i+1,N):
            answer+=B[i][j]
    print(answer)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [[int(next(tokens)) for _ in range(N)] for _ in range(N)]  # type: "List[List[int]]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = [[int(a) for a in input().split()] for _ in range(N)]
    B = [[A[i][j] for j in range(N)] for i in range(N)]
    C = [[A[i][j] for j in range(N)] for i in range(N)]
    for k in range(N):
        for i in range(N):
            for j in range(N):
                t = B[i][k] + B[k][j]
                if t < B[i][j]:
                    return -1
                if B[i][k] and B[k][j] and t == B[i][j]:
                    C[i][j] = 0
    return sum([sum([C[i][j] for j in range(i)]) for i in range(N)])
print(main())

Submission status: Accepted

Solution code:
n=int(input())
a=[list(map(int,input().split())) for _ in [0]*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)
                exit()
ans=0
for i in range(n):
    for j in range(i+1,n):
        for k in range(n):
            if i != k and j != k and a[i][j] == a[i][k] + a[k][j]:
                break
        else:
            ans += a[i][j]
    
print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

n=int(input())
aa=LLI(n)

def main():
    ans=sum(sum(ar) for ar in aa)//2
    fin=set()
    for w in range(n):
        aaw=aa[w]
        for u in range(n):
            if u==w:continue
            aau=aa[u]
            for v in range(u):
                if v==w:continue
                d=aau[w]+aaw[v]
                if d<aau[v]:
                    print(-1)
                    exit()
                if d==aau[v] and (u,v) not in fin:
                    ans-=d
                    fin.add((u,v))
    print(ans)

main()

Submission status: Accepted

Solution code:
import sys
inf = float('inf')
N = int(input())
d = [list(map(int, input().split())) for _ in range(N)]
for i in range(N):
    d[i][i] = 0
ans=0
for a in range(N):
    for b in range(N):
        flag = True
        for i in range(N):
            if i == a or i == b:
                continue
            if d[a][i]+d[i][b]<d[a][b]:
                print(-1)
                sys.exit()
            if d[a][i]+d[i][b]==d[a][b]:
                flag = False
                break
        if flag:
            ans+=d[a][b]
            
print(ans//2)

Submission status: Accepted

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

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

ans = 0
for i in range(N):
    for j in range(N):
        if all([A[i][j] < A[i][k]+A[k][j] or k==i or k==j for k in range(N)]):
            ans += A[i][j]
            
print(ans//2)

Submission status: Accepted

Solution code:
def main():
    n=int(input())
    if n==1:
        print(0)
        return 0
    import numpy as np
    p=np.array([np.array(list(map(int,input().split()))) for _ in [0]*n])
    if n==2:
        print(p[0][1])
        return 0
    import scipy.sparse.csgraph as sp
    ans=0
    d=np.full((n,n),0)
    for i in range(n):
        for j in range(i+1,n):
            b=p[i][j]
            if b!=np.sort(p[i]+p[j])[2]:
                d[i][j],d[j][i]=b,b
                ans+=b
    s=sp.shortest_path(d)
    if (s==p).all():
        print(ans)
    else:
        print(-1)
main()

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, atan2
from operator import mul
from functools import reduce
sys.setrecursionlimit(10 ** 9)

INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


n = I()
G = []
for _ in range(n):
    G += [LI()]


ret = 0
for i in range(n):
    for j in range(i + 1, n):
        flag = 1
        for k in range(n):
            if i == k or j == k:
                continue
            if G[i][j] > G[i][k] + G[k][j]:
                print(-1)
                exit()
            elif G[i][j] == G[i][k] + G[k][j]:
                flag = 0
        if flag:
            ret += G[i][j]


print(ret)

Submission status: Accepted

Solution code:
import heapq
from collections import deque

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

def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**9+1] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d


Road = [[] for _ in range(N)]
h = []
for i in range(N):
    for j in range(i+1, N):
        heapq.heappush(h, (A[i][j], i, j))
        
m = h[0][0]
D = [[10**9+1]*N for _ in range(N)]
ans = 0
while h:
    t = heapq.heappop(h)
    cost = t[0]
    i = t[1]
    j = t[2]
    if cost < 2*m:
        Road[i].append((cost, j))
        Road[j].append((cost, i))
        D[i][j] = cost
        D[j][i] = cost
    elif D[i][j] > cost:
        D[i] = dijkstra_heap(i, Road, N)
        if D[i][j] > cost:
            Road[i].append((cost, j))
            Road[j].append((cost, i))
            D[i][j] = cost
            D[j][i] = cost
    if D[i][j] < cost:
        ans = -1
        break
            
if ans == 0:
    for i in range(N):
        for t in Road[i]:
            ans += t[0]
            
    ans //= 2
        
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(list(map(int,input().split()))for i in range(N))
B = [A[i][:] for i in range(N)]
ans = 0
for i in range(N):
    for j in range(i+1,N):
        flag = True
        for k in range(N):
            if not i != k != j:
                continue
            if A[i][j] == A[i][k] + A[j][k]:
                flag = False
            elif A[i][j] > A[i][k] + A[j][k]:
                print(-1)
                exit()
        if flag:
            ans += A[i][j]
print(ans)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def size(self, x):
        if self.parents[x] < 0:
            return -self.parents[x]
        else:
            self.parents[x] = self.size(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

n = int(input())
A = [list(map(int,input().split())) for i in range(n)]
M = [[j for j in i] for i in A]

for k in range(n):
    for i in range(n):
        for j in range(n):
            M[i][j] = min(M[i][j], M[i][k] + M[k][j])

b = 0
if A != M:
    print(-1)
else:
    ans = 0
    for i in range(n):
        for j in range(i+1, n):
            b = 0
            for k in range(n):
                if k != i and k != j and M[i][j] == M[i][k] + M[k][j]:
                    b = 1
                    break
            if b == 0:
                ans += A[i][j]
    print(ans)

Submission status: Accepted

Solution code:
import sys
n=int(input())
a=[list(map(int,input().split())) for i in range(n)]
inf=float("inf")
data=[[inf]*n for i in range(n)]
ans=0
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]:
                break
            elif a[i][j]>a[i][k]+a[k][j]:
                print(-1)
                sys.exit()
        else:
            data[i][j]=a[i][j]
            ans+=a[i][j]
print(ans//2)

Submission status: Accepted

Solution code:
import copy
N = int(input())
A = [list(map(int, input().split())) for i in range(N)]
B = copy.deepcopy(A)
table = [[True]*N for i in range(N)]
ans = 0
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        for k in range(N):
            if k == i or k == j:
                continue
            else:
                if B[i][k] == B[i][j]+B[j][k]:
                    table[i][k] = False
                B[i][k] = min(B[i][k], B[i][j]+B[j][k])


if A == B:
    for i in range(N):
        for j in range(N):
            if table[i][j]:
                ans += B[i][j]
    print(ans//2)
else:
    print(-1)

Submission status: Accepted

Solution code:
import sys
from copy import deepcopy as dc
input = sys.stdin.buffer.readline
N = int(input())
d = [list(map(int, input().split())) for _ in range(N)]
d2 = dc(d)
for k in range(N):
  for i in range(N):
    for j in range(N):
      d2[i][j] = min(d2[i][k] + d2[k][j], d2[i][j])
f = 0
for i in range(N):
  for j in range(N):
    if d[i][j] != d2[i][j]:
      f = 1
if f:
  print(-1)
else:
  res = 0
  for i in range(N):
    for j in range(N):
      x = 1
      for k in range(N):
        if k != i and k != j:
          if d[i][j] == d[i][k] + d[k][j]: x = 0
      res += x * d[i][j]
          
  print(res // 2)

Submission status: Accepted

Solution code:
def union(parent,size,a,b):
    x=find(parent,a)
    y=find(parent,b)
    if x!=y:
        if size[x]<size[y]:
            parent[x]=y 
            size[y]=size[x]+size[y]
        else:
            parent[y]=x 
            size[x]=size[x]+size[y]
    return parent,size 
def find(parent, a):
    while a != parent[a]:
            parent[a]=parent[parent[a]]
            a=parent[a]
    return a
n=int(input())
mat=[]
for i in range(n):
    mat.append([int(i) for i in input().split()])
mat1=[[mat[i][j] for j in range(n)]for i in range(n)]
for k in range(n):
    for i in range(n):
        for j in range(n):
            mat1[i][j]=min(mat1[i][j],mat1[i][k]+mat1[k][j])
#print(mat,mat1)
if mat1!=mat:
    print(-1)
    exit()
need=[[1 for j in range(n)]for i in range(n)]
for k in range(n):
    for i in range(n):
        for j in range(i):
            if k==j or k==i:
                continue 
            if mat[i][k]+mat[k][j]==mat[i][j]:
                need[i][j]=need[j][i]=0 
ans=0 
for i in range(n):
    for j in range(n):
        ans+=need[i][j]*mat[i][j]
print(ans//2)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
from bisect import bisect_left, bisect_right
import random
from itertools import permutations, accumulate, combinations
import sys
import string



INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7




def warshall_floyd(graph):
    #d[i][j]: iからjへの最短距離
    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]:
                    return 1




n = I()
graph = [[INF] * n for _ in range(n)]
#d[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(n):
    edges = LI()
    for j in range(n):
        graph[i][j] = edges[j]
        graph[j][i] = edges[j]



if warshall_floyd(graph):
    print(-1)
else:
    ret = 0
    for i in range(n):
        for j in range(i + 1, n):
            if i == j:
                continue
            for k in range(n):
                if k != i and k != j and graph[i][k] + graph[k][j] == graph[i][j]:
                        break
            else:
                ret += graph[i][j]
    print(ret)

Submission status: Accepted

Solution code:
import copy

def Warshall_Floyd(edges,N):
  for k in range(N):
    for i in range(N):
      for j in range(N):
        edges[i][j]=min(edges[i][j],edges[i][k]+edges[k][j])
  return edges

n=int(input())
arr=[list(map(int,input().split())) for _ in range(n)]
g=[[float('inf')]*n for _ in range(n)]
for i in range(n):
  for j in range(n):
    g[i][j]=arr[i][j]
d=Warshall_Floyd(copy.deepcopy(g),n)
ans=0
for a in range(n):
  for b in range(n):
    if a>=b:
      continue
    w=g[a][b]
    if d[a][b]<w:
      print(-1)
      exit()
    else:
      tmp=10**10
      for k in range(n):
        if k==a or k==b:
          continue
        tmp=min(tmp,d[a][k]+d[k][b])
      if w==tmp:
        continue
      else:
        ans+=w
else:
  print(ans)

Submission status: Accepted

Solution code:
import copy

def Warshall_Floyd(edges,N):
  for k in range(N):
    for i in range(N):
      for j in range(N):
        edges[i][j]=min(edges[i][j],edges[i][k]+edges[k][j])
  return edges

n=int(input())
arr=[list(map(int,input().split())) for _ in range(n)]
g=[[float('inf')]*n for _ in range(n)]
for i in range(n):
  for j in range(n):
    g[i][j]=arr[i][j]
d=Warshall_Floyd(copy.deepcopy(g),n)
ans=0
for a in range(n):
  for b in range(n):
    if a>=b:
      continue
    w=g[a][b]
    if d[a][b]<w:
      print(-1)
      exit()
    else:
      tmp=10**10
      for k in range(n):
        if k==a or k==b:
          continue
        tmp=min(tmp,d[a][k]+d[k][b])
      if w==tmp:
        continue
      else:
        ans+=w
else:
  print(ans)

Submission status: Accepted

Solution code:
def Warshall_Floyd(edges,N):
  for k in range(N):
    for i in range(N):
      for j in range(N):
        edges[i][j]=min(edges[i][j],edges[i][k]+edges[k][j])
  return edges

n=int(input())
arr=[list(map(int,input().split())) for _ in range(n)]
edge=[]
for i in range(n):
  for j in range(n):
    if i>=j:
      continue
    edge.append((arr[i][j],(i,j)))
edge=sorted(edge,key=lambda x:x[0])
g=[[float('inf')]*n for _ in range(n)]
for i in range(n):
  for j in range(n):
    g[i][j]=arr[i][j]
d=Warshall_Floyd(g,n)
ans=0
for w,(a,b) in edge:
  if d[a][b]<w:
    print(-1)
    break
  else:
    tmp=10**10
    for k in range(n):
      if k==a or k==b:
        continue
      tmp=min(tmp,d[a][k]+d[k][b])
    if w==tmp:
      continue
    else:
      ans+=w
else:
  print(ans)

Submission status: Accepted

Solution code:
n = int(input())
ary = [list(map(int,input().split())) for _ in range(n)]
ans = sum([sum(i) for i in ary])
for i in range(n):
    for j in range(n):
        for k in range(n):
            if j == k or i == k:continue
            if ary[i][j] > ary[i][k] + ary[k][j]:print(-1);exit()
            if ary[i][j] == ary[i][k] + ary[k][j]:
                ans -= ary[i][j]
                break
print(ans//2)

Submission status: Accepted

Solution code:
n = int(input())
ary = [list(map(int,input().split())) for _ in range(n)]
ans = sum([sum(i) for i in ary])
for i in range(n):
    for j in range(n):
        flag = 0
        for k in range(n):
            if j == k or i == k:continue
            if ary[i][j] > ary[i][k] + ary[k][j]:print(-1);exit()
            if ary[i][j] == ary[i][k] + ary[k][j]:
                flag = 1
        if flag:ans -= ary[i][j]
print(ans//2)

Submission status: Accepted

Solution code:
import sys

n = int(input())

a = []

for _ in range(n):
    A = list(map(int, input().split( )))
    a.append(A)

b = [[a[i][j] for j in range(n)] for i in range(n)]

#三角不等式(等号可)を満たしてなかったら無理
#満たしてた場合、どの迂回路とも真の不等号ならば保持

for k in range(n):
    for i in range(n):
        for j in range(n):
            if a[i][k] + a[k][j] < a[i][j]:
                print(-1)
                sys.exit()
            if i!=k and j!=k and a[i][k] + a[k][j] == a[i][j]:

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

print(ans//2)

Submission status: Accepted

Solution code:
n = int(input())
dp = [list(map(int,input().split())) for _ in range(n)]
ans = sum([sum(i) for i in dp])
for i in range(n):
    for j in range(n):
        if dp[i][j] == 0:continue
        a = 0
        for k in range(n):
            if dp[i][k] == 0:continue
            if j == k:continue
            if dp[i][k]+dp[k][j] < dp[i][j]:print(-1);exit()
            if dp[i][k] + dp[k][j] == dp[i][j]:
                a = 1
        if a == 1:ans -= dp[i][j]
print(ans//2)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = []
    dist = [[0 for _ in range(N)] for _ in range(N)]
    for i in range(N):
        Ai = list(map(int, input().split()))
        A.append(Ai)
        for j in range(N):
            dist[i][j] = Ai[j]

    def wf(dist):
        need = [[1 for _ in range(N)] for _ in range(N)]
        for i in range(N):
            for j in range(N):
                for k in range(N):
                    if dist[i][j] > dist[i][k] + dist[k][j]:
                        print(-1)
                        exit()
                    elif dist[i][j] == dist[i][k] + dist[k][j]:
                        if i != k and j != k:
                            need[i][j] = 0
                            need[j][i] = 0
        return need

    need = wf(dist)
    ans = 0
    for i in range(N):
        for j in range(i+1, N):
            ans += need[i][j] * dist[i][j]
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

import copy

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

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

INF = int(1E17)
ok = True
ans = 0
for i in range(N-1):
    for j in range(i+1, N):
        if A[i][j] != B[i][j]:
            ok = False
        d = INF
        for k in range(N):
            if k == i or k == j:
                continue
            d = min(d, A[i][k] + A[k][j])
        if d > A[i][j]:
            ans += A[i][j]
                
if not ok:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
n=int(input())
d=[]

for i in range(n):
    tmp=[int(j) for j in input().split()]
    d.append(tmp)

ans=[[0]*n for i in range(n)]

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

for i in range(n):
    for j in range(i+1,n):
        for k in range(n):
            if i==k or j==k:
                continue
            if d[i][j]>d[i][k]+d[k][j]:
                print(-1)
                exit()
            elif d[i][j]==d[i][k]+d[k][j]:
                ans[i][j]=0
res=0
for i in range(n):
    res+=sum(ans[i])
print(res)