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, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()

def warshall_floyd(v_count: int, matrix: list) -> list:
    for i in range(v_count):
        for j, c2 in enumerate(row[i] for row in matrix):
            for k, (c1, c3) in enumerate(zip(matrix[j], matrix[i])):
                if c1 > c2+c3:
                    matrix[j][k] = c2+c3
    return matrix

A = [LIST() for _ in range(N)]
dist_matrix = warshall_floyd(N, deepcopy(A))

ans = 0
for i, j in combinations(range(N), 2):
    if A[i][j] != dist_matrix[i][j]:
        print(-1)
        break
    for k in range(N):
        if i == k or j == k:
            continue
        if A[i][k] + A[k][j] == A[i][j]:
            break
    else:
        ans += A[i][j]
else:
    print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
from heapq import heappop, heappush
from itertools import combinations

class Graph:
    def __init__(self, n, edges, weight=False):
        self.n = n
        self.adj = [[] for _ in range(n)]
        self.degree = [0] * n
        self.weight = defaultdict(lambda: 10**18)
        if weight:
            for u, v, weight in edges:
                self.adj[u].append(v)
                self.adj[v].append(u)
                self.degree[v] += 1
                self.weight[(u, v)] = weight
                self.weight[(v, u)] = weight
        else:
            for u, v in edges:
                self.adj[u].append(v)
                self.adj[v].append(u)
                self.degree[v] += 1
                self.weight[(u, v)] = 1
                self.weight[(v, u)] = 1

    def dijkstra(self, start, goal=None):  # O((n+m)log(n))
        INF = 10**18
        dist = [INF] * self.n
        dist[start] = 0
        heap = [(0, start)]  # (dist, v)
        sp_prev = [None] * self.n  # previous node in shortest path (sp)
        while heap:
            dist_v, v = heappop(heap)
            if dist[v] < dist_v:
                continue
            for adj in self.adj[v]:
                edge_weight = self.weight[(v, adj)]
                if dist[v] + edge_weight < dist[adj]:
                    dist[adj] = dist[v] + edge_weight
                    sp_prev[adj] = v
                    heappush(heap, (dist[adj], adj))

        if goal is not None:
            if dist[goal] == INF:
                return dist, []
            else:
                path = [goal]
                v = goal
                while v != start:
                    v = sp_prev[v]
                    path.append(v)
                path.reverse()
                return dist, path
        else:
            return dist, sp_prev

    def warshall_floyd(self):  # O(n^3)
        # dist[u][v]: uからvへの最短距離
        INF = 10**18
        dist = [[INF] * self.n for _ in range(self.n)]
        for u in range(self.n):
            dist[u][u] = 0
            for v in self.adj[u]:
                dist[u][v] = self.weight[(u, v)]
        for k in range(self.n):
            for u in range(self.n):
                for v in range(self.n):
                    dist[u][v] = min(dist[u][v], dist[u][k] + dist[k][v])
        return dist

# ---------------------- #

n = int(input())
A = [tuple(int(x) for x in input().split()) for _ in range(n)]
dist = []
for i in range(n):
    for j in range(n):
        if i < j:
            dist.append((i, j, A[i][j]))

G = Graph(n, dist, weight=True)
wf = G.warshall_floyd()

for i in range(n):
    for j in range(n):
        if A[i][j] != wf[i][j]:
            print(-1)
            exit()

ans = 0
for i, j in combinations(range(n), 2):
    for k in range(n):
        if i == k or j == k:
            continue
        if A[i][j] == A[i][k] + A[k][j]:
            break
    else:
        ans += A[i][j]

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))


def main():
    n = ii()

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

    for i in range(n):
        a.append(li())


    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
                
                if i==k or k == j:
                    continue
                if a[i][j] == a[i][k] + a[k][j]:
                    direct[i][j] = False
    
    ans = 0
    for i in range(n):
        for j in range(n):
            if direct[i][j]:
                ans += a[i][j]
    print(ans//2)


main()

Submission status: Accepted

Solution code:
N = int(input())
from copy import copy,deepcopy
dist = [list(map(int,input().split())) for _ in range(N)]
dist2 = deepcopy(dist)
seen = [[False]*N for _ in range(N)]
for k in range(N):
    for i in range(N):
        for j in range(N):
            if (i!=k and k!=j) and dist[i][j]>=dist[i][k]+dist[k][j]:
                dist[i][j]= dist[i][k]+dist[k][j]
ans = 0
for i in range(N):
    for j in range(N):
        flag = True
        if i ==j: continue
        for k in range(N):
            if i==k or j ==k: continue
            if dist2[i][j]>dist[i][k]+dist[k][j]:
                print(-1);exit()
            if dist2[i][j]==dist[i][k]+dist[k][j]:
                flag = False
                break
        if flag:
            ans += dist[i][j]
print(ans//2)

Submission status: Accepted

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

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

ans //= 2
print(ans)

Submission status: Accepted

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


for k in range(N):
    for i in range(N):
        for j in range(N):
            # costs[i][j]は最短経路でないといけない。
            if costs[i][j] > costs[i][k] + costs[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 costs[i][j] == costs[i][k] + costs[k][j]:
                flag = False
                break
        if flag:
            max_cost += costs[i][j]
print(max_cost)

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()
INF=10**12
D=[[INF]*N for i in range(N)]
for i in range(N):
  D[i][i]=0
X=[]
for i in range(N):
  for j in range(N):
    if i==j:
      continue
    X.append([A[i][j],i,j])
P=0
X.sort()
for i in range(len(X)):
  for j in range(N):
    if X[i][0]==D[X[i][1]][j]+D[j][X[i][2]] and D[j][X[i][2]]!=0 and D[X[i][1]][j]!=0:
      break
    if j==N-1:
      P+=X[i][0]
  D[X[i][1]][X[i][2]]=X[i][0]
  D[X[i][2]][X[i][1]]=X[i][0]
print(P//2)

Submission status: Accepted

Solution code:
N = int(input())
A = [list(map(int,input().split())) for _ in range(N)]
B = [A[i][:] for i in range(N)]
C = [A[i][:] for i in range(N)]
for k in range(N):
    for i in range(N):
        for j in range(N):
            if k == i or k == j: continue
            if B[i][k]+B[k][j] <= B[i][j]:
                A[i][j] = -1
                B[i][j] = B[i][k]+B[k][j]

ans = 0
for i in range(N):
    for j in range(N):
        if B[i][j] != C[i][j]:
            print(-1)
            exit()
        if A[i][j] != -1:
            ans += A[i][j]
            A[i][j] = -1
            A[j][i] = -1
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# hello worldと表示する
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial,sqrt
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

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

##############################
n=I() #n:頂点数　w:辺の数

d = [[float("inf")]*n for i in range(n)]
lis=[LI() for i in range(n)]
#d[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(n):
    for j in range(i+1,n):
        d[i][j]=lis[i][j]
        d[j][i]=lis[i][j]
for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０
warshall_floyd(d)
sm=0
for i in range(n):
    sm+=sum(lis[i])
#インデックスで与えられていることに注意
#ソース　https://juppy.hatenablog.com/entry/2018/11/01/蟻本_python_全点対最短経路法（ワーシャルフロイド法
count=0
for i in range(n-1):
    for j in range(i+1,n):
        if d[i][j]!=lis[i][j]:
            print(-1)
            sys.exit()
        if d[i][j]==lis[i][j]:
            for k in range(n):
                if i!=k!=j and d[i][k]+d[k][j]==d[i][j]:
                    count+=lis[i][j]
                    #print(i,j,k)
                    break
print(sm//2-count)

Submission status: Accepted

Solution code:
n=int(input())
dis=[list(map(int,input().split())) for _ in range(n)]
c=[[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
  for j in range(n):
    c[i][j]=min(dis[i][k]+dis[k][j] for k in range(n))
for i in range(n):
  for j in range(n):
    if c[i][j]!=dis[i][j]:
      print(-1)
      exit()
for i in range(n):
  for j in range(n):
    for k in range(n):
      if i==k or j==k:continue
      if dis[i][j]==dis[i][k]+dis[k][j]:c[i][j]=0
print(sum(sum(c[i]) for i in range(n))//2)

Submission status: Accepted

Solution code:
import copy
import sys

INF = 2**120

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

ans = sum([sum(d[i]) for i in range(n)])

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

for k in range(n):
    for i in range(n):
        for j in range(n):
            if d[i][j] > d[i][k]+d[k][j]:
                print('-1')
                sys.exit()
            if d[i][j] == d[i][k]+d[k][j] and i != k and j != k:
                minus[i][j] = 1

for i in range(n):
    for j in range(n):
        if minus[i][j]:
            ans -= d[i][j]

print(ans//2)

Submission status: Accepted

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

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall

n = int(readline())
f = []
A = []
chk = []
for i in range(n):
  ar = list(map(int,readline().split()))
  f.append(ar)
  for j,ai in enumerate(ar):
    if i == j:
      continue
    A.append((i,j,ai))
  
INF = 10**9+1
g = [[INF] * n for _ in range(n)]
for a,b,c in A:
    g[a][b] = c
    g[b][a] = c

g = csr_matrix(g)
d = floyd_warshall(csgraph=g)

t = f == d
if t.all():
  ans = 0
  for i in range(n):
    d[i,i] = INF

  for i in range(n):
    for j in range(i+1,n):
      opt = np.min(d[i] + d[j])
      if opt > d[i,j]:
        ans += d[i,j]
        
  print(int(ans))
else:
  print(-1)

Submission status: Accepted

Solution code:
N = int(input())

INF = 10 ** 9 + 7
G = [[int(_) for _ in input().split()] for _ in range(N)]
G2 = [G[_].copy() for _ in range(N)]

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

            if G2[i][j] < G[i][j]:
                print(-1)
                exit()
ans = 0
for i in range(N - 1):
    for j in range(i + 1, N):
        if i == j: continue
        elif G2[i][j] == G[i][j]:
            v = G2[i][j]
            for k in range(N):
                if i == j or i == k or j == k: continue
                if G2[i][k] + G2[k][j] == G2[i][j]:
                    v = 0
                    break
            ans += v
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

INF = 10 ** 9 + 7
G = [[int(_) for _ in input().split()] for _ in range(N)]
G2 = [G[_].copy() for _ in range(N)]

for k in range(N):
    for i in range(N):
        for j in range(N):
            G2[i][j] = min(G2[i][j], G2[i][k] + G2[k][j])
ans = 0
for i in range(N - 1):
    for j in range(i + 1, N):
        if i == j: continue
        if G2[i][j] < G[i][j]:
            print(-1)
            exit()
        elif G2[i][j] == G[i][j]:
            v = G2[i][j]
            for k in range(N):
                if i == j or i == k or j == k: continue
                if G2[i][k] + G2[k][j] == G2[i][j]:
                    v = 0
                    break
            ans += v
print(ans)

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


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

N = getN()
query = [getList() for i in range(N)]
query_before = copy.deepcopy(query)

def warshall_floyd(dist):
    for k in range(N):
        # i:start j:goal k:中間地点でループ回す
        for i in range(N):
            for j in range(N):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    return dist

warshall_floyd(query)

if query != query_before:
    print(-1)
    exit()

edges = []
for i in range(N):
    for j in range(i + 1, N):
        edges.append([query[i][j], i, j])

cnt = 0
for i in edges:
    flag = True
    w, s, t = i
    for k in range(N):
        if k != s and k != t and w >= query[s][k] + query[k][t]:
            flag = False
            break
    if flag:
        cnt += w
print(cnt)

Submission status: Accepted

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

    ans = 0
    for i in range(n - 1):
        for j in range(i + 1, n):
            d = m[i][j]
            for k in range(n):
                if k in (i, j):
                    continue
                t = m[i][k] + m[k][j]
                if t < d:
                    print(-1)
                    return
                if t == d:
                    break
            else:
                ans += d
    else:
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

    ans = 0
    for i in range(n - 1):
        for j in range(i + 1, n):
            d = m[i][j]
            for k in range(n):
                if k in (i, j):
                    continue
                t = m[i][k] + m[k][j]
                if t < d:
                    print(-1)
                    exit()
                if t == d:
                    break
            else:
                ans += d
    else:
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    import heapq
    n = int(readline())
    dist = [[INF] * n for _ in range(n)]
    hq = []
    table = [[0] * n for _ in range(n)]

    for i in range(n):
        a = list(map(int, readline().split()))
        for j in range(i + 1, n):
            hq.append((a[j], i, j))
            table[i][j] = a[j]
            dist[i][j] = a[j]
            dist[j][i] = a[j]

    for i in range(n):
        dist[i][i] = 0

    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]:
                    dist[i][j] = dist[i][k] + dist[k][j]
                    dist[j][i] = dist[i][j]

    for i in range(n):
        for j in range(i + 1, n):
            if dist[i][j] != table[i][j]:
                print(-1)
                sys.exit()

    ans = 0
    for i in range(n):
        for j in range(i + 1, n):
            for k in range(n):
                if k != i and k!= j:
                    if dist[i][j] == dist[i][k] + dist[k][j]:
                        break
            else:
                ans += dist[i][j]

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class Graph():  #non-directed
    def __init__(self, n, edge, indexed=1):
        self.n = n
        self.edge = edge
        self.indexed = indexed
        self.graph = [[] for _ in range(n)]
        for e in edge:
            self.graph[e[0] - indexed].append((e[1] - indexed, e[2]))
            self.graph[e[1] - indexed].append((e[0] - indexed, e[2]))

    def warshall_floyd(self, INF=10**18):
        dist = [[INF for j in range(self.n)] for i in range(self.n)]
        for i in range(self.n):
            dist[i][i] = 0
        for i in range(self.n):
            for j, cost in self.graph[i]:
                dist[i][j] = cost
        for k in range(self.n):
            for i in range(self.n):
                for j in range(self.n):
                    if dist[i][k] != INF and dist[k][j] != INF:
                        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
        return dist

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

E = list()

for i in range(N):
    for j in range(N):
        if i == j:
            continue
        E.append((i, j, A[i][j]))

g = Graph(N, E, 0)
wf = g.warshall_floyd()

flag = False

for i in range(N):
    for j in range(N):
        if A[i][j] != wf[i][j]:
            print(-1)
            flag = True
            break
    if flag:
        break
else:
    res = 0
    for i in range(N - 1):
        for j in range(i + 1, N):
            for k in range(N):
                if i == k or j == k:
                    continue
                if A[i][j] == A[i][k] + A[k][j]:
                    break
            else:
                res += A[i][j]

    print(res)

Submission status: Accepted

Solution code:
N = int(input())
dist = [[float("inf") if i != j else 0 for i in range(N)] for j in range(N)]

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

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

for i in range(N):
    for j in range(i + 1, N):
        for k in range(N):
            if k == i or k == j:
                continue
            # kを通る迂回ルートが存在する場合dist[i][j]取り除く(=カウントしない)
            if dist[i][j] == dist[i][k] + dist[k][j]:
                break
        else:
            # 迂回ルートが一つもなかった場合は答えに加算する
            ans += dist[i][j]
print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())
# list(map(int, input().split()))

N = int(input())
dist = [[float("inf") if i != j else 0 for i in range(N)] for j in range(N)]

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

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

for i in range(N):
    for j in range(i + 1, N):
        for k in range(N):
            if k == i or k == j:
                continue
            if dist[i][j] == dist[i][k] + dist[k][j]:
                break
        else:
            ans += dist[i][j]
print(ans)

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:
# ABC074D

import sys
input=sys.stdin.readline

def main():
    N=int(input())
    A=[tuple(map(int,input().split())) for i in range(N)]
    
    ans=0
    for i in range(N):
        for j in range(i+1,N):
            ans+=A[i][j]
            for k in range(N):
                if i!=k and j!=k:
                    if A[i][j]>A[i][k]+A[k][j]:
                        print(-1)
                        exit()
                    elif A[i][j]==A[i][k]+A[k][j]:
                        ans-=A[i][j]
                        break
                    
    print(ans)
    
    
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
def resolve():
    N = int(input())
    A = [list(map(int, input().split())) for _ in range(N)]
    ans = 0
    for src in range(N-1):
        for dst in range(src+1, N):
            mintotal = float("inf")
            for trans in range(N):
                if trans == src or trans == dst:
                    continue
                mintotal = min(mintotal, A[src][trans] + A[trans][dst])
            if A[src][dst] > mintotal:
                print(-1)
                return
            if A[src][dst] < mintotal:
                ans += A[src][dst]
    print(ans)




if '__main__' == __name__:
    resolve()

Submission status: Accepted

Solution code:
def main():
    import sys

    def I():
        return int(sys.stdin.readline().rstrip())

    def LI():
        return list(map(int, sys.stdin.readline().rstrip().split()))  # 空白あり

    N = I()
    A = [[0] * (N + 1)] + [[0] + LI() for _ in range(N)]

    ans = (sum(sum(A[i]) for i in range(N + 1))) // 2
    minus = 0

    # A[i][j]が実現可能か、必要かを判定していく
    for i in range(1, N):
        for j in range(i + 1, N + 1):
            for k in range(1, N + 1):
                if k == i or k == j:
                    continue
                else:
                    if A[i][j] > A[i][k] + A[k][j]:  # A[i][j]が実現できない
                        print(-1)
                        exit()
                    elif A[i][j] == A[i][k] + A[k][j]:  # A[i][j]は無駄
                        minus += A[i][j]
                        break

    print(ans - minus)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline

def main():
    N = int(input())
    grid = []
    for _ in range(N):
        tmp = list(map(int, readline().split()))
        grid.append(tmp)
    
    removes = set([])
    for k in range(N):
        for i in range(N):
            for j in range(N):
                gridij = grid[i][j]
                gridik = grid[i][k]
                gridkj = grid[k][j]
                if gridij > gridik + gridkj:
                    print(-1)
                    return
                elif i != j and j != k and k != i and gridij == gridik + gridkj:
                    removes.add((i, j))
                else:
                    pass
    
    ans = 0
    for i in range(N):
        for j in range(i+1, N):
            ans += grid[i][j] * ((i, j) not in removes)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from sys import stdin, stdout
input = stdin.readline
print = stdout.write

N = int(input())
A = [[int(i) for i in input().split()] for _ in range(N)]
sumA = sum(sum(A, [])) // 2
correct = True

def isCorrect():
    for u in range(N):
        for v in range(u + 1, N):
            for k in range(N):
                if A[u][k] and A[v][k]:
                    #print(u,v,k,A[u][k],A[v][k],A[u][v])
                    if A[u][k] + A[k][v] < A[u][v]:
                        return False
    return True


if not isCorrect(): print(str(-1))
else:
    for u in range(N):
        for v in range(u + 1, N):
            for k in range(N):
                if A[u][k] and A[k][v]:
                    if A[u][k] + A[k][v] == A[u][v]:
                        sumA -= A[u][v]
                        break
    print(str(sumA))

Submission status: Accepted

Solution code:
from sys import stdin, stdout
input = stdin.readline
#print = stdout.write

N = int(input())
A = [[int(i) for i in input().split()] for _ in range(N)]
sumA = sum(sum(A, [])) // 2
correct = True

def isCorrect():
    for u in range(N):
        for v in range(u + 1, N):
            for k in range(N):
                if A[u][k] and A[v][k]:
                    #print(u,v,k,A[u][k],A[v][k],A[u][v])
                    if A[u][k] + A[k][v] < A[u][v]:
                        return False
    return True


if not isCorrect(): print(str(-1))
else:
    for u in range(N):
        for v in range(u + 1, N):
            for k in range(N):
                if A[u][k] and A[k][v]:
                    if A[u][k] + A[k][v] == A[u][v]:
                        sumA -= A[u][v]
                        break
    print(str(sumA))

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


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

    ans = 0
    for i in range(N):
        for j in range(i + 1, N):
            needed = True
            for k in range(N):
                if k == i or k == j:
                    continue
                if G[i][j] > G[i][k] + G[k][j]:
                    print(-1)
                    return
                if G[i][j] == G[i][k] + G[k][j]:
                    needed = False
            if needed:
                ans += G[i][j]

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


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

    ans = 0
    for i in range(N):
        for j in range(i + 1, N):
            needed = True
            for k in range(N):
                if G[i][j] > G[i][k] + G[k][j]:
                    print(-1)
                    return
                if k not in (i, j) and G[i][j] == G[i][k] + G[k][j]:
                    needed = False
            if needed:
                ans += G[i][j]

    print(ans)
    return


if __name__ == '__main__':
    main()