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:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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)]

sys.setrecursionlimit(1000000)
mod = 1000000007

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

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
"""from collections import *
from itertools import *
from bisect import *
from heapq import *

import math
from fractions import gcd"""
import sys
input = sys.stdin.readline
from heapq import*
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()
res = 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
            if A[i][j]==A[i][k]+A[k][j]:
                break
        else:
            res += A[i][j]
print(res)

Submission status: Accepted

Solution code:
"""from collections import *
from itertools import *
from bisect import *
from heapq import *

import math
from fractions import gcd"""
from heapq import*
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()
res = 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
            if A[i][j]==A[i][k]+A[k][j]:
                break
        else:
            res += A[i][j]
print(res)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 1000000007

    N=int(input())
    dp=[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 dp[i][j]>dp[i][k]+dp[k][j]:
                    print(-1)
                    exit()
    #dp[i][j]=dp[i][k]+dp[k][j] が成り立つ時調べる？
    res = 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
                if dp[i][j]==dp[i][k]+dp[k][j]:
                    break
            else:
                res += dp[i][j]
    print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, *L = map(int, open(0).read().split())
cost = []
for i,m in enumerate(zip(*[iter(L)]*N)):
  cost.append(list(m))
  cost[i][i] = 10**10
ans = 0
for i in range(N):
  for j in range(i):
    m = min(a+b for a, b in zip(cost[i],cost[j]))
    if m<cost[i][j]:
      print(-1)
      exit()
    if m>cost[i][j]:
      ans += cost[i][j]
print(ans)

Submission status: Accepted

Solution code:
N, *L = map(int, open(0).read().split())
cost = []
for m in zip(*[iter(L)]*N):
  cost.append(m)
ans = 0
for i in range(N):
  for j in range(i):
    for k in range(N):
      if k==i or k==j:
        continue
      if cost[i][j]>cost[i][k]+cost[k][j]:
        print(-1)
        import sys
        sys.exit()
      if cost[i][j]==cost[i][k]+cost[k][j]:
        break
    else:
      ans += cost[i][j]
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
dist = [list(map(int, input().split())) for i in range(n)]
use = [[True]*n for _ in range(n)]
# 最短性の確認
for i in range(n):
    for j in range(n):
        for k in range(n):
            if dist[j][k] > dist[j][i] + dist[i][k]:
                print(-1)
                exit()
            if (i - j) * (j - k) * (k - i) and dist[j][k] == dist[j][i] + dist[i][k]:
                use[j][k] = False
                
ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
import math,itertools,bisect,sys,copy,queue
INF = 10**20

def LI(): return [int(x) for x in sys.stdin.readline().split()]

N = int(input())
A = [LI() for _ in range(N)]
a = copy.deepcopy(A)


for k in range(N):
    for i in range(N):
        for j in range(N):
            if A[i][j] == 0 or A[i][k] == 0 or A[k][j] == 0: continue
            if A[i][j] > A[i][k] + A[k][j]:
                print (-1)
                exit (0)
            if A[i][j] == A[i][k] + A[k][j]:
                A[i][j] = 0
print (sum(sum(A[i]) for i in range(N) )//2)

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):
    for j in range(N):
        cnt += A[i][j]
flg = 0
B = [[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 A[i][j]>A[i][k]+A[k][j]:
                flg = -1
                break
            elif A[i][j]==A[i][k]+A[k][j] and A[i][k]*A[k][j]>0 and B[i][j]==0:
                cnt -= A[i][j]
                B[i][j]=1
        if flg==-1:break
    if flg==-1:break
if flg==-1:
    print(-1)
else:
    print(cnt//2)

Submission status: Accepted

Solution code:
import sys
import math
import fractions
import itertools
from collections import deque
import copy
import heapq
import bisect


def warshall_floyd(d):
    """
    d[i][l]がi→lへのコストを示す隣接行列
    結果としてd[i][l]はi→lへの最短コストになる。
    """
    info = copy.deepcopy(d)
    for i in range(len(info)):
        for l in range(len(info)):
            for k in range(len(info)):
                info[l][k] = min(info[l][k], info[l][i] + info[i][k])
    return info


MOD = float('inf')
INF = 10 ** 18 + 7
input = lambda: sys.stdin.readline().strip()

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

result = warshall_floyd(A)
ans = 0
for i in range(N):
    for l in range(N):
        if result[i][l] != A[i][l]:
            print(-1)
            sys.exit()
        ans += A[i][l]
        if A[i][l] == 0:
            A[i][l] = INF

ans /= 2
for i in range(N - 1):
    for l in range(i + 1, N):
        for k in range(N):
            if A[i][l] == A[i][k] + A[k][l]:
                ans -= A[i][l]
                break
print(int(ans))

Submission status: Accepted

Solution code:
import numpy as np

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


def solve():
    N = int(input())
    A = np.array([input().split() for _ in range(N)], dtype=np.int64).reshape(N, N)
    
    B = floyd_warshall(csr_matrix(A), directed=False)
    
    if np.any(B < A):
        print(-1)
        exit()
    
    np.fill_diagonal(B, np.inf)
    for i in range(N - 1):
        for j in range(i + 1, N):
            if B[i][j] == np.min(B[i] + B[j]):
                A[i][j] = A[j][i] = 0
    print(np.sum(A) // 2)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque
 
sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7
 
DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]
 
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N = I()
    G = []
    for _ in range(N):
        a = LI()
        G.append(a)
    dp = copy.deepcopy(G)
    for i in range(N):
        for j in range(N):
            for k in range(N):
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
 
    if dp != G:
        print(-1)
        return
 
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if j == k:
                    continue
                if i == k:
                    continue
                if dp[i][k] == 0 or dp[i][j] == 0 or dp[j][k] == 0:
                    continue
                if dp[i][j] == dp[i][k] + dp[k][j]:
                    dp[i][j] = 0
                    dp[j][i] = 0
    cnt = 0
    for i in range(N):
        for j in range(N):
            cnt += dp[i][j]
    print(cnt // 2)
main()

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix

import numpy as np

n = int(input())
a = np.array([list(map(int, input().split())) for _ in range(n)])

g = csr_matrix(a)
dist = floyd_warshall(g)

if (dist == a).all():
    sm = a.sum()
    sm //= 2

    INF = 10 ** 18 + 1
    for i in range(n):
        a[i, i] = INF

    for u in range(n):
        for v in range(u + 1, n):
            mn = np.min(a[u] + a[v])
            if mn == a[u, v]:
                sm -= a[u, v]

    print(sm)

else:
    print(-1)

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix

import numpy as np

n = int(input())
a = np.array([list(map(int, input().split())) for _ in range(n)])

g = csr_matrix(a)
dist = floyd_warshall(g)

if (dist == a).all():
    sm = a.sum()

    INF = 10 ** 18 + 1
    for i in range(n):
        a[i, i] = INF

    for u in range(n):
        for v in range(n):
            if u == v:
                continue

            mn = np.min(a[u] + a[v])
            if mn == a[u, v]:
                sm -= a[u, v]

    ans = sm // 2
    print(ans)

else:
    print(-1)

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix

import numpy as np

n = int(input())
a = np.array([list(map(int, input().split())) for _ in range(n)])

g = csr_matrix(a)
dist = floyd_warshall(g)

if (dist == a).all():
    sm = dist.sum()

    INF = 10 ** 18 + 1
    for i in range(n):
        dist[i, i] = INF

    for u in range(n):
        for v in range(n):
            if u == v:
                continue

            mn = np.min(dist[u] + dist[v])
            if mn == dist[u, v]:
                sm -= dist[u, v]

    ans = int(sm) // 2
    print(ans)

else:
    print(-1)

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix

import numpy as np

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

a = np.array(a)

g = csr_matrix(a)
dist = floyd_warshall(g)

bl = dist == a

if bl.all():
    sm = dist.sum()
    INF = 10 ** 18 + 1
    inf = np.array([INF] * n)
    inf = np.diag(inf)
    dist += inf
    for u in range(n):
        for v in range(n):
            if u == v:
                continue

            mn = np.min(dist[u] + dist[v])
            if mn == dist[u, v]:
                sm -= dist[u, v]

    ans = int(sm) // 2
    print(ans)

else:
    print(-1)

Submission status: Accepted

Solution code:
import sys

N = int(sys.stdin.readline().strip())
A = [list(map(int, sys.stdin.readline().strip().split())) for _ in range(N)]
need = [[True]*N for _ in range(N)]

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

            if A[i][j]+A[j][k]<A[i][k]:
                print(-1)
                exit()

            if A[i][j]+A[j][k]==A[i][k]:
                need[i][k] = False

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

Submission status: Accepted

Solution code:
from copy import deepcopy
import sys
input = sys.stdin.readline


def floyd_warshall(dist):
    v = len(dist)
    for k in range(v):
        for i in range(v):
            for j in range(v):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])


N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
dist = deepcopy(A)
floyd_warshall(dist)
edges = []
for u in range(N-1):
    for v in range(u+1, N):
        edges.append((A[u][v], u, v))
edges.sort()
ans = 0
for d, u, v in edges:
    if dist[u][v] < d:
        ans = -1
        break
    ok = False
    for w in range(N):
        if w == u or w == v:
            continue
        if dist[u][w] + dist[w][v] == dist[u][v]:
            ok = True
            break
    if not ok:
        ans += d
print(ans)

Submission status: Accepted

Solution code:
def JOI14_B():
    N = I()
    A = [I()for _ in range(N)]
    A.extend(A)
    dp = [[0]*(N*2+1) for _ in range(N*2+1)]

    for j in range(N):
        for i in range(N*2-j):
            if (N-j)%2==1:
                dp[i][i+j] = max(dp[i+1][i+j]+A[i],dp[i][i+j-1]+A[i+j])
            else:
                if A[i]>A[i+j]:
                    dp[i][i+j] = dp[i+1][i+j]
                else:
                    dp[i][i+j] = dp[i][i+j-1]
    ans = 0
    for i in range(N):
        ans = max(ans,dp[i][i+N-1])
    print(ans)
    #print(dp)
    return

def square869120Contest1_G():
    def held_karp(dists,TL):
        # Copyright (c) 2016 Carl Ekerot
        """
        Implementation of Held-Karp, an algorithm that solves the Traveling
        Salesman Problem using dynamic programming with memoization.
        Parameters:
            dists: distance matrix
        Returns:
            A tuple, (cost, path).
        """
        n = len(dists)

        # Maps each subset of the nodes to the cost to reach that subset, as well
        # as what node it passed before reaching this subset.
        # Node subsets are represented as set bits.
        C = {}
        dp = defaultdict(int)

        # Set transition cost from initial state
        for k in range(1, n):
            C[(1 << k, k)] = (dists[0][k], 0)
            dp[(1 << k, k)] = 1

        # Iterate subsets of increasing length and store intermediate results
        # in classic dynamic programming manner
        for subset_size in range(2, n):
            for subset in itertools.combinations(range(1, n), subset_size):
                # Set bits for all nodes in this subset
                bits = 0
                for bit in subset:
                    bits |= 1 << bit
                shortest_length = inf
                # Find the lowest cost to get to this subset
                for k in subset:
                    prev = bits & ~(1 << k)

                    res = []
                    for m in subset:
                        if not (prev, m) in C:
                            continue
                        if m == 0 or m == k:
                            continue
                        if C[(prev, m)][0] + dists[m][k]>TL[m][k]:
                            continue
                        res.append((C[(prev, m)][0] + dists[m][k], m))
                        if shortest_length>C[(prev, m)][0] + dists[m][k]:
                            shortest_length = C[(prev, m)][0] + dists[m][k]
                    if not res:
                        continue
                    C[(bits, k)] = min(res)
                    for d,m in res:
                        if shortest_length!=d:
                            continue
                        dp[(bits, k)] += dp[(prev,m)]

        # We're interested in all bits but the least significant (the start state)
        bits = (2 ** n - 1) - 1

        # Calculate optimal cost
        res = []
        shortest_length = inf
        for k in range(1, n):
            if not (bits, k) in C:
                continue
            if C[(bits, k)][0] + dists[k][0] > TL[k][0]:
                continue
            res.append((C[(bits, k)][0] + dists[k][0], k))
            if shortest_length > C[(bits, k)][0] + dists[k][0]:
                shortest_length = C[(bits, k)][0] + dists[k][0]
        if not res:
            return False
        opt, parent = min(res)
        way = 0
        for d, k in res:
            if not (bits, k) in C:
                continue
            if C[(bits, k)][0] + dists[k][0] > TL[k][0]:
                continue
            if shortest_length < d:
                continue
            way += dp[(bits,k)]

        # Backtrack to find full path
        path = []
        for i in range(n - 1):
            path.append(parent)
            new_bits = bits & ~(1 << parent)
            _, parent = C[(bits, parent)]
            bits = new_bits

        # Add implicit start state
        path.append(0)

        return shortest_length, list(reversed(path)), way

    N, M = LI()
    dist = [[inf]*N for _ in range(N)]
    TL = [[0]*N for _ in range(N)]
    for _ in range(M):
        s, t, d, time = LI()
        s -= 1; t -= 1
        dist[s][t] = dist[t][s] = d
        TL[s][t] = TL[t][s] = time
    ans = held_karp(dist,TL)
    if (not ans) or ans[2]==0:
        print("IMPOSSIBLE")
        return
    print(ans[0],ans[2])
    return

def JOI13_D():
    def solve(yday,leader,next):
        a = [0]*3
        for i in range(3):
            if next&(1<<i)==(1<<i):
                a[i] = 1
        rep = 0
        if a[leader]==0:
            return rep
        for i in range(3):
            if yday&(1<<i)==(1<<i):
                if a[i]==1:
                    rep = 1
        return rep
    N = I()
    S = SI()
    member = {"J":0,"O":1,"I":2}
    dp = [[0]*8 for _ in range(N+1)]
    dp[0][1] = 1
    for i in range(N):
        leader = member[S[i]]
        for j in range(8):
            for k in range(8):
                dp[i+1][j] += (dp[i][k]*solve(k,leader,j))
    ans = sum(dp[-1])%10007
    #print(dp)
    print(ans)
    return

def JOI16_D():
    N, M = LI()
    A = [(I()-1)for _ in range(N)]
    imos = [[0] * (N + 1) for _ in range(M)]
    for i in range(M):
        for j in range(N):
            imos[i][j + 1] += imos[i][j] + (A[j] != i)
    loop = 2**M
    dp = [inf]*loop
    dp[0] = 0
    cnt = Counter(A)
    L = [0]*loop
    #print(imos)
    for i in range(loop):
        for j in range(M):
            if i&(1<<j)==(1<<j):
                continue
            next = i|(1<<j)
            if L[next]==0:
                L[next] = L[i]+cnt[j]
            cur = imos[j][L[next]] - imos[j][L[i]]
            if dp[next]>dp[i] + cur:
                dp[next] = dp[i] + cur
    ans = dp[-1]
    #print(L)
    print(ans)
    return

def ABC6_D():
    N = I()
    C = [I() for _ in range(N)]
    LIS = [C[0]]
    for i in range(N):
        if C[i] > LIS[-1]:
            LIS.append(C[i])
        else:
            LIS[bisect.bisect_left(LIS, C[i])] = C[i]
    print(N - len(LIS))
    return

def ABC134_E():
    N = I()
    A = [I()for _ in range(N)]
    que = deque()
    que.append(A[0])
    L = 1
    for i in range(1,N):
        cur = bisect.bisect_left(que,A[i])
        #print(que,cur,L)
        if cur==0:
            que.appendleft(A[i])
            L += 1
        else:
            que[cur-1] = A[i]

    #print(que)
    ans = len(que)
    print(ans)

    return

def JOI7_F():
    def dijkstra_2(edge_adj, node, start):
        # node<=2000くらい
        # edge_adj[node][to] = [cost]
        dist = [inf] * node
        used = [False] * node
        dist[start] = 0
        while True:
            v = -1
            for i in range(node):
                if not used[i] and (v == -1 or dist[v] > dist[i]):
                    v = i
            if v == -1:
                break
            used[v] = True
            for i in range(node):
                if dist[i] > dist[v] + edge_adj[v][i]:
                    dist[i] = dist[v] + edge_adj[v][i]
        return dist
    N, K = LI()
    V = [[inf]*N for _ in range(N)]
    ans = []
    for _ in range(K):
        A = LI()
        s = A[1]-1
        t = A[2]-1
        if A[0]==1:
            if V[s][t] <= A[3]:
                continue
            V[s][t] = A[3]
            V[t][s] = A[3]
        else:
            dist = dijkstra_2(V,N,s)
            ans.append(dist[t])
    for v in ans:
        if v==inf:
            print(-1)
            continue
        print(v)
    return

def JOI15_E():
    def bfs(n, E, fordfs):
        # 点の数、スタートの点、有向グラフ
        W = [inf] * n
        # 各点の状態量、最短距離とか,見たかどうかとか
        que = deque()
        for e in E:
            e -=1
            W[e] = 0
            que.append(e)
        while que:
            now = que.popleft()
            nowW = W[now]
            for ne in fordfs[now]:
                if W[ne] > nowW + 1:
                    W[ne] = nowW + 1
                    que.append(ne)
        return W

    class Dijkstra(object):
        """
        construct: O(ElogV)
        """

        def __init__(self, edges, start=0):
            """
            :param list of list of list of int edges:
            :param int start=0:
            """
            self.__dist = [inf] * len(edges)
            self.__dist[start] = 0
            self.__calculate(edges, start)

        @property
        def dist(self):
            return self.__dist

        def __calculate(self, edges, start):
            Q = [(0, start)]  # (dist,vertex)
            while (Q):
                dist, v = heapq.heappop(Q)
                if self.dist[v] < dist: continue  # 候補として挙がったd,vだが、他に短いのがある
                for u, cost in edges[v]:
                    if self.dist[u] > self.dist[v] + cost:
                        self.__dist[u] = self.dist[v] + cost
                        heapq.heappush(Q, (self.dist[u], u))
    N, M, K, S = LI()
    P, Q = LI()
    C = [I()for _ in range(K)]
    V = [[]for _ in range(N)]
    for _ in range(M):
        s, t = LI()
        s -= 1
        t -= 1
        V[s].append(t)
        V[t].append(s)
    L = bfs(N,C,V)
    #print(L)
    cost = [[]for _ in range(N)]
    for i in range(N):
        for v in V[i]:
            if L[v]==0:
                continue
            elif L[v]<=S:
                cost[i].append((v,Q))
            else:
                cost[i].append((v,P))
    di = Dijkstra(cost)
    ans = di.dist
    #print(cost)
    if L[-1]<=S:
        print(ans[N-1]-Q)
    else:
        print(ans[N-1]-P)
    return

def JOI13_E():
    def bfs(n, e, fordfs):
        # 点の数、スタートの点、有向グラフ
        W = [inf] * n
        # 各点の状態量、最短距離とか,見たかどうかとか
        W[e] = 0
        que = deque()
        que.append(e)
        while que:
            now = que.popleft()
            nowW = W[now]
            for ne in fordfs[now]:
                if W[ne] == inf:
                    W[ne] = nowW + 1
                    que.append(ne)
        return W

    def dijkstra_2(edge_adj, node, start):
        # node<=2000くらい
        # edge_adj[node][to] = [cost]
        dist = [inf] * node
        used = [False] * node
        dist[start] = 0
        while True:
            v = -1
            for i in range(node):
                if not used[i] and (v == -1 or dist[v] > dist[i]):
                    v = i
            if v == -1:
                break
            used[v] = True
            for i in range(node):
                if dist[i] > dist[v] + edge_adj[v][i]:
                    dist[i] = dist[v] + edge_adj[v][i]
        return dist
    N, K = LI()
    C = [[]for _ in range(N)]
    V = [[]for _ in range(N)]
    for i in range(N):
        C[i] = LI()
    for i in range(K):
        a, b = LI()
        a -= 1
        b -= 1
        V[a].append(b)
        V[b].append(a)
    costV = [[inf]*N for _ in range(N)]
    for i in range(N):
        L = bfs(N,i,V)
        c = C[i][0]; l = C[i][1]
        for j in range(N):
            if i==j:
                continue
            if L[j]<=l:
                costV[i][j] = c
    dist = dijkstra_2(costV,N,0)
    ans = dist[N-1]
    #print(costV)
    print(ans)
    return

def ABC12_D():
    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, M = LI()
    V = [[inf]*N for _ in range(N)]
    for i in range(N):
        V[i][i] = 0
    for _ in range(M):
        a, b, t = LI()
        a -= 1
        b -= 1
        V[a][b] = t
        V[b][a] = t
    L = warshall_floyd(N,V)
    #print(L)
    ans = inf
    for i in range(N):
        cur = max(L[i])
        ans = min(ans,cur)
    print(ans)
    return

def ABC79_D():
    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
    H, W = LI()
    C = [LI()for _ in range(10)]
    A = [LI()for _ in range(H)]
    L = warshall_floyd(10,C)
    #print(L)
    ans = 0
    for a in A:
        for i in a:
            if i>=0:
                ans += L[i][1]
    print(ans)
    return

def JOIgassyuku10_3():
    N, M, K = LI()
    V = [[]for _ in range(N)]
    for _ in range(M):
        a, b, c = LI()
        a -= 1
        b -= 1
        V[a].append((b,c))
        V[b].append((a,c))


    return

def ABC74_D():
    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 = warshall_floyd(N,copy.deepcopy(A))
    shortest_path = 0
    for i in range(N):
        for j in range(N):
            if i==j:
                continue
            if dist[i][j]<A[i][j]:
                print(-1)
                return
            if dist[i][j]>A[i][j]:
                continue
            flag = True
            for k in range(N):
                if i==k or j==k:
                    continue
                judge = (dist[i][k]+dist[k][j])-dist[i][j]
                if judge==0:
                    flag = False
            if flag:
                shortest_path += A[i][j]
    ans = shortest_path//2
    print(ans)
    return



def square869120Contest1_E():
    N, Q = LI()
    A = LI()
    C = LI()
    C.append(1)
    L = [0]*N
    for i in range(1,N):
        L[i] = pow(A[i-1],A[i],mod) + L[i-1]
    #print(L)
    ans = 0
    now = 0
    for i in range(Q+1):
        next = C[i]-1
        cur = abs(L[next]-L[now])
        ans += cur
        ans %= mod
        now = next
        #print(ans)
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque

import gc
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__':
    ABC74_D()
"""

"""

Submission status: Accepted

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

for i in range(N):
    for j in range(N):
        for k in range(N):
            if i==j or j==k or k==i:
                continue
            
            if A[i][j]+A[j][k]<A[i][k]:
                print(-1)
                exit()
                
            if A[i][j]+A[j][k]==A[i][k]:
                need[i][k] = False

ans = 0

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

print(ans//2)

Submission status: Accepted

Solution code:
from copy import deepcopy
N = int(input())
A = []
for i in range(N):
    A.append(list(map(int,input().split())))
B = deepcopy(A)
for u in range(N):
    for v in range(u):
        if u <= v:
            continue
        for w in range(N):
            if w == u or w == v:
                continue
            if A[u][v] > A[u][w]+A[w][v]:
                print(-1)
                exit()
            if A[u][v] == A[u][w]+A[w][v]:
                B[u][v] = 0
                B[v][u] = 0
ans = 0
for i in range(N):
    for j in range(N):
        ans += B[i][j]
print(ans//2)