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:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


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


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):
    EC = []
    for i, r in enumerate(A):
        for j, c in enumerate(r):
            if c == 0:
                break
            EC.append((c, i, j))

    EC.sort()
    ans = 0
    for c, i, j in EC:
        q = [(0, i)]
        min_path = c
        f = True
        while q:
            c2, k = q.pop()
            if k != i and c2 + A[k][j] <= min_path:
                min_path = c2 + A[k][j]
                f = False
            else:
                for l, c3 in enumerate(A[k]):
                    if c3 != 0 and c2 + c3 < c:
                        q.append((c2 + c3, l))

        if min_path != c:
            return -1
        elif f:
            ans += c
    return ans


def main():
    N = read_int()
    A = [read_int_n() for _ in range(N)]

    print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import copy
import numpy as np

N = int(input())
A = np.asarray([[int(Aij) for Aij in input().split()] for _ in range(N)])

def warshall_floyd(D):
    for i in range(N):
        for j in range(i + 1, N):
            for k in range(N):
                D[j][k] = min(D[j][k], D[j][i] + D[i][k])
    return D

A2 = warshall_floyd(copy.deepcopy(A))

if np.any(A != A2):
    print(-1)
else:
    d = 0
    A += np.diag([2*10**9] * N)
    for i in range(N):
        for j in range(i + 1, N):
            if np.min(A[i] + A[j]) != A[i, j]:
                d += A[i, j]
    print(d)

Submission status: Time Limit Exceeded

Solution code:
import copy
N = int(input())
A = [[int(Aij) for Aij in input().split()] for _ in range(N)]

n = len(A)
d = 0
for i in range(n):
    for j in range(i + 1, n):
        flag = True
        for k in range(n):
            if i == k or j == k:
                continue
            if A[i][k] + A[k][j] < A[i][j]:
                print('-1')
                exit()
            elif A[i][k] + A[k][j] == A[i][j]:
                flag = False
                break
        if flag:
            d += A[i][j]
print(d)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = []
for i in range(N):
  A.append([int(x) for x in input().split()])
B = [[True for i in range(N)] for j in range(N)]
A_sum = 0
for i in range(N):
  for j in range(N):
    for k in range(N):
      if i != k and j != k:
        if A[i][j] > (A[i][k] + A[k][j]):
          A_sum = -2
          break
        elif A[i][j] == (A[i][k] + A[k][j]):
          B[i][j] = False
          B[j][i] = False
if A_sum >= 0:
  for i in range(N):
    for j in range(N):
      if B[i][j]:
        A_sum += A[i][j]
print(A_sum // 2)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = []
for i in range(N):
  A.append([int(x) for x in input().split()])
B = [[True for i in range(N)] for j in range(N)]
A_sum = 0
for i in range(N):
  for j in range(N):
    for k in range(N):
      if i != k and j != k:
        if A[i][j] > (A[i][k] + A[k][j]):
          A_sum = -2
        if A[i][j] == (A[i][k] + A[k][j]):
          B[i][j] = False
          B[j][i] = False
if A_sum >= 0:
  for i in range(N):
    for j in range(N):
      if B[i][j]:
        A_sum += A[i][j]
print(A_sum // 2)

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-1):
    for j in range(i+1, N):
        direct = A[i][j]
        for k in range(N):
            if k == i or k == j:
                continue
            ind = A[i][k] + A[k][j]
            if direct > ind:
                print(-1)
                exit()
            elif direct == ind:
                break
        else:
            ans += direct
print(ans)

Submission status: Time Limit Exceeded

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

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])

if A!=B:
    print(-1)
else:
    for i in range(N):
        for j in range(i+1,N):
            exists = True
            for k in range(N):
                if k not in (i,j) and B[i][j]==B[i][k]+B[k][j]:
                    exists = False                    
            if exists:
                Ans += B[i][j]
    print(Ans)

Submission status: Time Limit Exceeded

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

INF = float('inf')
shortest = [[INF]*N for i in range(N)]

ans = 0
for k in range(N):
    for i in range(N):
        for j in range(N):
            if Map[i][k] == 0 or Map[k][j] == 0:
                continue

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

            elif Map[i][k] + Map[k][j] == Map[i][j]:
                ans -= Map[i][j]

for m in Map:
    ans += sum(m)

print(ans // 2)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

def printMatrix(A):
  for i in range(N):
    for j in range(N):
      print(str(A[i][j]) + " ", end = '')
    print("")


N = int(input())
A = [np.array(input().split(), dtype=np.int64) for _ in range(N)]
B = [[False] * N for _ in range(N)] # not exist

inf = 0xFFFFFFFF

for i in range(N):
    A[i][i] = inf

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

      if A[i][j] == A[i][k] + A[k][j]:
        #print(str(i) + " " + str(j) + " " + str(k))
        B[i][j] = B[j][i] = True
      if A[i][j] > A[i][k] + A[k][j]:
        #print(str(i) + " " + str(j) + " " + str(k))
        print(-1)
        sys.exit()
      A[i][j] = min(A[i][j], A[i][k] + A[k][j])
      #printMatrix(A)
      #print()

#printMatrix(B)

sum = 0
for i in range(N):
  for j in range(i + 1, N):
    if not B[i][j]:
      sum += A[i][j]

print(sum)

Submission status: Time Limit Exceeded

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

ans = 0
for i in range(n):
    for j in range(i+1,n):
        found = True
        for k in range(n):
            if k == i or k == j: continue
            compound = a[i][k] + a[k][j]
            if a[i][j] == compound:
                found = False
                continue
            if a[i][j] > compound:
                print(-1)
                exit()
        if found:
            ans += a[i][j]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=input()
cost={}

org=[[float("inf") for i in range(N)] for _ in range(N)]
for i in range(N):
	A=map(int, raw_input().split())
	for j in range(N):
		org[i][j]=A[j]
		if j>i:
			cost[(i,j)]=A[j]


for param in range(-1,len(cost)-N+1):

	cost_sel=sorted(cost.items(), key=lambda x: x[1])[:N+param]

	#Initialize
	dp=[[float("inf") for i in range(N)] for _ in range(N)]
	for i in range(N): dp[i][i]=0

	for i,j in cost_sel:
		dp[i[0]][i[1]]=j
		dp[i[1]][i[0]]=j

	#Warshall-Floyd
	for k in range(N):
		for x in range(N):
			for y in range(N):
				dp[x][y]=min(dp[x][y], dp[x][k]+dp[k][y])

	#print dp
	if org==dp:
		print sum( [x[1] for x in cost_sel] )
		quit()
else:
	print -1

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [[] for _ in range(N)]
E = [[0]*(N) for _ in range(N) ]

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

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

			if A[i][j] == A[i][k] + A[k][j]:
				E[i][k] = E[k][i] = E[k][j] = E[j][k] = 1
				flag = 1

			elif A[i][j] > A[i][k] + A[k][j]:
				print(-1)
				exit(0)

			else:
				pass

		if flag == 0:
			E[i][j] = E[j][i] = 1


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

print(ans//2)

Submission status: Time Limit Exceeded

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

#check
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(0)

ans = 0
for i in range(N):
    for j in range(i+1, N):
        isNeighbor = True
        for k in range(N):
            if i == k or j == k:
                continue
            if A[i][j] == A[i][k] + A[k][j]:
                isNeighbor = False
        if isNeighbor:
            ans += A[i][j]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy

n = int(input())

a = [[] for i in range(n)]
a2 = [[] for i in range(n)]


for i in range(n):
    a[i] = list(map(int, input().split(' ')))
    a2[i] = copy.deepcopy(a[i])

flag = False


for i in range(n):
    for j in range(n-i-1):
        j = n - j -1
        for k in range(n):
            if k == i or k == j:
                continue
            if a[i][j] > a[i][k]+a[k][j]:
                print(-1)
                flag = True
                break
            elif a[i][j] == a[i][k]+a[k][j]:
                a2[i][j] = 0
                a2[j][i] = 0

        if flag:break
    if flag:break

sumr = 0

if flag is False:
    for i in a2:
        sumr += sum(i)
    print(sumr//2)

Submission status: Time Limit Exceeded

Solution code:
import copy

n = int(input())

a = [[] for i in range(n)]
a2 = [[] for i in range(n)]


for i in range(n):
    a[i] = list(map(int, input().split(' ')))
    a2[i] = copy.deepcopy(a[i])

flag = False


for i in range(n):
    for j in range(n):
        for k in range(n):
            if k == i or k == j:
                continue
            if a[i][j] > a[i][k]+a[k][j]:
                print(-1)
                flag = True
                break
            elif a[i][j] == a[i][k]+a[k][j]:
                a2[i][j] = 0

        if flag:break
    if flag:break

sumr = 0

if flag is False:
    for i in a2:
        sumr += sum(i)
    print(sumr//2)

Submission status: Time Limit Exceeded

Solution code:
import sys
N = int(input())

#graph = [[0 for i in range(N)] for j in range(N)]
graph = []
for i in range(N):
    graph.append(list(map(int,input().split())))
flag = 0
ans = 0
for i in range(N):
    for j in range(i+1,N):
        wei = 0
        for k in range(N):
            if graph[i][k] + graph[k][j] < graph[i][j]:
                flag = 1
            if i!=k and j!=k and graph[i][k] + graph[k][j] == graph[i][j]:
                wei = 1
        if wei == 0:
            ans += graph[i][j]

if flag == 0:
    print(ans)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    a = [[0]*n for _ in range(n)]
    wf = [[0]*n for _ in range(n)]
    ret = 0
    for i in range(n):
        l = list(map(int,input().split()))
        for j in range(n):
            a[i][j] = l[j]
            wf[i][j] = l[j]

    for k in range(n):
        for i in range(n):
            for j in range(n):
                if wf[i][j] > wf[i][k] + wf[k][j]:
                    wf[i][j] = wf[i][k] + wf[k][j]

    for i in range(n):
        for j in range(n):
            for k in range(n):
                if wf[i][j] < a[i][j]: return -1
                if i==k or j==k : continue
                if wf[i][j] == wf[i][k] + wf[k][j]: break
            else: ret += wf[i][j]

    return ret//2
print(main())

Submission status: Time Limit Exceeded

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

ret = 0
for i in range(V):
    for j in range(i+1, V):
        f = True
        for k in range(V):
            if i == k or j == k:
                continue
            if A[i][j] > A[i][k] + A[k][j]:
                print(-1)
                exit()
            elif A[i][j] == A[i][k] + A[k][j]:
                f = False
        if f:
            ret += A[i][j]

print(ret)

Submission status: Time Limit Exceeded

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

ret = 0
for i in range(V):
    for j in range(i+1, V):
        f = True
        for k in range(V):
            if i == k or j == k:
                continue
            if A[i][j] > A[i][k] + A[k][j]:
                print(-1)
                exit()
            elif A[i][j] == A[i][k] + A[k][j]:
                f = False
        if f:
            ret += A[i][j]

print(ret)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [list(map(int,input().split())) for i in range(N)]
flag1 = 0
length = 0
for i in range(N):
	for j in range(i+1,N):
		flag2 = 0
		for k in range (N):
			if A[i][j] > A[i][k]+A[k][j] :
				flag1 = 1
				break
			elif A [i][j] == A[i][k]+A[k][j]:
				if k != i and k != j:
					flag2 = 1
		if flag2 == 0:
			length += A[i][j]
if flag1 == 1:
	print(-1)
else:
	print(length)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [list(map(int,input().split())) for i in range(N)]
flag1 = 0
length = 0
for i in range(N):
	for j in range(i+1,N):
		flag2 = 0
		for k in range (N):
			if A[i][j] > A[i][k]+A[k][j] :
				flag1 = 1
			elif A [i][j] == A[i][k]+A[k][j] and k != i and k != j:
				flag2 = 1
		if flag2 == 0:
			length += A[i][j]
if flag1 == 1:
	print(-1)
else:
	print(length)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [list(map(int,input().split())) for i in range(N)]
flag1 = 0
length = 0
for i in range(N):
	for j in range(i+1,N):
		flag2 = 0
		for k in range (N):
			if A[i][j] > A[i][k]+A[k][j] :
				flag1 = 1
				break
			elif A [i][j] == A[i][k]+A[k][j] and k != i and k != j:
				flag2 = 1
		if flag2 == 0:
			length += A[i][j]
if flag1 == 1:
	print(-1)
else:
	print(length)

Submission status: Time Limit Exceeded

Solution code:
def Warshall_Floyd(edges,N):
  import copy
  d=copy.deepcopy(edges)
  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

import sys
N=int(input())
A=[list(map(int,input().split())) for i in range(N)]
B=Warshall_Floyd(A,N)
if A!=B:
  print(-1)
  sys.exit()

ans=0
for i in range(N):
  for j in range(i):
    need=1
    for k in range(N):
      if k!=i and k!=j:
        if A[i][j]==A[i][k]+A[k][j]: need=0
    ans+=need*A[i][j]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def Warshall_Floyd(edges,N):
  """頂点N個のグラフ上の隣接行列edges(空欄はinfとせよ)が与えられたとき, 
  2点間の最短距離距離を隣接行列で返す"""
  for k, i, j in itertools.product(range(N), range(N),range(N)):
    if edges[i][j]>edges[i][k]+edges[k][j]: return 1
  return 0
 
import sys
import itertools
N=int(input())
A=[list(map(int,input().split())) for i in range(N)]
if Warshall_Floyd(A,N):
  print(-1)
  sys.exit()
 
ans=0
for i, j in itertools.product(range(N),range(N)):
  need=1
  for k in range(N):
    if k!=i and k!=j and A[i][j]==A[i][k]+A[k][j]:
      need=0
      break
  if need:ans+=A[i][j]
print(ans//2)

Submission status: Time Limit Exceeded

Solution code:
def Warshall_Floyd(edges,N):
  """頂点N個のグラフ上の隣接行列edges(空欄はinfとせよ)が与えられたとき, 
  2点間の最短距離距離を隣接行列で返す"""
  for k, i, j in itertools.product(range(N), range(N),range(N)):
    if edges[i][j]>edges[i][k]+edges[k][j]: return 1
  return 0
 
import sys
import itertools
N=int(input())
A=[list(map(int,input().split())) for i in range(N)]
if Warshall_Floyd(A,N):
  print(-1)
  sys.exit()
 
ans=0
for i in range(N):
  for j in range(i):
    need=1
    for k in range(N):
      if k!=i and k!=j and A[i][j]==A[i][k]+A[k][j]:
        need=0
        break
    if need:ans+=A[i][j]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
N=int(input())
edges=[list(map(int,input().split())) for i in range(N)]
ans=0
for k, i, j in itertools.product(range(N), range(N),range(N)):
  #Xの10通り、Yの10通りの全組み合わせ
  if edges[i][j]>edges[i][k]+edges[k][j]:
    print(-1)
    sys.exit()
  if k==0:
    need=1
    for l in range(N):
      if l!=i and l!=j and edges[i][j]==edges[i][l]+edges[l][j]:
        need=0
        break
    if need:ans+=edges[i][j]
        
print(ans//2)

Submission status: Time Limit Exceeded

Solution code:
import sys
from sys import stdin
input = stdin.readline
N=int(input())
edges=[list(map(int,input().split())) for i in range(N)]
ans=0
for k in range(N):
  for i in range(N):
    for j in range(i):
      if edges[i][j]>edges[i][k]+edges[k][j]:
        print(-1)
        sys.exit()
      if k==0:
        need=1
        for l in range(N):
          if l!=i and l!=j and edges[i][j]==edges[i][l]+edges[l][j]:
            need=0
            break
        if need:ans+=edges[i][j]
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def Warshall_Floyd(edges,N):
  """頂点N個のグラフ上の隣接行列edgesが与えられたとき, 
  2点間の最短距離距離を隣接行列で返す"""
  import copy
  d=copy.deepcopy(A)
  for k in range(N):
    for i in range(N):
      for j in range(i):
        if d[i][j]>d[i][k]+d[k][j]: return 1
  return 0
 
import sys
from sys import stdin
input = stdin.readline
N=int(input())
A=[list(map(int,input().split())) for i in range(N)]
if Warshall_Floyd(A,N):
  print(-1)
  sys.exit()
 
ans=0
for i in range(N):
  for j in range(i):
    need=1
    for k in range(N):
      if k!=i and k!=j:
        if A[i][j]==A[i][k]+A[k][j]:
          need=0
          break
    ans+=need*A[i][j]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def Warshall_Floyd(edges,N):
  """頂点N個のグラフ上の隣接行列edges(空欄はinfとせよ)が与えられたとき, 
  2点間の最短距離距離を隣接行列で返す"""
  for k in range(N):
    for i in range(min(70,N)):
      for j in range(i):
        if edges[i][j]>edges[i][k]+edges[k][j]: return 1
  return 0
 
import sys
from sys import stdin
input = stdin.readline
N=int(input())
A=[list(map(int,input().split())) for i in range(N)]
if Warshall_Floyd(A,N):
  print(-1)
  sys.exit()
 
ans=0
for i in range(N):
  for j in range(i):
    need=1
    for k in range(N):
      if k!=i and k!=j and A[i][j]==A[i][k]+A[k][j]:
        need=0
        break
    if need:ans+=A[i][j]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def Warshall_Floyd(edges,N):
  """頂点N個のグラフ上の隣接行列edges(空欄はinfとせよ)が与えられたとき, 
  2点間の最短距離距離を隣接行列で返す"""
  for k in range(N):
    for i in range(min(100,N)):
      for j in range(i):
        if edges[i][j]>edges[i][k]+edges[k][j]: return 1
  return 0
 
import sys
from sys import stdin
input = stdin.readline
N=int(input())
A=[list(map(int,input().split())) for i in range(N)]
if Warshall_Floyd(A,N):
  print(-1)
  sys.exit()
 
ans=0
for i in range(N):
  for j in range(i):
    need=1
    for k in range(N):
      if k!=i and k!=j and A[i][j]==A[i][k]+A[k][j]:
        need=0
        break
    if need:ans+=A[i][j]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def Warshall_Floyd(edges,N):
  """頂点N個のグラフ上の隣接行列edges(空欄はinfとせよ)が与えられたとき, 
  2点間の最短距離距離を隣接行列で返す"""
  for k in range(N):
    for i in range(N):
      for j in range(min(i,200)):
        if edges[i][j]>edges[i][k]+edges[k][j]: return 1
  return 0
 
import sys
from sys import stdin
input = stdin.readline
N=int(input())
A=[list(map(int,input().split())) for i in range(N)]
if Warshall_Floyd(A,N):
  print(-1)
  sys.exit()
 
ans=0
for i in range(N):
  for j in range(i):
    need=1
    for k in range(N):
      if k!=i and k!=j and A[i][j]==A[i][k]+A[k][j]:
        need=0
        break
    if need:ans+=A[i][j]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def Warshall_Floyd(edges,N):
  """頂点N個のグラフ上の隣接行列edges(空欄はinfとせよ)が与えられたとき, 
  2点間の最短距離距離を隣接行列で返す"""
  for k in range(N):
    for i in range(N):
      for j in range(i):
        if edges[i][j]>edges[i][k]+edges[k][j]: return 1
  return 0
 
import sys
from sys import stdin
input = stdin.readline
N=int(input())
A=[list(map(int,input().split())) for i in range(N)]
if Warshall_Floyd(A,N):
  print(-1)
  sys.exit()
 
ans=0
for i in range(N):
  for j in range(i):
    need=1
    for k in range(N):
      if k!=i and k!=j and A[i][j]==A[i][k]+A[k][j]:
        need=0
        break
    if need:ans+=A[i][j]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def Warshall_Floyd(edges,N):
  """頂点N個のグラフ上の隣接行列edges(空欄はinfとせよ)が与えられたとき, 
  2点間の最短距離距離を隣接行列で返す"""
  for k in range(N):
    for i in range(N):
      for j in range(i):
        if edges[i][j]>edges[i][k]+edges[k][j]: return 1
  return 0
 
import sys
from sys import stdin
input = stdin.readline
N=int(input())
A=[list(map(int,input().split())) for i in range(N)]
if Warshall_Floyd(A,N):
  print(-1)
  sys.exit()
 
ans=0
for i in range(N):
  for j in range(i):
    need=1
    for k in range(N):
      if k!=i and k!=j:
        if A[i][j]==A[i][k]+A[k][j]:
          need=0
          break
    ans+=need*A[i][j]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def Warshall_Floyd(edges,N):
  """頂点N個のグラフ上の隣接行列edges(空欄はinfとせよ)が与えられたとき, 
  2点間の最短距離距離を隣接行列で返す"""
  for k in range(N):
    for i in range(N):
      for j in range(i):
        if A[i][j]>A[i][k]+A[k][j]: return 1
  return 0
 
import sys
from sys import stdin
input = stdin.readline
N=int(input())
A=[list(map(int,input().split())) for i in range(N)]
if Warshall_Floyd(A,N):
  print(-1)
  sys.exit()
 
ans=0
for i in range(N):
  for j in range(i):
    need=1
    for k in range(N):
      if k!=i and k!=j:
        if A[i][j]==A[i][k]+A[k][j]:
          need=0
          break
    ans+=need*A[i][j]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def Warshall_Floyd(edges,N):
  """頂点N個のグラフ上の隣接行列edgesが与えられたとき, 
  2点間の最短距離距離を隣接行列で返す"""
  import copy
  d=copy.deepcopy(A)
  for k in range(N):
    for i in range(N):
      for j in range(i):
        d[i][j]=min(d[i][j],d[i][k]+d[k][j])
  return d
 
import sys
from sys import stdin
input = stdin.readline
N=int(input())
A=[list(map(int,input().split())) for i in range(N)]
B=Warshall_Floyd(A,N)
if A!=B:
  print(-1)
  sys.exit()
 
ans=0
for i in range(N):
  for j in range(i):
    need=1
    for k in range(N):
      if k!=i and k!=j:
        if A[i][j]==A[i][k]+A[k][j]:
          need=0
          break
    ans+=need*A[i][j]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def Warshall_Floyd(edges,N):
  """頂点N個のグラフ上の隣接行列edgesが与えられたとき, 
  2点間の最短距離距離を隣接行列で返す"""
  import copy
  d=copy.deepcopy(A)
  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
 
import sys
from sys import stdin
input = stdin.readline
N=int(input())
A=[list(map(int,input().split())) for i in range(N)]
B=Warshall_Floyd(A,N)
if A!=B:
  print(-1)
  sys.exit()
 
ans=0
for i in range(N):
  for j in range(i):
    need=1
    for k in range(N):
      if k!=i and k!=j:
        if A[i][j]==A[i][k]+A[k][j]:
          need=0
          break
    ans+=need*A[i][j]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def Warshall_Floyd(edges,N):
  """頂点N個のグラフ上の隣接行列edgesが与えられたとき, 
  2点間の最短距離距離を隣接行列で返す"""
  import copy
  d=copy.deepcopy(A)
  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
 
import sys
from sys import stdin
input = stdin.readline
N=int(input())
A=[list(map(int,input().split())) for i in range(N)]
B=Warshall_Floyd(A,N)
if A!=B:
  print(-1)
  sys.exit()
 
ans=0
for i in range(N):
  for j in range(i):
    need=1
    for k in range(N):
      if k!=i and k!=j:
        if A[i][j]==A[i][k]+A[k][j]: need=0
    ans+=need*A[i][j]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def Warshall_Floyd(edges,N):
  """頂点N個のグラフ上の隣接行列edgesが与えられたとき, 
  2点間の最短距離距離を隣接行列で返す"""
  import copy
  d=copy.deepcopy(A)
  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

import sys
N=int(input())
A=[list(map(int,input().split())) for i in range(N)]
B=Warshall_Floyd(A,N)
if A!=B:
  print(-1)
  sys.exit()

ans=0
for i in range(N):
  for j in range(i):
    need=1
    for k in range(N):
      if k!=i and k!=j:
        if A[i][j]==A[i][k]+A[k][j]: need=0
    ans+=need*A[i][j]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy
def solve():
    INF = float('inf')
    N = int(input())
    a = []
    for i in range(N):
        a.append(list(map(int, input().split())))
        flag = 0
        length = 0
        

    for i in range(N):
        for j in range(i+1, N):
            muda = 0
            for k in range(N):
                if k == i or k == j:
                    continue
                mix = a[i][k] + a[k][j]
                if a[i][j] > mix:
                    flag = 1
                    continue
                elif a[i][j] == mix:
                    muda = 1
                    continue
            if muda == 1:
                continue
            length += a[i][j]

    if (flag == 0):
        length = int(length)
    else:
        length = -1
    print(length)

solve()

Submission status: Time Limit Exceeded

Solution code:
import copy
INF = float('inf')
N = int(input())
a = []
for i in range(N):
    a.append(list(map(int, input().split())))
flag = 0
length = 0


for i in range(N):
    for j in range(i+1, N):
        muda = 0
        for k in range(N):
            if k == i or k == j:
                continue
            mix = a[i][k] + a[k][j]
            if a[i][j] > mix:
                flag = 1
                continue
            elif a[i][j] == mix:
                muda = 1
                continue
        if muda == 1:
            continue
        length += a[i][j]

if (flag == 0):
    length = int(length)
else:
    length = -1
print(length)

Submission status: Time Limit Exceeded

Solution code:
import copy
INF = float('inf')
N = int(input())
a = []
for i in range(N):
    a.append(list(map(int, input().split())))
flag = 0
length = 0


for i in range(N):
    for j in range(N):
        muda = 0
        for k in range(N):
            if k == i or k == j:
                continue
            mix = a[i][k] + a[k][j]
            if a[i][j] > mix:
                flag = 1
            elif a[i][j] == mix:
                muda = 1
        if muda == 1:
            continue
        length += a[i][j]

if (flag == 0):
    length = int(length/2)
else:
    length = -1
print(length)

Submission status: Time Limit Exceeded

Solution code:
import copy
INF = float('inf')
N = int(input())
a = []
for i in range(N):
    a.append(list(map(int, input().split())))
b = copy.deepcopy(a)
flag = 0
length = 0
muda = [[0 for col in range(N)] for row in range(N)]

for i in range(N):
    for j in range(N):
        for k in range(N):
            if k == i or k == j:
                continue
            mix = b[i][k] + b[k][j]
            if a[i][j] > mix:
                flag = 1
            elif a[i][j] == mix:
                muda[i][j] = 1
for i in range(N):
    for j in range(N):
        if muda[i][j] == 1:
            continue
        length += a[i][j]
if (flag == 0):
    length = int(length/2)
else:
    length = -1
print(length)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def solve():
    N = int(input())
    A = np.zeros((N,N))
    for i in range(N):
        line = list(map(int, input().split(' ')))
        for j in range(N):
            A[i][j] = line[j]
    D = np.copy(A) 
    for i in range(N):
        for j in range(N):
            for k in range(N):
                D[j][k] = min(D[j][k], D[j][i]+D[i][k])
    dis_sum = 0
    for i in range(N-1):
        for j in range(i+1, N):
            if D[i][j] != A[i][j]:
                return -1
            found = False
            for k in range(N):
                if k != i and k != j and D[i][j] == D[i][k] + D[k][j]:
                    found = True
                    break
            if not found:
                dis_sum += D[i][j]
    return int(dis_sum)

if __name__ == '__main__':
    print(solve())

Submission status: Time Limit Exceeded

Solution code:
def solve():
    N = int(input())
    A = []
    for i in range(N):
        A.append(list(map(int, input().split(' '))))
    D = [line[:] for line in A] 
    for i in range(N):
        for j in range(N):
            for k in range(N):
                D[j][k] = min(D[j][k], D[j][i]+D[i][k])
    dis_sum = 0
    for i in range(N-1):
        for j in range(i+1, N):
            if D[i][j] != A[i][j]:
                return -1
            found = False
            for k in range(N):
                if k != i and k != j and D[i][j] == D[i][k] + D[k][j]:
                    found = True
                    break
            if not found:
                dis_sum += D[i][j]
    return dis_sum

if __name__ == '__main__':
    print(solve())