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:
from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph)
#from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul,itemgetter
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
#input=sys.stdin.readline  #危険！基本オフにしろ！
sys.setrecursionlimit(10**8)


def main():
    n=int(input())
    grid=[list(map(int,input().split()))for i in range(n)]
    p=shortest_path(csgraph=csr_matrix(grid))
    q=[list(i) for i in p]
    
    if q!=grid:
        print(-1)
    else:
        for i in range(n):
            p[i][i]=float("inf")
        ans=0
        #print(p)
        for i in range(n):
            for j in range(i):
                if p[i][j]<min(p[i])+min(p[j]):
                    ans+=p[i][j]
        print(int(ans))




if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
As =[list(map(int, input().split())) for _ in range(N)]
flag1 = False
ans = 0
for i in range(N):
    for j in range(i+1, N):
        flag2 = True
        for k in range(N):
            if k == i or k == j:
                continue
            if As[i][k]+As[k][j] < As[i][j]:
                flag1 = True
                break
            elif As[i][k]+As[k][j] == As[i][j]:
                flag2 = False
        if flag2:
            ans += As[i][j]
        if flag1:
            break
    if flag1:
        break
if not flag1:
    print(ans)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import sys

import numpy as np

sys.setrecursionlimit(10000)
INF = float('inf')

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

A = np.array(A)


def solve():
    # 消していいやつ
    useless = np.zeros((N, N), dtype=bool)

    # 1 つ経由するのだけ考えれば OK
    for st, en in itertools.combinations(range(N), r=2):
        for via in range(N):
            if via in [st, en]:
                continue
            if A[st, via] + A[via, en] < A[st, en]:
                return -1
            if A[st, via] + A[via, en] == A[st, en]:
                useless[st, en] = True
                useless[en, st] = True

    return A[~useless].sum() // 2


print(solve())

Submission status: Time Limit Exceeded

Solution code:
import sys, math, collections, heapq, itertools
F = sys.stdin
def single_input(): return F.readline().strip("\n")
def line_input(): return F.readline().strip("\n").split()
def gcd(a, b):
    a, b = max(a, b), min(a, b)
    while a % b > 0: a, b = b, a % b
    return b
  
def solve():
    N = int(single_input())
    A = [list(map(int, line_input())) for i in range(N)]
    for i in range(N):
        A[i][i] = 10 ** 15

    Total = 0
    possible = True
    for c in itertools.combinations(range(N), 2):
        a, b = int(c[0]), int(c[1])
        dist = A[a][b]
        for i in range(N):
            if A[a][i] + A[b][i] == dist: break
            elif A[a][i] + A[b][i] < dist:
                possible = False
                break
        else: Total += dist
        if not possible:
            print(-1)
            break
    else: print(Total)

    return 0
  
if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [list(map(int,input().split())) for _ in range(n)]
ans = 0
for i in range(n):
    for j in range(i,n):
        if i==j:
            continue
        dp = 10**9+1
        for k in range(n):
            if k==j or k==i:
                continue
            dp = min(dp,a[i][k]+a[k][j])
        if a[i][j]<dp:
            ans += a[i][j]
        elif a[i][j]>dp:
            print(-1)
            exit()
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
ans = 0
tmp = 0
inf = 10 ** 20
INF = float("INF")
eps = 1.0 / 10 ** 10
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]#WideIntPoint
def ws(): return sys.stdin.readline().split()
def i(): return int(sys.stdin.readline())
def s(): return input()
def vi(n): return [i() for _ in range(n)]
def vs(n): return [s() for _ in range(n)]#VerticalString
def mi(n): return [wi() for _ in range(n)]#MatrixInt
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]
n = int(input())
a = mi(n)

"""d = [[float("inf") for i in range(n + 1)] for i in range(n + 1)]
#d[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(n):
    for j in range(n):
        d[x][y] = z
        d[y][x] = z"""


def warshall_floyd(n,d):
    e = [[0 for i in range(n)] for i in range(n)]
    #d[i][j]: 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]:
                    print(-1)
                    exit()
                elif d[i][j] == d[i][k] + d[k][j] and i != j and i != k and j != k:
                    e[i][j] = float("INF")
    return (d, e)

##############################
b = warshall_floyd(n,a)[0]
c = warshall_floyd(n,a)[1]
ans = 0
for i in range(n):
    for j in range(n):
        if c[i][j] != float("INF"):
            ans += b[i][j]
ans = ans // 2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = []
for i in range(n):#h:高さ
    a.append([int(m) for m in input().split()])

"""d = [[float("inf") for i in range(n + 1)] for i in range(n + 1)]
#d[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(n):
    for j in range(n):
        d[x][y] = z
        d[y][x] = z"""


def warshall_floyd(n,d):
    e = [[0 for i in range(n)] for i in range(n)]
    #d[i][j]: 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]:
                    print(-1)
                    exit()
                elif d[i][j] == d[i][k] + d[k][j] and i != j and i != k and j != k:
                    e[i][j] = float("INF")
    return (d, e)

##############################
b = warshall_floyd(n,a)[0]
c = warshall_floyd(n,a)[1]
ans = 0
for i in range(n):
    for j in range(n):
        if c[i][j] != float("INF"):
            ans += b[i][j]
ans = ans // 2
print(ans)

Submission status: Time Limit Exceeded

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

INF = 10**9+10
E_list = [[] for _ in range((N*(N-1))//2)]
k = 0
for i in range(N):
    for j in range(i+1,N):
        E_list[k] = (A[i][j],i,j)
        k += 1
E_list.sort(key = lambda x:x[0])
B = [[INF]*N for _ in range(N)]
ans = 0
for l,i,j in E_list:
    l_min = INF
    Bi = B[i]
    Bj = B[j]
    for k in range(N):
        tmp = Bi[k]+Bj[k]
        if tmp < l_min:
            l_min = tmp
    if l > l_min:
        ans = -1
        break
    elif l < l_min:
        ans += l
    Bi[j] = l
    Bj[i] = l
print(ans)

Submission status: Time Limit Exceeded

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

INF = 10**9+10
E_list = [[] for _ in range((N*(N-1))//2)]
k = 0
for i in range(N):
    for j in range(i+1,N):
        E_list[k] = (A[i][j],i,j)
        k += 1
E_list.sort(key = lambda x:x[0])
B = [[INF]*N for _ in range(N)]
ans = 0
for l,i,j in E_list:
    l_min = INF
    Bi = B[i]
    Bj = B[j]
    for k in range(N):
        l_min = min(l_min,Bi[k]+Bj[k])
    if l > l_min:
        ans = -1
        break
    elif l < l_min:
        ans += l
    Bi[j] = l
    Bj[i] = l
print(ans)

Submission status: Time Limit Exceeded

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

INF = 10**9+10
E_list = []
for i in range(N):
    for j in range(i+1,N):
        E_list.append([A[i][j],i,j])
E_list.sort(key = lambda x:x[0])
B = [[INF]*N for _ in range(N)]
ans = 0
for l,i,j in E_list:
    l_min = INF
    Bi = B[i]
    Bj = B[j]
    for k in range(N):
        l_min = min(l_min,Bi[k]+Bj[k])
    if l > l_min:
        ans = -1
        break
    elif l < l_min:
        ans += l
    Bi[j] = l
    Bj[i] = l
print(ans)

Submission status: Time Limit Exceeded

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

INF = 10**9+10
E_list = []
for i in range(N):
    for j in range(i+1,N):
        E_list.append([A[i][j],i,j])
E_list.sort()
B = [[INF]*N for _ in range(N)]
ans = 0
for l,i,j in E_list:
    l_min = INF
    Bi = B[i]
    Bj = B[j]
    for k in range(N):
        l_min = min(l_min,Bi[k]+Bj[k])
    if l > l_min:
        ans = -1
        break
    elif l < l_min:
        ans += l
    Bi[j] = l
    Bj[i] = l
print(ans)

Submission status: Time Limit Exceeded

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

INF = 10**10
E_list = []
for i in range(N):
    for j in range(i+1,N):
        E_list.append([A[i][j],i,j])
E_list.sort()
B = [[INF]*N for _ in range(N)]
ans = 0
for l,i,j in E_list:
    l_min = INF
    for k in range(N):
        l_min = min(l_min,B[i][k]+B[k][j])
    if l > l_min:
        ans = -1
        break
    elif l < l_min:
        ans += l
    B[i][j] = l
    B[j][i] = l
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
import math
import copy

def main():
    # 文字列の2進数を数値にする
    # '101' → '5'
    # 文字列の頭に'0b'をつけてint()にわたす
    # binary = int('0b'+'101',0)

    # 2進数で立っているbitを数える
    # 101(0x5) → 2
    # cnt_bit = bin(5).count('1')
    
    # N! を求める
    # f = math.factorial(N)

    # N の逆元
    # N_inv = pow(N,MOD-2,MOD)

    # nCr
    # Nの階乗 * rの階乗の逆元 * n-rの階乗の逆元
    
    # 切り捨て
    # 4 // 3
    # 切り上げ
    #-(-4 // 3)
    
    # 初期値用:十分大きい数(100億)
    INF = float("inf")

    # 大きな素数
    MOD = 10**9+7
    
    # 1文字のみを読み込み
    # 入力:2
    # a = input().rstrip()
    # 変数:a='2'
    
    # スペース区切りで標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a, b, c, d = (int(_) for _ in input().split())  
    # 変数:a=2 b=4 c=5 d =7
    
    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a = list(int(_) for _ in input().split())
    # 変数:a = [2, 4, 5, 7]    

    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2457
    # a = list(int(_) for _ in input())
    # 変数:a = [2, 4, 5, 7]    
    N = int(input())
    a = []
    t_ans = {}
    ans = 0
    for i in range(N):
        a.append(list(int(_) for _ in input().split()))
    d = copy.deepcopy(a)
    
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if a[i][j] > a[i][k]+a[k][j]:
                    print(-1)
                    exit()
                elif a[i][j] == a[i][k]+a[k][j] and a[i][j] != 0 and k!=i and k!=j:
                    d[i][j] = 0
                    # if ((i,k) not in t_ans and (k,i) not in t_ans):
                    #     t_ans[i,k] = a[i][k]
                    # elif (i,k) in t_ans and t_ans[i,k] > a[i][k]:
                    #     t_ans[i,k] = a[i][k]
                    # elif (k,i) in t_ans and t_ans[k,i] > a[i][k]:
                    #     t_ans[i,k] = a[i][k]
                        
                    # if ((k,j) not in t_ans and (j,k) not in t_ans):
                    #     t_ans[k,j] = a[k][j]
                    # elif (k,j) in t_ans and t_ans[k,j] > a[k][j]:
                    #     t_ans[k,j] = a[k][j]
                    # elif (j,k) in t_ans and t_ans[j,k] > a[k][j]:
                    #     t_ans[j,k] = a[k][j]
    for i in range(N):
        ans += sum(d[i])
    print(ans//2)
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import heapq
INF = 10**10
n = int(input())
a = [[int(item) for item in input().split()] for _ in range(n)]
b = [[INF for _ in range(n)] for _ in range(n)]

ans = sum(map(sum, a)) // 2
for k in range(n):
    for i in range(n):
        for j in range(i, n):
            b[i][j] = min(b[i][j], a[i][k] + a[k][j])
            b[j][i] = b[i][j]
            if a[i][j] == a[i][k] + a[k][j] and j != k and i != k:
                ans -= a[i][j]

if a == b:
    print(ans)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import heapq
INF = 10**10
n = int(input())
a = [[int(item) for item in input().split()] for _ in range(n)]
b = [[INF for _ in range(n)] for _ in range(n)]

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

ans = sum(map(sum, a)) // 2
for k in range(n):
    for i in range(n):
        for j in range(i+1, n):
            if b[i][j] == a[i][k] + a[k][j] and j != k and i != k:
                ans -= b[i][j]
if a == b:
    print(ans)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import floyd_warshall as wf
n=int(input())
s=[list(map(float,input().split()))for i in range(n)]
a=wf(s,directed=False).tolist()
if s!=a:
    print(-1)
else:
    c=0
    for i in range(n):
        s[i][i]=float("inf")
    for i in range(n):
        for j in range(i):
            d=min(map(sum,zip(s[i],s[j])))
            if s[i][j]<d:
                c+=int(s[i][j])
    else:
        print(c)

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import floyd_warshall as wf
n=int(input())
s=[list(map(float,input().split()))for i in range(n)]
a=wf(s,directed=False).tolist()
if s!=a:
    print(-1)
else:
    c=0
    for i in range(n-1):
        for j in range(i+1,n):
            for d in range(n):
                if d!=i and d!=j:
                    if s[i][j]>=s[i][d]+s[d][j]:
                        break
            else:
                c+=int(s[i][j])
    else:
        print(c)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
dist=[list(map(int,input().split())) for i in range(N)]
ans=sum([sum(dist[i]) for i in range(N)])
ans//=2
was=set()
for i in range(N):
    if ans<0:break
    for j in range(i+1,N):
        if ans<0:break
        for k in range(j+1,N):
            a,b,c=dist[i][j],dist[i][k],dist[j][k]
            if b<a and c<a:
                M=a
                S=b+c
                check=(i,j)
            elif a<b and c<b:
                M=b
                S=a+c
                check=(i,k)
            elif a<c and b<c:
                M=c
                S=a+b
                check=(j,k)
            else:continue
            if S==M:
                if check in was:continue
                ans-=M
                was|={check,}
            elif S<M:
                ans=-1*float('inf')
                break
if ans<0:ans=-1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
dist=[list(map(int,input().split())) for i in range(N)]
ans=sum([sum(dist[i]) for i in range(N)])
ans//=2
for i in range(N):
    for j in range(i+1,N):
        for k in range(j+1,N):
            a,b,c=dist[i][j],dist[i][k],dist[j][k]
            if sum([a,b,c])/2==max(a,b,c):
                ans-=max(a,b,c)
            elif sum([a,b,c])/2<max(a,b,c):
                ans=-1*float('inf')
if ans<0:ans=-1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
dist=[list(map(int,input().split())) for i in range(N)]
ans=sum([sum(dist[i]) for i in range(N)])
ans//=2
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][k]+dist[j][k]==dist[i][j]:
                ans-=dist[i][j]
            elif dist[i][k]+dist[j][k]<dist[i][j]:
                ans=-1*float('inf')
if ans<0:ans=-1
print(ans)

Submission status: Time Limit Exceeded

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

D = [[True for i in range(N)] for j in range(N)]
flg=True
for i in range(N-2):
    for j in range(i+1,N-1):
        for k in range(j+1,N):
            if A[i][j]==A[j][k]+A[k][i]:
                D[i][j]=False
                D[j][i]=False
            if A[j][k]==A[i][j]+A[k][i]:
                D[j][k]=False
                D[k][j]=False
            if A[k][i]==A[i][j]+A[j][k]:
                D[k][i]=False
                D[i][k]=False
            if A[i][j]>A[j][k]+A[k][i] or A[j][k]>A[i][j]+A[k][i] or A[k][i]>A[i][j]+A[j][k]:
                flg=False
                #print(A[i][j],A[j][k],A[k][i])
                break

if flg:
    ans=0
    for i in range(N):
        for j in range(i+1,N):
           if D[i][j]:
               #print(i,j,A[i][j])
               ans+=A[i][j]
    print(ans)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys

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

    INF = float('INF')
    for i in range(N):
        A[i][i] = INF

    ans = 0
    for i in range(N):
        for j in range(i):
            #bipas = min(map(sum, zip(A[i], A[j])))
            bipas = 10**10
            for k in range(N):
                bipas = min(bipas, A[i][k] + A[j][k])

            if A[i][j] > bipas:
                ans = -1
                break
            elif A[i][j] < bipas:
                ans += A[i][j]

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

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

    INF = float('INF')
    for i in range(N):
        A[i][i] = INF

    ans = 0
    for i in range(N):
        for j in range(i):
            bipas = 10**9 + 1
            for k in range(N):
                bipas = min(bipas, A[i][k] + A[k][j])

            if A[i][j] > bipas:
                ans = -1
                break
            elif A[i][j] < bipas:
                ans += A[i][j]

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def restoring_road_network(N: int, A: list)->int:
    total = 0
    for i in range(N):
        for j in range(i+1, N):
            ok = True
            for k in range(N):
                if i == k or k == j:
                    continue
                if A[i][k] + A[k][j] < A[i][j]:
                    return -1
                if A[i][k] + A[k][j] == A[i][j]:
                    ok = False
            if ok:
                total += A[i][j]

    return total


if __name__ == "__main__":
    N = int(input())
    A = [[int(s) for s in input().split()] for _ in range(N)]
    ans = restoring_road_network(N, A)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
    def __init__(self, size: int):
        self.__size = size
        self.__root = [-1] * size

    def find(self, x: int)->int:
        if self.__root[x] < 0:
            return x

        root = self.find(self.__root[x])
        self.__root[x] = root
        return root

    def union(self, x: int, y: int):
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return

        if self.__root[ry] < self.__root[rx]:
            rx, ry = ry, rx

        self.__root[rx] += self.__root[ry]
        self.__root[ry] = rx

    def same(self, x: int, y: int)->bool:
        return self.find(x) == self.find(y)


def kruskal(V: int, edges: list)->list:
    uf = UnionFind(V)

    new_edges = []
    for u, v, c in sorted(edges, key=lambda x: x[2]):
        if not uf.same(u, v):
            new_edges.append((u, v, c))
            uf.union(u, v)
    return new_edges


def restoring_road_network(N: int, A: list)->int:
    total = 0
    for i in range(N):
        for j in range(i+1, N):
            ok = True
            for k in range(N):
                if A[i][k] + A[k][j] < A[i][j]:
                    return -1
                if i == k or k == j:
                    continue
                if A[i][k] + A[k][j] == A[i][j]:
                    ok = False
            if ok:
                total += A[i][j]

    return total


if __name__ == "__main__":
    N = int(input())
    A = [[int(s) for s in input().split()] for _ in range(N)]
    ans = restoring_road_network(N, A)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
num = 0
for i in range(N):
    for j in range(i + 1, N):
        s = A[i][j]
        use = True
        for k in range(N):
            if k == i or k == j:
                continue
            t = A[i][k] + A[k][j]
            if t < s:
                print(-1)
                exit()
            if t == s:
                use = False
        if use:
            num += s
print(num)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
B = [a[:] for a in A]
for k in range(N):
    for i in range(N):
        if i == k:
            continue
        for j in range(i + 1, N):
            if j == k:
                continue
            s = A[i][j]
            t = A[i][k] + A[k][j]
            if t < s:
                print(-1)
                exit()
            if t == s:
                B[i][j] = 0
print(sum([sum([B[i][j] for j in range(i + 1, N)]) for i in range(N)]))

Submission status: Time Limit Exceeded

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

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

memo = {}
for i in range(n):
  memo[i] = {}
for k in range(n):
  for i in range(n):
    for j in range(n):
      if k != i and i != j 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]:
          if j not in memo[i]:
            ans -= a[i][j]
            memo[i][j] = 1
                  
print(ans//2)

#プリム法
#mincost = [float("inf")]*n
#used = [False]*n
#mincost[0] = 0
#res = 0
#
#while True:
#  v = -1
#  for u in range(n):
#    if (not used[u]) and (v == -1 or mincost[u] < mincost[v]):
#      v = u
#  if v == -1:
#    break
#  used[v] = True
#  res += mincost[v]
#  for u in range(n):
#    mincost[u] = min(mincost[u],a[v][u])

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A

#B

#C
"""
a,b,c,d,e,f = LI()
a *= 100
b *= 100
ans = [a,0]
for i in range(f//a+1):
    for j in range((f-a*i)//b+1):
        for k in range((f-a*i-b*j)//c+1):
            for l in range((f-a*i-b*j-c*k)//d+1):
                if i or j or k or l:
                    s = c*k+d*l
                    w = a*i+b*j
                    q = w*e//100
                    if s <= q:
                        if w+s <= f:
                            if ans[1]/ans[0] < s/(s+w):
                                ans = [w+s,s]
print(*ans)
"""

#D
n = I()
a = LIR(n)
d = [[a[i][j] for i in range(n)] for j in range(n)]
l = [[[i] for j in range(n)] for i in range(n)]
for k in range(n):
    for i in range(n):
        for j in range(n):
            if d[i][j] >= d[i][k]+d[k][j]:
                d[i][j] = d[i][k]+d[k][j]
                l[i][j] = l[i][k]+l[k][j]
if a != d:
    print(-1)
    quit()
ans = 0
for i in range(n):
    for j in range(n):
        if len(l[i][j]) == 4:
            ans += d[i][j]
ans //= 2
print(ans)
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A

#B

#C
"""
a,b,c,d,e,f = LI()
a *= 100
b *= 100
ans = [a,0]
for i in range(f//a+1):
    for j in range((f-a*i)//b+1):
        for k in range((f-a*i-b*j)//c+1):
            for l in range((f-a*i-b*j-c*k)//d+1):
                if i or j or k or l:
                    s = c*k+d*l
                    w = a*i+b*j
                    q = w*e//100
                    if s <= q:
                        if w+s <= f:
                            if ans[1]/ans[0] < s/(s+w):
                                ans = [w+s,s]
print(*ans)
"""

#D
n = I()
a = LIR(n)
d = [[a[i][j] for i in range(n)] for j in range(n)]
l = [[[i] for j in range(n)] for i in range(n)]
for k in range(n):
    for i in range(n):
        for j in range(n):
            if d[i][j] >= d[i][k]+d[k][j]:
                d[i][j] = d[i][k]+d[k][j]
                l[i][j] = l[i][k]+l[k][j]
if a != d:
    print(-1)
    quit()
ans = 0
for i in range(n):
    for j in range(n):
        l[i][j] = list(set(l[i][j]))
        if len(l[i][j]) == 2:
            ans += d[i][j]
ans //= 2
print(ans)
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Time Limit Exceeded

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

def calc():
    ans=0
    for i in range(N):
        for j in range(N):
            used=True
            for k in range(N):
                if i==k or k==j:continue
                if A[i][j]>A[i][k]+A[k][j]:
                    return -1
                elif A[i][j]==A[i][k]+A[k][j]:
                    used=False
            if used:
                ans+=A[i][j]
    return ans//2
                
print(calc())

Submission status: Time Limit Exceeded

Solution code:
def warshall_floyd(n,graph):
    dist = [[0 for i in range(n)] for k in range(n)]
    for i in graph:
        for k in range(len(graph[i])):
            dist[i-1][graph[i][k][0]-1] = graph[i][k][1] #頂点iから頂点kに移動する時の値
    

    for i in range(n): #経由
        for k in range(n): #始点
            for j in range(n): #終点
                dist[k][j] = min(dist[k][j],dist[k][i]+dist[i][j])
    return dist


n = int(input())
graph = dict()
for i in range(1,n+1):
    graph[i] = []
data = []
ans = 0
for i in range(n):
    a = list(map(int,input().split()))
    data.append(a)
    for k in range(i+1,n):
        ans += 2*a[k]
        graph[i+1].append([k+1,a[k]])
        graph[k+1].append([i+1,a[k]])

theorical = warshall_floyd(n,graph)

if theorical != data:
    print("-1")
else:
    for i in range(n): #始点
        for k in range(n): #終点
            for j in range(n): #経由
                if i != j and k != j and theorical[i][k] == theorical[i][j] + theorical[j][k]:
                    ans -= theorical[i][k]
                    break
    print(ans//2)

Submission status: Time Limit Exceeded

Solution code:
import heapq
N = int( input())
A = [ list( map( int, input().split())) for _ in range(N)]
Q = []
for i in range(N-1):
    for j in range(i+1,N):
        heapq.heappush(Q, [A[i][j],i,j])
WF = [ [10**9+1]*N for _ in range(N)]
for i in range(N):
    WF[i][i] = 0
cnt = 0
while Q:
    a, s, g = heapq.heappop(Q)
    addcheck = 1
    for i in range(N):
        if i == s or i == g:
            continue
        else:
            if WF[s][i] + WF[i][g] == a:
                addcheck = 0
            elif WF[s][i] + WF[i][g] < a:
                 break
    else:
        WF[s][g] = a
        WF[g][s] = a
        if addcheck:
            cnt += a
        continue
    print(-1)
    break
else:
    print( cnt)

Submission status: Time Limit Exceeded

Solution code:
INF = 10 ** 20
n = int(input())
edges = [list(map(int, input().split())) for _ in range(n)]
dist = [[INF] * n for _ in range(n)]

edgeList = []
for i in range(n):
    for j in range(i, n):
        edgeList.append((edges[i][j], i, j))
edgeList.sort()

for k in range(n):
    for i in range(n):
        for j in range(n):
            dist[i][j] = min(dist[i][j], edges[i][k] + edges[k][j])
ans = 0
for c, i, j in edgeList:
    minCost = min([dist[i][k] + dist[k][j] for k in range(n) if (k != i and k != j)] + [INF])
    if c > minCost:
        print(-1)
        break
    if c < minCost:
        ans += c
else:
    print(ans)