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: Time Limit Exceeded

Solution code:
def D_RestoringRoadNetwork(N, A):
    dist = [x[:] for x in A] # 全ての町同士の距離
    dist2 = [x[:] for x in A] # 不要な経路を削ぎ落とした町同士の距離
    isMinDist = True  # 与えられた行列が真に最短距離を表しているか

    # ワーシャルフロイド法
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if A[i][j] > dist[i][k] + dist[k][j]:
                    # 迂回路の方が短いとなれば元の行列は最短距離を表していない
                    isMinDist = False
                elif A[i][j] == dist[i][k] + dist[k][j] and dist[i][k] > 0 and dist[k][j] > 0:
                    # 最短経路でも迂回路でも同じ距離ならば、表にあった最短距離の経路は不要
                    dist2[i][j] = 0
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    if isMinDist:
        ans = 0
        for i in range(N):
            for j in range(i, N):
                # 行列の上三角しか見ないのは、対称行列(ij成分=ji成分)になるから
                ans += dist2[i][j]
        return ans
    else:
        return -1

N=int(input())
A=[[int(i) for i in input().split()] for j in range(N)]
print(D_RestoringRoadNetwork(N, A))

Submission status: Time Limit Exceeded

Solution code:
import sys

# sys.stdin = open('d1.in')


def read_int_list():
    return list(map(int, input().split()))


def read_str_list():
    return input().split()


def read_int():
    return int(input())


def read_str():
    return input()


def solve():
    n = read_int()
    d = [read_int_list() for i in range(n)]
    res = 0
    for i in range(n):
        for j in range(i+1, n):
            ok = True
            for k in range(n):
                if k != i and k != j:
                    ok &= d[i][j] < d[i][k] + d[k][j]
                    if d[i][j] > d[i][k] + d[k][j]:
                        return -1
            if ok:
                res += d[i][j]
    return res


def main():
    res = solve()
    print(res)


main()

Submission status: Time Limit Exceeded

Solution code:
import sys

# sys.stdin = open('d1.in')


def read_int_list():
    return list(map(int, input().split()))


def read_str_list():
    return input().split()


def read_int():
    return int(input())


def read_str():
    return input()


def solve():
    n = read_int()
    d = [read_int_list() for i in range(n)]
    for i in range(n):
        for j in range(i+1, n):
            for k in range(n):
                if not d[i][j] <= d[i][k] + d[k][j]:
                    return -1
    res = 0
    for i in range(n):
        for j in range(i+1, n):
            ok = True
            for k in range(n):
                if k != i and k != j:
                    ok &= d[i][j] < d[i][k] + d[k][j]
            if ok:
                res += d[i][j]
    return res


def main():
    res = solve()
    print(res)


main()

Submission status: Time Limit Exceeded

Solution code:
import sys

# sys.stdin = open('d1.in')


def read_int_list():
    return list(map(int, input().split()))


def read_str_list():
    return input().split()


def read_int():
    return int(input())


def read_str():
    return input()


def solve():
    n = read_int()
    d = [read_int_list() for i in range(n)]
    for i in range(n):
        for j in range(n):
            for k in range(n):
                if not d[i][j] <= d[i][k] + d[k][j]:
                    return -1
    res = 0
    for i in range(n):
        for j in range(i+1, n):
            ok = True
            for k in range(n):
                if k != i and k != j:
                    ok &= d[i][j] < d[i][k] + d[k][j]
            if ok:
                res += d[i][j]
    return res


def main():
    res = solve()
    print(res)


main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n = int(input())
a_all = []
for i in range(n):
    a_list = input().split()
    a_list = [int(a) for a in a_list]
    a_all.append(a_list)

a_array = np.array(a_all)
for i in range(n):
    a_array[i][:i] = 0

a_goukeiyou = np.copy(a_array)
    
huseiritsu = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        for k in range(j+1,n):
            hen1 = a_array[i][j]
            hen2 = a_array[j][k]
            hen3 = a_array[i][k]
            if hen1 <= hen2 + hen3 and hen2 <= hen1+hen3 and hen3 <= hen1 + hen2:
                if hen1 == hen2 + hen3:
                    a_goukeiyou[i][j]=0
                elif hen2 == hen3 + hen1:
                    a_goukeiyou[j][k]=0
                elif hen3 == hen1 + hen2:
                    a_goukeiyou[i][k]=0
            else:
                huseiritsu = 1
                break

if huseiritsu == 1:
    print("-1")
else:
    print(a_goukeiyou.sum())

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A = [list(map(int, input().split())) for i in range(N)]
result=0
flag=True
isbreak=False
for m in range(N-1):
    for n in range(m+1,N):
        list_t=list(range(N))
        list_t.remove(m)
        list_t.remove(n)
        for t in list_t:
            if A[m][n]>A[m][t]+A[t][n]:
                result=-1                
                isbreak=True
                break
            elif A[m][n]==A[m][t]+A[t][n] and result!=-1:
                flag=False
                break
        if flag and result!=-1:
            result+=A[m][n]
        else:
            flag=True
        if isbreak:
            break
    if isbreak:
        break
print(result)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A = [list(map(int, input().split())) for i in range(N)]
result=0
flag=True
isbreak=False
for m in range(N-1):
    for n in range(m+1,N):
        list_t=list(range(N))
        list_t.remove(m)
        list_t.remove(n)
        for t in list_t:
            if A[m][n]>A[m][t]+A[t][n]:
                result=-1
                break
                isbreak=True
            elif A[m][n]==A[m][t]+A[t][n] and result!=-1:
                flag=False
        if flag and result!=-1:
            result+=A[m][n]
        else:
            flag=True
        if isbreak:
            break
    if isbreak:
        break
print(result)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A = [list(map(int, input().split())) for i in range(N)]
result=0
flag=True
for m in range(N-1):
    for n in range(m+1,N):
        list_t=list(range(N))
        list_t.remove(m)
        list_t.remove(n)
        for t in list_t:
            if A[m][n]>A[m][t]+A[t][n]:
                result=-1
            elif A[m][n]==A[m][t]+A[t][n] and result!=-1:
                flag=False
        if flag and result!=-1:
            result+=A[m][n]
        else:
            flag=True
print(result)

Submission status: Time Limit Exceeded

Solution code:
import sys

# utils
def read_numbers():
    return [int(num) for num in sys.stdin.readline().split()]
def read_string():
    return sys.stdin.readline().rstrip('\r\n')
def list2str(*array):
    return ' '.join([str(i) for i in array])

def main(A):
    roads = [[True for i in range(len(A))] for j in range(len(A))]
    for city1 in range(0,len(A)):
        for city2 in range(city1+1, len(A)):
            distance12 = A[city1][city2]
            for city3 in range(len(A)):
                if city3 == city1 or city3 == city2:
                    continue
                distance13 = A[city1][city3]
                distance32 = A[city3][city2]
                if distance13+distance32 < distance12:
                    return -1
                if distance13+distance32 == distance12:
                    roads[city1][city2] = False
    total = 0
    for city1 in range(0,len(A)):
        for city2 in range(city1+1, len(A)):
            if roads[city1][city2]:
                total += A[city1][city2]
    return total

def parse_stdin():
    # N = read_numbers()
    # data = []
    # for i in range(N):
    #    data.append(read_numbers())
    N = read_numbers()[0]
    A = []
    for i in range(N):
        A.append(read_numbers())
    return A

def test_main():
    """run pytest stdin.py to test"""
    assert main([[0, 1, 3],
                 [1, 0, 2],
                 [3, 2, 0]]) == 3

if __name__ == '__main__':
    A = parse_stdin()
    result = main(A)
    print(result)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
d=[]
for i in [0]*n:
    d.append([int(x) for x in input().split()])
from itertools import product
ans=0
for i,j in product(range(n),range(n)):
    flag=0
    for k in range(n):
        if d[i][j]>d[i][k]+d[k][j]:
            print(-1)
            import sys
            sys.exit()
        if d[i][j]==d[i][k]+d[k][j] and (k!=i and k!=j and i!=j ):
            flag=1
    if flag==0:
        ans+=d[i][j]
print(ans//2)

Submission status: Time Limit Exceeded

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

LARGE = 9999999999

total = 0
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        flag = False
        for k in range(n):
            if i == k or j == k:
                continue
            if a[i][j] > a[i][k] + a[k][j]:
                print(-1)
                raise SystemExit
            elif a[i][j] == a[i][k] + a[k][j]:
                flag = True
        if not flag and i < j:
            total += a[i][j]
print(total)

Submission status: Accepted

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

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

for j in range(N):
    for k in range(j):
        a = A[j][k]
        for i in range(N):
            if i in {j, k}:
                continue
            if a == A[j][i]+A[i][k]:
                break
        else:
            s += a
            # print(j,k,a)
print(s)

Submission status: Accepted

Solution code:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
ips = lambda:input().split()
import collections
import math
import itertools
import heapq as hq
import sys

n = ni()
cost =[]
tot = 0
for i in range(n):
    A = lma()
    cost.append(A)
    tot+=sum(A)
nu=[[False]*n for i in range(n)]
for k in range(n):
    for i in range(n):
        if i==k:continue
        for j in range(n):
            if j==k:
                continue
            #print("ijk",i,j,k,"cost",cost[i][j],cost[i][k]+cost[k][j])
            if cost[i][j] >cost[i][k] + cost[k][j]:
                print(-1)
                exit()
            elif cost[i][j]==cost[i][k] + cost[k][j]:

                nu[i][j]=True
#print(nu)
for i in range(n):
    for j in range(n):
        if nu[i][j]:
            tot-=cost[i][j]
print(tot//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)]
for k in range(N):
 for i in range(N):
  for j in range(N):
   b[i][j] = min(b[i][j], b[i][k] + b[k][j])
inf = 10 ** 10
if a == b:
 dp = [[inf] * N for _ in range(N)]
 for i in range(N):
  for j in range(N):
   mn = i
   for k in range(N):
    if k == j: continue
    if a[i][k] + a[k][j] == a[i][j]:
     if a[mn][j] > a[k][j]:
      mn = k
   if dp[mn][j] == inf:
    dp[mn][j] = a[mn][j]
   elif dp[mn][j] != a[mn][j]:
    print(-1)
    exit(0)
 for i in range(N):
  for j in range(N):
   if dp[i][j] == inf: dp[i][j] = 0
 print(sum([sum(dp[i]) for i in range(N)]) // 2)
else: print(-1)

Submission status: Accepted

Solution code:
INF = 10**18

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

# warshall-floyd
dist = [G[i][:] for i in range(N)]
for k in range(N):
    for i in range(N):
        for j in range(N):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

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

        if dist[i][j] < G[i][j]:
            print(-1)
            exit()

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

Submission status: Accepted

Solution code:
import sys
import copy

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


INF = 10**18


def warshall_floyd(V, cost):
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if cost[i][k] < INF and cost[k][j] < INF:
                    cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])


def main():

    V = in_n()
    cost = [[] for _ in range(V)]

    for i in range(V):
        cost[i] = in_nl()

    short_cost = copy.deepcopy(cost)
    warshall_floyd(V, short_cost)

    ans = 0
    for i in range(V):
        for j in range(i + 1, V):
            if short_cost[i][j] < cost[i][j]:
                print(-1)
                exit()
            for k in range(V):
                if i == k or j == k:
                    continue
                if short_cost[i][k] + short_cost[k][j] == cost[i][j]:
                    break
            else:
                ans += cost[i][j]

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# AtCoder Beginner Contest 074 D - Restoring Road Network　

import sys

N = int(input())
A = []
for _ in range(N):
    a = list(map(int, sys.stdin.readline().strip().split()))
    b = a
    A.append(a)

needless = [[False] * N for _ in range(N)]

# ワーシャルフロイド
for k in range(N):
    for i in range(N):
        for j in range(N):
            if A[i][j] > A[i][k] + A[k][j]:
                print(-1)
                sys.exit()
            elif (A[i][j] == A[i][k] + A[k][j]) and (A[i][k] != 0) and (A[k][j] != 0):
                needless[i][j] = True

# for i in needless:
#     print(i)

ans = 0
for h in range(N):
    for w in range(N):
        if needless[h][w] is False:
            ans += A[h][w]

print(ans // 2)

Submission status: Accepted

Solution code:
from itertools import product
def main(): 
    with open(0) as f:
        N = int(f.readline())
        A = [list(map(int, line.split())) for line in f.readlines()]

    possible = True
    ans = 0
    r = range(N)
    for i,j in product(r, r) :
        if j <= i: continue
        for k in r:
            if k == i or k == j:
                continue
            if A[i][j] < A[i][k] + A[k][j]:
                continue
            elif A[i][j] == A[i][k] + A[k][j]:
                break
            else:
                possible = False
            break
        else:
            ans += A[i][j]
    print(ans if possible else -1)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

    for i in r: A[i][i] = float('inf')
    possible = True
    ans = 0
    for i in r :
        for j in range(i+1,N):
            for k in r:
                if A[i][j] < A[i][k] + A[k][j]:
                    continue
                elif A[i][j] == A[i][k] + A[k][j]:
                    break
                else:
                    possible = False
                    break
            else:
                ans += A[i][j]
    print(ans if possible else -1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    inf=float("inf")
    n=int(input())
    alst=[list(map(int,input().split())) for _ in range(n)]
 
    for i in range(n):
        alst[i][i]=inf
 
    sm=0
    token=0
 
    for i in range(n):
        for j in range(i+1,n):
            for k in range(n):
                if alst[i][k]+alst[k][j]>alst[i][j]:
                    continue
                elif alst[i][k]+alst[k][j]==alst[i][j]:
                    break
                else:
                    token=1
                    break
            else :
                sm+=alst[i][j]
    
    if token : sm=-1
 
    print(sm)
 
main()

Submission status: Accepted

Solution code:
from collections import deque
import sys, copy, itertools,heapq
input = sys.stdin.readline

n = int(input())
MAP = [list(map(int,input().split())) for i in range(n)]
for i in range(n):
  MAP[i][i]=10**9


ans = 0
for i in range(n):
  for j in range(i+1,n):
    MAPP=[0]*n
    for k in range(n):
      MAPP[k]=MAP[i][k]+MAP[j][k]
    d = min(MAPP)
    if MAP[i][j] < d:
      ans += MAP[i][j]
    elif d < MAP[i][j]:
      print(-1)
      exit()
  
#print(MAP)
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
inf=10**15
a=[[0]*n for _ in range(n)]
dist=[[0]*n for _ in range(n)]

for u in range(n):
    for v,c in enumerate(list(map(int,input().split()))):
        a[u][v]=c
        dist[u][v]=c

def calc(n,a,dist):

    for k in range(n):
        for i in range(n):
            for j in range(n):
                if k==i or k==j or i==j or dist[i][k]==inf or dist[k][j]==inf:
                    continue
                
                if dist[i][k]+dist[k][j]==a[i][j]:
                    dist[i][j]=inf
                elif dist[i][k]+dist[k][j]<a[i][j]:
                    return -1
    
    ret=0
    for i in range(n):
        for j in range(n):
            if dist[i][j]==inf:
                continue
            ret+=dist[i][j]
    
    return ret//2


print(calc(n,a,dist))

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict, deque, Counter
from copy import deepcopy
from bisect import bisect, bisect_right, bisect_left
from heapq import heapify, heappop, heappush
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]
    
    
def main():
    N = I()
    A = [LI() for i in range(N)]

    dq = []
    heapify(dq)
    
    for i in range(N):
        for j in range(N):
            heappush(dq, (A[i][j], i, j))
    
    # dist matrix
    dist = [[float('inf') if i != j else 0 for i in range(N)] for j in range(N)]
    
    res = 0
    
    while dq:
        d, x, y = heappop(dq)
        equal = True
        for i in range(N):
            tempD = dist[x][i]+dist[i][y]
            if d > tempD:
                print(-1)
                exit()
            elif d == tempD:
                equal = False
    
        dist[x][y] = d
        dist[y][x] = d
    
        if equal:
            res+=d

    print(res)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

    for i in range(n):
        alst[i][i]=inf

    sm=0
    token=0

    for i in range(n):
        for j in range(i+1,n):
            for k in range(n):
                if alst[i][k]+alst[k][j]>alst[i][j]:
                    continue
                elif alst[i][k]+alst[k][j]==alst[i][j]:
                    break
                else:
                    token=1
                    break
            else :
                sm+=alst[i][j]
    
    if token : sm=-1

    print(sm)

main()

Submission status: Accepted

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

d = [[A[i][j] for i in range(N)]for j in range(N)]

for k in range(N):#wwa-ssyarru
    for i in range(N):
        for j in range(N):
            d[i][j] = min(d[i][j],d[i][k]+d[k][j])

for i in range(N):#言われた通りに直でつなげるだけで最短炉更新されたらもう無理
    for j in range(N):
        if A[i][j]!=d[i][j]:
            print(-1)
            exit()

ans = 0
#経由で=のとこ合ったらそこはつかわない
for i in range(N):
    for j in range(N):
        ok = True
        for k in range(N):
            if k == i or k == j:
                continue
            if d[i][j]==d[i][k]+d[j][k]:
                ok=False
        if ok:
            ans+=d[i][j]

print(ans//2)

Submission status: Accepted

Solution code:
n = int(input())
A = [list(map(int, input().split())) for _ in range(n)]
INF = 10**9 + 1
dp = [[INF]*n for _ in range(n)]

# コスト登録
for i, line in enumerate(A):
    for j, a in enumerate(line):
        dp[i][j] = a

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

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

Submission status: Accepted

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


def warshall_floyd(d):
    # d        : nxn adjacent matrix
    # next_node: node after i on the shortest path of (i,j)
    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]:
                    d[i][j] = d[i][k] + d[k][j]


def check(a, b):
    res = 0
    for i in range(n):
        for j in range(i + 1, n):
            if b[i][j] < a[i][j]:
                return -1
            flag = True
            for k in range(n):
                if k == i or k == j:
                    continue
                if b[i][j] == b[i][k] + b[k][j]:
                    flag = False
                    break
            if flag:
                res += a[i][j]
    return res


n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
b = deepcopy(a)
warshall_floyd(b)
ans = check(a, b)
print(ans)

Submission status: Accepted

Solution code:
def main():
    from sys import stdin
    input = stdin.readline

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

    ans = 0
    tf = [[True] * n for _ in range(n)]
    # Warshall-Floyd algorithm
    for k in range(n):
        for i in range(n-1):
            if i == k:
                continue
            for j in range(i, n):
                if j == k:
                    continue
                elif a[i][j] > a[i][k] + a[k][j]:
                    print(-1)
                    exit()
                elif a[i][j] == a[i][k] + a[k][j] and tf[i][j]:
                    ans -= a[i][j]
                    tf[i][j] = False
    
    ans += sum([sum(i) for i in a]) // 2
    print(ans)

main()

Submission status: Accepted

Solution code:
def main():
    from sys import stdin
    input = stdin.readline

    n = int(input())
    a = []
    for _ in range(n):
        a.append(list(map(int, input().split())))
    
    ans = 0
    tf = [[True] * n for _ in range(n)]
    # Warshall-Floyd algorithm
    for k in range(n):
        for i in range(n-1):
            if i == k:
                continue
            for j in range(i, n):
                if j == k:
                    continue
                elif a[i][j] > a[i][k] + a[k][j]:
                    print(-1)
                    exit()
                elif a[i][j] == a[i][k] + a[k][j] and tf[i][j]:
                    ans -= a[i][j]
                    tf[i][j] = False
    
    ans += sum([sum(i) for i in a]) // 2
    print(ans)

main()

Submission status: Accepted

Solution code:
import sys
import copy

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

def fnc(M):
    m = list([True]*len(M) for _ in range(len(M)))
    for k in range(len(M)):
        for i in range(len(M)):
            for j in range(len(M)):
                if M[i][j] > M[i][k]+M[k][j]:
                    print(-1)
                    sys.exit()
                if M[i][j] == M[i][k]+M[k][j] and i != k and j != k:
                    m[i][j] = False
    return M,m

M,m = fnc(A)

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys 
from heapq import heappop,heappush
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())
# INF = 10**31
cost = [[0]*(N+1) for _ in range(N+1)] 
tmp = [[0]*(N+1) for _ in range(N+1)] 
for i in range(N):
    A = list(map(int,readline().split()))
    for j in range(N):
        cost[i+1][j+1] = A[j]
        tmp[i+1][j+1] = A[j]
        

for k in range(1,N+1):
    for i in range(1,N+1):
        for j in range(1,N+1):
            if cost[i][j] > cost[i][k] + cost[k][j]:
                print(-1)
                sys.exit()
            if cost[i][k] and cost[k][j] and cost[i][j] == cost[i][k] + cost[k][j]:
                tmp[i][j] = 0

ans = sum([sum([c for c in row]) for row in tmp])
print(ans//2)

Submission status: Accepted

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

np.fill_diagonal(A, 10**9)

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

print(ans)

Submission status: Accepted

Solution code:
from numpy import *
N = int(input())
A = array([input().split() for _ in range(N)], dtype=int64).reshape(N,N)

fill_diagonal(A, 10**9)

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

print(ans)

Submission status: Accepted

Solution code:
from numpy import *
N = int(input())
A = array([input().split() for _ in range(N)], dtype=int64)

fill_diagonal(A, 10**9)

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

print(ans)

Submission status: Accepted

Solution code:
from numpy import *
N = int(input())
A = array([input().split() for _ in range(N)], dtype=int64)

fill_diagonal(A, 10**10)

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

print(ans)

Submission status: Accepted

Solution code:
from numpy import *
N = int(input())
A = array([list(map(int,input().split())) for n in range(N)])

fill_diagonal(A, 10**10)

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

print(ans)

Submission status: Accepted

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

def warshall_floyd(adj_mat: list):
    """
    ワーシャルフロイド
    隣接行列を受け取る(隣接していないノードはINF、自身へのコストは0)
    全点の間の最短距離をあらわす行列を返す(V * V)
    O(|V|**3)
    ネスト深くならないバージョン
    """
    mat = adj_mat.copy()
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if mat[i][j] > mat[i][k] + mat[k][j]:
                    return -1
                elif mat[i][j] == mat[i][k] + mat[k][j] and i != k and k != j:
                    is_need[i][j] = 0
                
    return mat

adj = warshall_floyd(A)
if adj == -1:
    print(-1)
else:
    ans = 0
    for i in range(N):
        for j in range(N):
            if is_need[i][j]:
                ans += A[i][j]
    print(ans//2)

Submission status: Accepted

Solution code:
from numpy import *
N = int(input())
A = array([list(map(int,input().split())) for n in range(N)])
ans = 0

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

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

print(ans)

Submission status: Accepted

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

N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
A2 = [[0]*N for _ in range(N)]
for i in range(N):
    for j in range(N):
        A2[i][j] = A[i][j]
for k in range(N):
    for i in range(N):
        for j in range(N):
            A2[i][j] = min(A2[i][j], A2[i][k]+A2[k][j])
ok = True
for i in range(N):
    for j in range(N):
        if A[i][j] != A2[i][j]:
            ok = False
if not ok:
    print(-1)
    exit()
ans = 0
for i in range(N):
    for j in range(N):
        connected = True
        for k in range(N):
            if i == k or j == k: continue
            if A[i][j] == A[i][k]+A[k][j]:
                connected = False
                break
        if connected:
            ans += A[i][j]
print(ans//2)