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: Wrong Answer

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

exist = True
ans = 0
ls = []
for i in range(n - 1):
    for j in range(i + 1, n):
        ls.append((a[i][j], i, j))
ls.sort()
ds = [[1000000001 for _ in range(n)] for _ in range(n)]
for u in range(n):
    ds[u][u] = 0
for (d, u, v) in ls:
    use = True
    for w in range(n):
        if u == w or v == w:
            continue
        if a[u][v] == ds[u][w] + ds[w][v]:
            use = False
        elif ds[u][w] + ds[w][v] < a[u][v]:
            exist = False
    if use:
        ds[u][v] = d
        ds[v][u] = d
        for w in range(n):
            ds[u][w] = min(ds[u][w], d + ds[v][w])
            ds[w][u] = ds[u][w]
        ans += d
if not exist:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

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

exist = True
ans = 0
ls = []
for i in range(n - 1):
    for j in range(i + 1, n):
        ls.append((a[i][j], i, j))
ls.sort()
ds = [[1000000001 for _ in range(n)] for _ in range(n)]
for (d, u, v) in ls:
    use = True
    for w in range(n):
        if u == w or v == w:
            continue
        if a[u][v] == ds[u][w] + ds[w][v]:
            use = False
        elif ds[u][w] + ds[w][v] < a[u][v]:
            exist = False
    if use:
        ds[u][v] = d
        ds[v][u] = d
        ans += d

if not exist:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
import heapq


def dijkstra(graph, root, goal, limit):
    # print('dijkstra',root, goal, limit)
    # print(graph)
    dist = [float('inf')] * len(graph)
    dist[root] = 0
    q = [(0, root)]
    while q:
        d, v = heapq.heappop(q)
        # print(d,v)
        if dist[v] < d:
            continue
        limit_over = True
        for cost, target in graph[v]:
            # print(d,v, cost, target, dist)
            if dist[target] > dist[v] + cost:
                dist[target] = dist[v] + cost
                if target == goal:
                    return dist
                heapq.heappush(q, (dist[target], target))
                # print('heapq',q)
            if dist[v] + cost <= limit:
                limit_over = False
        if limit_over:
            # print('limit')
            return dist
    return dist

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

    h = []
    for i in range(n):
        for j in range(i+1, n):
            heapq.heappush(h, (a[i][j], i, j))

    graph = [[] for i in range(n)]
    total = 0
    while h:
        cost, s, t = heapq.heappop(h)
        dist = dijkstra(graph, s, t, cost)
        if dist[t] < cost:
            print(-1)
            exit()
        elif dist[t] > cost:
            total += cost
            graph[s].append((cost, t))
            graph[t].append((cost, s))
            dist = dijkstra(graph, s, t, cost)
            # print(total, s, t, cost)

    # print(*graph, sep = '\n')
    print(total)
        
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

class UnionFind:
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]

    def find(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self.find(self.table[x])
            return self.table[x]

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False

    def subsetall(self):
        a = []
        for i in range(len(self.table)):
            if self.table[i] < 0:
                a.append((i, -self.table[i]))
        return a

def main():
    n = I()
    a = [LI() for _ in range(n)]
    for i in range(n):
        ai = a[i]
        for j in range(i+1,n):
            aij = ai[j]
            aj = a[j]
            for k in range(n):
                if ai[k] + aj[k] < aij:
                    return -1

    r = 0
    ij = sorted(list(itertools.chain.from_iterable([[[a[i][j], i, j] for j in range(i+1,n)] for i in range(n)])))
    uf = UnionFind(n)
    aa = [[inf] * n for _ in range(n)]
    for i in range(n):
        aa[i][i] = 0
    for k,i,j in ij:
        if uf.union(i,j):
            aa[i][j] = aa[j][i] = k
            r += k
        elif aa[i][j] > k:
            f = True
            for l in range(n):
                if aa[l][i] + aa[l][j] <= k:
                    f = False
                    break
            if f:
                aa[i][j] = aa[j][i] = k
                r += k

    return r


print(main())

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

# ワーシャルフロイド法
# 全頂点間最短路
# d[i][j]は2頂点間i, j間の移動コストを格納, Mは頂点数

INF = float("inf")
import copy

def warshall_floyd(d):
    n = len(d)
    wf = copy.deepcopy(d)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                wf[i][j] = min(wf[i][j], wf[i][k] + wf[k][j])

    return wf #wf[i][j]に頂点i, j間の最短距離を格納

##############################

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

if d != warshall_floyd(d):
    print(-1)
else:
    ret = 0
    for i in range(n):
        for j in range(i+1,n):
            if i == j: continue
            ret += d[i][j]
            for mid in range(n):
                if mid in (i, j): continue
                if d[i][mid] + d[mid][j] == d[i][j]:
                    ret -= d[i][j]
                    break
    print(ret)

Submission status: Time Limit Exceeded

Solution code:
import itertools
N = int(input())
A = [[int(_) for _ in input().split()] for _ in range(N)]
ans = sum(sum(a) for a in A) // 2
seen = set()
for i in range(N):
    for j in range(i + 1, N):
        for k in range(N):
            if A[i][j] > A[i][k] + A[j][k]:
                print(-1)
                exit()
            elif k == i or i == j or j == k:
                continue
            elif A[i][j] == A[i][k] + A[j][k]:
                ans -= A[i][j]
                break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import floyd_warshall

N, *A = map(int, open(0).read().split())
A = list(zip(*[iter(A)] * N))

B = floyd_warshall(A, False).astype(int)

ans = 0
for i in range(N):
    for j in range(i + 1, N):
        if A[i][j] > B[i][j]:
            print(-1)
            quit()

        if A[i][j] == B[i][j] and all(B[i][j] != B[i][k] + B[k][j] for k in range(N) if k != i and k != j):
            ans += B[i][j]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
input=sys.stdin.buffer.readline
n=int(input())
d=[list(map(int,input().split())) for _ in range(n) ]
d=np.array(d)
#do a floyd warshall and test if something improves 
for k in range(n):
    for i in range(n):
        for j in range(i+1,n):
            if d[i][k]+d[k][j]<d[i][j]:
                print(-1)
                exit()
ans=0
for i in range(n):
    for j in range(i+1,n):
        flag=True
        for k in range(n):
            if k!=i and k!=j and d[i][k]+d[k][j]==d[i][j]:
                flag=False
        if flag:
            ans+=d[i][j]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.buffer.readline
n=int(input())
d=[list(map(int,input().split())) for _ in range(n) ]
#do a floyd warshall and test if something improves 
for k in range(n):
    for i in range(n):
        for j in range(i+1,n):
            if d[i][k]+d[k][j]<d[i][j]:
                print(-1)
                exit()
ans=0
for i in range(n):
    for j in range(i+1,n):
        flag=True
        for k in range(n):
            if k!=i and k!=j and d[i][k]+d[k][j]==d[i][j]:
                flag=False
        if flag:
            ans+=d[i][j]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
d=[list(map(int,input().split())) for _ in range(n) ]
#do a floyd warshall and test if something improves 
for k in range(n):
    for i in range(n):
        for j in range(i+1,n):
            if d[i][k]+d[k][j]<d[i][j]:
                print(-1)
                exit()
ans=0
for i in range(n):
    for j in range(i+1,n):
        flag=True
        for k in range(n):
            if k!=i and k!=j and d[i][k]+d[k][j]==d[i][j]:
                flag=False
        if flag:
            ans+=d[i][j]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
d=[list(map(int,input().split())) for _ in range(n) ]
#do a floyd warshall and test if something improves 
for k in range(n):
    for i in range(n):
        for j in range(n):
            if d[i][k]+d[k][j]<d[i][j]:
                print(-1)
                exit()
ans=0
for i in range(n):
    for j in range(n):
        flag=True
        for k in range(n):
            if k!=i and k!=j and i!=j and d[i][k]+d[k][j]==d[i][j]:
                flag=False
        if flag:
            ans+=d[i][j]
print(ans//2)

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import floyd_warshall
n = int(input())
d = [[10**14]*n for i in range(n)]
L = []
dist = []
for i in range(n):
    d[i][i] = 0
for i in range(n):
    L = list(map(int,input().split()))
    dist.append(L)
    for j in range(n):
        d[i][j] = L[j]
        d[j][i] = L[j]
d = floyd_warshall(d)
flag = True
for i in range(n):
  for j in range(n):
    if d[i][j] < dist[i][j]:
      flag = False
      break
if not flag:
  print(-1)
else:
  ans = 0
  for i in range(n):
    for k in range(n):
      for j in range(n):
        if i != k and k != j:
          if d[i][j] == d[i][k]+d[k][j]:
            ans += d[i][j]
  print(int((sum(sum(d))-ans)//2))

Submission status: Time Limit Exceeded

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

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

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

ans = 0
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 A[i][j] == A[i][k] + A[k][j]:  # 代替可能
                break
        else:
            ans += A[i][j]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
table=[]
for i in range(n):
  table.append([int(_) for _ in input().split()])
T=[[1]*n for i in range(n)]
import itertools
chk,ans=True,0
for Com in itertools.combinations(range(n),3):
  a,b,c=Com[0],Com[1],Com[2]
  lab,lbc,lca=table[a][b],table[b][c],table[c][a]
  if lab>=lbc and lab>=lca:
    if lab>lbc+lca:
      chk=False
    elif lab==lbc+lca:
      T[a][b],T[b][a]=0,0
  elif lbc>=lab and lbc>=lca:
    if lbc>lab+lca:
      chk=False
    elif lbc==lab+lca:
      T[b][c],T[c][b]=0,0
  elif lca>=lab and lca>=lbc:
    if lca>lab+lbc:
      chk=False
    elif lca==lab+lbc:
      T[c][a],T[a][c]=0,0
for i in range(n):
  for j in range(i+1,n):
    if T[i][j]==1:
      ans+=table[i][j]
print(ans if chk==True else -1)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

amap = [list(map(int, input().split())) for _ in range(n)]
isnt_const = False
cost = 0
for i in range(n):
  for j in range(i+1, n):
    isnt_add = False
    for k in range(n):
      if i == k or k == j:
        continue
      if amap[i][j] > amap[i][k] + amap[k][j]:
        isnt_const = True
        break
      elif amap[i][j] == amap[i][k] + amap[k][j]:
        isnt_add = True
    if not isnt_add:
      cost += amap[i][j]

if isnt_const:
  print(-1)
else:
  print(cost)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
d = [x[:] for x in a]
ans = 0
for i in range(n):
    for j in range(i + 1, n):
        l = []
        s = d[i][j]
        for k in range(n):
            if k == i or k == j:
                continue
            dist = d[i][k] + d[k][j]
            if dist == s:
                ans -= s
                break
            d[i][j] = min(d[i][j], dist)
for i in range(n):
    if a[i] != d[i]:
        print(-1)
        exit()
an = 0
for i in range(n):
    an += sum(a[i])
print(an // 2 + ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
d = [x[:] for x in a]
ans = 0
for i in range(n):
    for j in range(i + 1, n):
        l = []
        for k in range(n):
            dist = d[i][k] + d[k][j]
            l.append(dist)
            d[i][j] = min(d[i][j], dist)
        for m in Counter(l).most_common():
            if m[1] >= 3:
                ans -= m[0]
for i in range(n):
    if a[i] != d[i]:
        print(-1)
        exit()
an = 0
for i in range(n):
    an += sum(a[i])
print(an // 2 + ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
d = [x[:] for x in a]
ans = 0
for i in range(n):
    for j in range(n):
        l = []
        if i > j:
            continue
        for k in range(n):
            if i != j:
                l.append(d[i][k] + d[k][j])
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
        for m in Counter(l).most_common():
            if m[1] >= 3:
                ans -= m[0]
for i in range(n):
    if a[i] != d[i]:
        print(-1)
        exit()
an = 0
for i in range(n):
    an += sum(a[i])
print(an // 2 + ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
d = [x[:] for x in a]
ans = 0
for i in range(n):
    for j in range(n):
        l = []
        for k in range(n):
            if i != j:
                l.append(d[i][k] + d[k][j])
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
        for m in Counter(l).most_common():
            if m[1] >= 3:
                ans -= m[0]
for i in range(n):
    if a[i] != d[i]:
        print(-1)
        exit()
for i in range(n):
    ans += sum(a[i])
print(ans // 2)

Submission status: Time Limit Exceeded

Solution code:
def warshall_floyd(n,d):
    #d[i][j]: iからjへの最短距離
    r = [[float("inf")]*n for i in range(n)]
    for k in range(n):
        for i in range(n):
            for j in range(n):
                r[i][j] = min(d[i][j],r[i][k] + r[k][j])
    return r

n = int(input())
a = [[] for i in range(n)]
for i in range(n):
    a[i] = list(map(int,input().split()))
for i in range(n):
    if a[i][i] != 0:
        print(-1)
        exit()


war = warshall_floyd(n,a)

res = 0
for i in range(n):
    for j in range(n):
        if war[i][j] < a[i][j]:
            print(-1)
            exit()
        elif war[i][j] == a[i][j]:
            judge = 1
            for h in range(n):
                if h != i and h != j and war[i][h]+war[h][j] == war[i][j]:
                    judge = -1
            if judge == 1:
                res += war[i][j]
print(res//2)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

def main():
    N = int(input())
    A = []
    C = []
    for i in range(N):
        A.append(list(map(int, input().split())))
        C.append([0] * N)

    for i in range(N):
        ai = A[i]
        ci = C[i]
        for j in range(i + 1, N):
            cf = False
            aj = A[j]
            aij = ai[j]
            for k in range(N):
                if k == i or k == j:
                    continue
                d = ai[k] + aj[k]
                if d < aij:
                    print(-1)
                    return
                if d == aij:
                    cf = True
            if cf:
                ci[j] = 1

    x = 0
    for i in range(N):
        ai = A[i]
        ci = C[i]
        for j in range(i + 1, N):
            if ci[j] == 0:
                x += ai[j]


    print(x)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

def main():
    N = int(input())
    A = []
    C = []
    for i in range(N):
        A.append(list(map(int, input().split())))
        C.append([0] * N)

    for i in range(N):
        for j in range(i + 1, N):
            cf = False
            aij = A[i][j]
            for k in range(N):
                if k == i or k == j:
                    continue
                d = A[i][k] + A[k][j]
                if d < aij:
                    print(-1)
                    return
                if d == aij:
                    cf = True
            if cf:
                C[i][j] = 1

    x = 0
    for i in range(N):
        for j in range(i + 1, N):
            if C[i][j] == 0:
                x += A[i][j]


    print(x)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def inpl(): return [int(i) for i in input().split()]
import sys 
N = int(input())
A = [inpl() for _ in range(N)]
ans = 0
for i in range(N):
    A[i][i] = float('inf')
for i in range(N):
    for j in range(i):
        mindis = min([A[i][k] + A[j][k] for k in range(N)])
        if mindis > A[i][j]:
            ans += A[i][j]
            continue
        if mindis < A[i][j]:
            print(-1)
            sys.exit()

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
n = int(input())
d = []
for i in range(n):
    line = [int(x) for x in input().split()]
    d.append(line)

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

res = 0
for i in range(i):
    for j in range(i+1,n):
        flag = True
        for k in range(n):
            if i==k or j==k:
                continue
            if d[i][j]==d[i][k]+d[k][j]:
                flag = False
                break
        if flag:
            res += d[i][j]
print(res)

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
N=int(input())
len = [list(map(int,input().split())) for t in range (N)]
a=0
n=0
while n < N:
    m=n+1
    while m < N:
        i=0
        while i < N:
            if i!=n and i!=m:
                if len[n][i]+len[i][m]==len[n][m]:
                    a+=len[n][m] 
                    break
                elif len[n][i]+len[i][m]<len[n][m]:  
                    print(-1)
                    sys.exit()
            i+=1
        m+=1
    n+=1

sum=0
n=0
while n < N:
    m=n+1
    while m < N:
        sum+=len[n][m]
        m+=1
    n+=1

print(sum-a)

Submission status: Time Limit Exceeded

Solution code:
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import *
from bisect import *

def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]

N = read()
A = []
for _ in range(N):
  A.append(reads())

necc = [[True] * N for _ in range(N)]

for i, j, k in combinations(range(N), 3):
  a, b, c = sorted((
    (A[i][j], i, j),
    (A[i][k], i, k),
    (A[j][k], j, k)
  ))
  if a[0] + b[0] < c[0]:
    print(-1); exit()
  elif a[0] + b[0] == c[0]:
    necc[c[1]][c[2]] = False

ans = sum(A[i][j] for i, j in combinations(range(N), 2) if necc[i][j])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-


def read():
    global n, dis
    n = int(input())
    dis = []
    for i in range(0, n):
        dis.append(list(map(int, input().split())))


def floyd():
    for k in range(0, n):
        for i in range(0, n):
            for j in range(0, n):
                if i != j and j != k and i != k:
                    if dis[i][j] > dis[i][k] + dis[k][j]:
                        return False
    return True


def solve():
    ans = 0
    for i in range(0, n):
        for j in range(i + 1, n):
            flag = True
            for k in range(0, n):
                if i != j and j != k and i != k:
                    if dis[i][j] == dis[i][k] + dis[k][j]:
                        flag = False
                        break
            if flag:
                ans += dis[i][j]
    return ans


def work():
    if not floyd():
        print("-1")
        return
    print(solve())


if __name__ == "__main__":
    read()
    work()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq,copy

# decimal.getcontext().prec = 50
# sys.setrecursionlimit(10000)
# MOD = 10**9 + 7

def warshall_floyd(d):
    """Warshall Floyd method"""

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

def solve(f):
    n = f.read_int()
    a = [f.read_int_list() for _ in xrange(n)]

    aorg = copy.deepcopy(a)
    warshall_floyd(a)

    for i in xrange(n):
        for j in xrange(n):
            if aorg[i][j] != a[i][j]: return -1

    ans = 0
    for i in xrange(n):
        for j in xrange(n):
            if i == j: continue
            for k in xrange(n):
                if i == k or j == k: continue
                if a[i][j] == a[i][k] + a[k][j]: break
            else:
                ans += a[i][j]

    return ans/2


class Reader(object):
    def __init__(self, filename=None):
        self.file = open(filename) if filename is not None else None
        self.case = 1

    def __readline(self):
        return self.file.next().strip() if self.file else raw_input()

    def next_case(self):
        self.file.next()
        self.case += 1

    def read_int(self): return int(self.__readline())
    def read_float(self): return float(self.__readline())
    def read_long(self): return long(self.__readline())
    def read_decimal(self): return decimal.Decimal(self.__readline())
    def read_str(self): return self.__readline()

    def read_int_list(self): return map(int, self.__readline().split())
    def read_float_list(self): return map(float, self.__readline().split())
    def read_long_list(self): return map(long, self.__readline().split())
    def read_decimal_list(self): return map(decimal.Decimal, self.__readline().split())
    def read_str_list(self): return self.__readline().split()

if __name__ == '__main__':
    filename = sys.argv[1] if len(sys.argv) > 1 else None
    f = Reader(filename)
    if f.file:
        while True:
            print "Case #%d\n"%f.case, solve(f)
            try:
                f.next_case()
            except StopIteration:
                break
    else:
        print solve(f)

Submission status: Time Limit Exceeded

Solution code:
import sys
import copy
n = int(input())
a = []
for i in range(n):
	a.append(list(map(int,input().split())))
b = copy.deepcopy(a)
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])
flag = False
for i in range(n):
	for j in range(n):
		if a[i][j] != b[i][j]:
			flag = True
			break
	if flag:
		break
if flag:
	print(-1)
	sys.exit()
d = [[True 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 i == k or k == j:
				continue
			if a[i][j] == a[i][k]+a[k][j]:
				d[i][j] = False
ans = 0
for i in range(n):
	for j in range(i,n):
		if d[i][j]:
			ans += a[i][j]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
def inpl(): return tuple(map(int, input().split()))
from itertools import product

def main():
    N = int(input())
    adj = [inpl() for _ in range(N)]
    need = [[True]*N for _ in range(N)]
    ok = True
    res = 0
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if adj[i][j] < adj[i][k] + adj[k][j]:
                    continue
                elif i == k or j == k:
                    continue
                elif adj[i][j] == adj[i][k] + adj[k][j]:
                    need[i][j] = False
                    need[j][i] = False
                else:
                    ok = False
    if ok:
        for i in range(N):
            for j in range(i+1, N):
                if need[i][j]:
                    res += adj[i][j]
        print(res)
    else:
        print(-1)

main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N = int(input())
A_arr = np.zeros((N, N)).astype(int)
for i in range(N):
     A_arr[i, :]= [int(_) for _ in input().split()]

        
total = 0
isValid = True
for i in range(N):
    for j in range(i, N):
        needed=True
        for k in range(N):
            if (k != i) and (k!=j):
                if A_arr[i, j] < A_arr[i, k] + A_arr[k, j]:
                    pass
                elif A_arr[i, j] == A_arr[i, k] + A_arr[k, j]:
                    needed=False
                else:
                    isValid = False
        if needed:
            total += A_arr[i, j]
if isValid:
    print(total)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from itertools import combinations

def inpl(): return tuple(map(int, input().split()))

N = int(input())
res = 0
exist = True
A = []

for _ in range(N):
    A.append(inpl())

for i, j in combinations(range(N), 2):
    vervose = False

    for k in range(N):
        if A[i][j] > A[i][k] + A[k][j]:
            exist = False
            break
    
    if not exist:
        break
    
    for k in range(N):
        if i == k or j == k:
            pass
        elif A[i][j] == A[i][k] + A[k][j]:
            vervose = True
            break
        
    if not vervose:
        res += A[i][j]
if exist:
    print(res)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from itertools import combinations

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

N = int(input())
res = 0
exist = True
A = []

for _ in range(N):
    A.append(inpl())

for i, j in combinations(range(N), 2):
    vervose = False

    for k in range(N):
        if i == k or j == k:
            pass
        elif A[i][j] < A[i][k] + A[k][j]:
            pass
        elif A[i][j] == A[i][k] + A[k][j]:
            vervose = True
        else:
            exist = False
            break

    res += A[i][j] * (not vervose)

if exist:
    print(res)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from itertools import combinations

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

N = int(input())
res = 0
exist = True
A = []

for _ in range(N):
    A.append(inpl())

for i, j in combinations(range(N), 2):
    vervose = False

    if not exist:
        break

    for k in range(N):
        if i == k or j == k:
            pass
        else:
            if A[i][j] < A[i][k] + A[k][j]:
                pass
            elif A[i][j] == A[i][k] + A[k][j]:
                vervose = True
            else:
                exist = False
                break
    if vervose:
        pass
    else:
        res += A[i][j]

if exist:
    print(res)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
def solve(n, tbl):
    for k, tbl_k in enumerate(tbl):
        for i, tbl_i in enumerate(tbl):
            ik = tbl_i[k]
            if ik == 0:
                continue
            for j in range(i + 1, n):
                ij, kj = tbl_i[j], tbl_k[j]
                if ij == 0 or kj == 0:
                    continue
                if ij > ik + kj:
                    return -1
                if ij == ik + kj:
                    tbl_i[j] = 0
    return sum(sum(row[i + 1:]) for i, row in enumerate(tbl))


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