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:
import sys
N=int(input())

def warshall_floyd(d):
  #d[i][j]: iからjへの最短距離
  for k in range(N):
    for i in range(N):
      for j in range(N):
        if i<j and i!=k and k!=j and d[i][j]==d[i][k]+d[k][j]:
          #print((i,k),(k,j))
          shortcut_set.add((i,j))
        d[i][j]=min(d[i][j],d[i][k]+d[k][j])
  return d

mat=[]
for i in range(N):
  mat.append([int(x) for x in input().split()])
#print(mat)

dist=[[float("inf")]*N for i in range(N)]
graph=[[] for _ in range(N)]
for i in range(N):
  for j in range(N):
    if i==j:
      dist[i][i]=0
    else:
      graph[i].append((j,mat[i][j]))
      dist[i][j]=mat[i][j]
#print(graph)
#print(dist)

shortcut_set=set()
dist=warshall_floyd(dist)
#print(dist)

for i in range(N):
  for j in range(N):
    if dist[i][j]!=mat[i][j]:
      print(-1)
      sys.exit(0)
      
answer=0
for i in range(N):
  for j in range(i+1,N):
    if not (i,j) in shortcut_set:
      answer+=dist[i][j]
      
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

n = int(input())

d = [[float('inf')]*n for i in range(n)]

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

for i in range(n):
    if d[i][i] != 0:
        print(-1)
        exit()

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

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

print(ans//2)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
wf=[list(map(int,input().split())) for i in range(n)]

ans=0
for i in range(n):
    for j in range(i+1,n):
        use=True
        for h in range(n):
            if h!=i and h!=j and wf[i][j] > wf[i][h]+wf[h][j]:
                print(-1)
                exit()
            if h!=i and h!=j and wf[i][j] == wf[i][h]+wf[h][j]:
                use=False
        if use:
            ans+=wf[i][j]
print(int(ans))

Submission status: Time Limit Exceeded

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

from scipy.sparse.csgraph import floyd_warshall
wf=floyd_warshall(a)
if not (a==wf).all() :
    print(-1)
    exit()

ans=0
for i in range(n):
    for j in range(i+1,n):
        use=True
        for h in range(n):
            if h!=i and h!=j and wf[i][j] == wf[i][h]+wf[h][j]:
                use=False
        if use:
            ans+=wf[i][j]
print(int(ans))

Submission status: Time Limit Exceeded

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

from scipy.sparse.csgraph import floyd_warshall
wf=floyd_warshall(a)
if not (a==wf).all() :
    print(-1)
    exit()

ans=0
for i in range(n):
    for j in range(n):
        use=True
        for h in range(n):
            if h!=i and h!=j and wf[i][j] == wf[i][h]+wf[h][j]:
                use=False
        if use:
            ans+=wf[i][j]
print(int(ans//2))

Submission status: Time Limit Exceeded

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

from scipy.sparse.csgraph import floyd_warshall
wf=floyd_warshall(a)
if not (a==wf).all() :
    print(-1)
    exit()

ans=0
for i in range(n):
    for j in range(n):
        use=True
        for h in range(n):
            if h!=i and h!=j and wf[i][j] == wf[i][h]+wf[h][j]:
                use=False
        if use:
            ans+=wf[i][j]
print(int(ans//2))

Submission status: Time Limit Exceeded

Solution code:

import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read
inp = sys.stdin.buffer.readline
def inpS(): return inp().rstrip().decode()
readlines = sys.stdin.buffer.readlines
MOD = 10**9+7
INF = 1<<60
# A：想定する最短距離と計算(WF)で算出した最短距離が合っているか判定
# A[i][j] > A[i][k] + A[k][j] : -1
# AとWFが合っていたら最短距離の和を出力
def resolve():
    N = int(input())
    A = [list(map(int, input().split())) for _ in range(N)]
    B = [[True]*(N) for _ in range(N)]

    for k in range(N):
        for i in range(N):
            for j in range(N):
                if A[i][j] > A[i][k] + A[k][j]:
                    print(-1)
                    return
                # 1~Nまでの最短距離を求める為、不要な道を削除
                # (sample1:1->3=3, 1->2->3=1+2) よって1->3は削除
                elif A[i][j] == A[i][k] + A[k][j] and k!=i and k!= j:
                    B[i][j] = False

    ans = [sum([A[i][j] for j in range(N) if B[i][j]]) for i in range(N)]
    print(sum(ans)//2)

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
MOD = 10**9 + 7

N = int(input())
INF = 10**10
cost = [[INF]*N for _ in range(N)]

for i in range(N):
    C = list(map(int, input().split()))
    for j in range(N):
        cost[i][j] = C[j]
    cost[i][i] = INF

ans = 0
for j in range(N):
    for k in range(j+1,N):
        mn = INF
        for i in range(N):
            mn = min(mn, cost[j][i]+cost[i][k])    
        if (cost[j][k] > mn):
            print (-1)
            exit()
        elif (cost[j][k] < mn):
            ans += cost[j][k]                      
print (ans)

Submission status: Time Limit Exceeded

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

d = [a[i][:] for i in range(n)]
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])

ans = 0
for i in range(n):
    for j in range(n):
        if a[i][j] > d[i][j]:
            ans = -2
            break
        for k in range(n):
            if i == k or j == k: continue
            if d[i][j] == d[i][k] + d[k][j]: break
        else:
            ans += d[i][j]
    else:
        continue
    break

ans //= 2
print(ans)

Submission status: Time Limit Exceeded

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


L = []
for i in range(N-1):
    for j in range(i+1, N):
        L.append((A[i][j], i, j))
L.sort()

B = deepcopy(A)
for k in range(N):
    for i in range(N):
        for j in range(N):
            if B[i][k] != 0 and B[k][j] != 0 and B[i][j] == B[i][k] + B[k][j]:
                B[i][j] = INF

ans = 0
for i in range(N):
    for j in range(N):
        if B[i][j] != INF:
            ans += B[i][j]
ans //= 2

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(ans)
else:
    print(-1)

Submission status: Time Limit Exceeded

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

from heapq import *

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

def Dijkstra(s,g):
    dist = [1e100]*n
    dist[s] = 0
    pq = [(dist[s],s)]
    heapify(pq)
    while pq:
        d,p = heappop(pq)
        if dist[p] < d:continue
        for nxt,c in path[p].items():
            if dist[nxt] > c + d:
                dist[nxt] = c + d
                heappush(pq,(dist[nxt],nxt))
    return dist[g]

path = [{} for _ in range(n)]
road = []
heapify(road)

for i in range(1,n):
    for j in range(i):
        a = A[i][j]
        heappush(road,(a,j,i))
ans = 0
while road:
    a,i,j = heappop(road)
    D = Dijkstra(i,j)
    if D < a:
        ans = -1
        break
    elif D > a:
        path[i][j] = a
        path[j][i] = a
        ans += a
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy
n = int(input())
l = [list(map(int,input().split())) for i in range(n)]
l1 = copy.deepcopy(l)

for k in range(n):
    for i in range(n):
        for j in range(n):
            if l[i][j] > l[i][k]+l[k][j]:
                print(-1)
                exit()

            elif l[i][j] == l[i][k]+l[k][j]:
                if i != k and k != j :
                    l1[i][j] = 0
ans = 0
for i in l1:
    for j in i:
        ans += j
print(ans//2)

Submission status: Time Limit Exceeded

Solution code:
n= int(input())
rg=[]
for i in range(n):
    temp= list(map(int,input().split()))
    rg.append(temp)
bypass = set()
for i in range(n):
    for j in range(i+1,n):
        rgij=rg[i][j]
        for k in range(n):
            if not k in [i,j]:
                byp = rg[i][k]+rg[k][j]
                if rgij > byp:
                    print(-1)
                    exit(0)
                elif rgij == byp:bypass.add((i,j))
rel=0
for i in range(n):
    for j in range(i+1,n):
        if (i,j) not in bypass:rel += rg[i][j]
print(rel)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import numpy as np
from scipy.sparse.csgraph import floyd_warshall
from sys import exit

N = int(input())

matr = [tuple(map(int, input().split())) for _ in range(N)]
way = floyd_warshall(matr).astype(int)
if np.any(way < matr):
    print(-1)
    exit()

ans = 0
for a, b in itertools.combinations(range(N), 2):
    for c in set(range(N)) - {a, b}:
        if matr[a][b] == matr[a][c] + matr[c][b]:
            break
    else:
        ans += matr[a][b]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n= int(input())
atab = []
rg=[]
for i in range(n):
    temp= list(map(int,input().split()))
    atab.append(temp)
    rg.append(temp)
#WF
for k in range(n):
    for i in range(n):
        rgik=rg[i][k]
        for j in range(n):
            if rg[i][j] > rgik + rg[k][j]:
                print(-1)
                exit(0)
bypass = set()
for i in range(n):
    for j in range(n):
        if j-i>1:
            for k in range(i+1,j):
                for l in range(i+1,j):
                    tabsq=[(atab[i][k],i,k),(atab[i][j],i,j),(atab[l][k],l,k),(atab[l][j],l,j)]
                    for m in [[0,1,2],[0,1,3],[0,2,3],[1,2,3]]:
                        newl = sorted([tabsq[index] for index in m])
                        if newl[0][1]==newl[0][2] or newl[1][1]==newl[1][2] or newl[2][1]==newl[2][2]:pass
                        else:
                            if newl[0][0]+newl[1][0]==newl[2][0]:bypass.add((newl[2][1],newl[2][2]))
rel = 0
for i in range(n):
    for j in range(n):
        if (i<j) and ((i,j) not in bypass):rel += atab[i][j]
print(rel)

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import dijkstra as di
n = int(input())
grid = [list(map(int, input().split())) for i in range(n)]
dgrid = di(grid)

ans = [[0 for i in range(n)] for j in range(n)]
for i in range(n):
    for j in range(n):
        if grid[i][j] != dgrid[i][j]:
            print(-1)
            exit()

ans = 0
for i in range(n):
    for j in range(n):
        for k in range(n):
            if i == j or j == k or k == i:
              continue
            if grid[i][k] + grid[k][j] == grid[i][j]:
                dgrid[i][j] = 0

ans = 0
for i in range(n):
    for j in range(i+1, n):
        ans += dgrid[i][j]
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush


def bfs(x, y):
    path = [float('inf')] * N
    q = []
    heappush(q, (0, x))
    path[x] = 0

    while q:
        s, p = heappop(q)
        for np, d in edge[p]:
            nd = path[p] + d
            if path[np] > nd:
                path[np] = nd
                heappush(q, (nd, np))
    
    return path[y]


N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
q = []
for i in range(N):
    for j in range(i + 1, N):
        q.append((A[i][j], i, j))

q.sort()

# B = [[float('inf')] * N for _ in range(N)]

ans = 0
edge = [[] for _ in range(N)]
for a, i, j in q:
    b = bfs(i, j)
    if a < b:
        edge[i].append((j, a))
        edge[j].append((i, a))
        ans += a
    elif a == b:
        pass
    else:
        print(-1)
        exit()

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def bfs(x, y):
    path = [float('inf')] * N
    q = deque()
    q.append(x)
    path[x] = 0
    while q:
        p = q.popleft()
        for np, d in edge[p]:
            if path[np] > path[p] + d:
                path[np] = path[p] + d
                q.append(np)
    
    return path[y]


N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
q = []
for i in range(N):
    for j in range(i + 1, N):
        q.append((A[i][j], i, j))

q.sort()

# B = [[float('inf')] * N for _ in range(N)]

ans = 0
edge = [[] for _ in range(N)]
for a, i, j in q:
    b = bfs(i, j)
    if a < b:
        edge[i].append((j, a))
        edge[j].append((i, a))
        ans += a
    elif a == b:
        pass
    else:
        print(-1)
        exit()

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
from collections import deque


def bfs(x, y):
    path = [float('inf')] * N
    q = deque()
    q.append(x)
    path[x] = 0
    while q:
        p = q.popleft()
        for np, d in edge[p]:
            if path[np] > path[p] + d:
                path[np] = path[p] + d
                q.append(np)
    
    return path[y]


N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
q = []
for i in range(N):
    for j in range(i + 1, N):
        heappush(q, (A[i][j], i, j))

ans = 0
edge = [[] for _ in range(N)]
while q:
    a, i, j = heappop(q)
    b = bfs(i, j)
    if a < b:
        edge[i].append((j, a))
        edge[j].append((i, a))
        ans += a
    elif a == b:
        pass
    else:
        print(-1)
        exit()

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [[int(i) for i in input().split()] for _ in range(n)]
ans = 0
b = [i[:] for i in 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 b[i][j] < a[i][j]:
            ans = -1
            flag = True
            break
        if b[i][j] == a[i][j]:
            for k in range(n):
                if k == i or k == j: continue
                if b[i][j] == b[i][k] + b[k][j]: break
            else:
                ans += b[i][j]
    if flag: break

ans //= 2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq
import math
class Graph:
    def __init__(self,v,adj,w_v = None):
        super().__init__()
        self.v = v
        self.w_e = [{} for _ in [0]*self.v]
        self.neighbor = [[] for _ in [0]*self.v]
        
        self.w_v = w_v

        for i, adj_i in enumerate(adj):
            for j, w in enumerate(adj_i):
                self.w_e[i][j] = w #weight of edge
                self.neighbor[i].append(j)

    def dijkstra(self,v_n):
        d = [10**18]*self.v
        d[v_n] = 0
        prev = [-1]*self.v

        queue = []
        for i,d_i in enumerate(d): heapq.heappush(queue,(d_i,i))
        
        while len(queue)>0:
            d_u,u = queue.pop()
            if d[u]<d_u :continue
            for v in self.neighbor[u]:
                alt = d[u]+self.w_e[u][v]
                if d[v]>alt:
                    d[v] = alt
                    prev[v] = u
                    heapq.heappush(queue,(alt,v))

        return d,prev
    
    def WarshallFloyd(self):
        d = [[10**18]*self.v for _ in [0]*self.v]
        for i in range(self.v):
            for j in self.neighbor[i]:
                d[i][j] = self.w_e[i][j]
                
        for i in range(self.v):
            for j in range(self.v):
                for k in range(self.v):
                    check = d[i][k] + d[k][j]
                    if d[i][j] > check:
                        d[i][j] = check
        return d

def main():
    n = int(input())

    a = [[int(t)for t in input().split()]for _ in [0]*n]

    g = Graph(n,a)
    a_check = g.WarshallFloyd()

    s = 0
    for i in range(n):
        for j in range(n):
            a_ij = a[i][j]
            if a_ij != a_check[i][j]:
                print(-1)
                return
            if sum([a_ij == a[i][k] + a[k][j] for k in range(n) if k != i and k != j]) == 0:
                s+=a_ij
    print(s//2)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def solve(V, G):
    for i in range(V):
        G[i][i] = float("inf")
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if G[i][k] + G[k][j] < G[i][j] < float("inf"):
                    return False, G
                elif G[i][j] == G[i][k] + G[k][j]:
                    G[i][j] = float("inf")
    return True, G


def dist(V, G):
    ans = 0
    for i in range(V):
        for j in range(i, V):
            if G[i][j] < float("inf"):
                ans += G[i][j]
    return ans


def main():
    V = int(input())
    G = [[int(i) for i in input().split()] for i in range(V)]
    flag, G = solve(V, G)
    if flag:
        print(dist(V, G))
    else:
        print(-1)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    V = int(input())
    flag = True
    ans = 0

    G = [[int(i) for i in input().split()] for i in range(V)]
    for i in range(V):
        G[i][i] = float("inf")
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if G[i][k] + G[k][j] < G[i][j] < float("inf"):
                    flag = False
                    break
                elif G[i][j] == G[i][k] + G[k][j]:
                    G[i][j] = float("inf")

    for i in range(V):
        for j in range(i, V):
            if G[i][j] < float("inf"):
                ans += G[i][j]

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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def solve(V, G):
    for i in range(V):
        G[i][i] = float("inf")
    for k in range(V):
        for i in range(V):
            for j in range(V):
                #print(G)
                if G[i][k] + G[k][j] < G[i][j] < float("inf"):
                    return False, G
                elif G[i][j] == G[i][k] + G[k][j]:
                    G[i][j] = float("inf")
    return True, G


def dist(G):
    ans = 0
    for i in range(N):
        for j in range(N):
            if G[i][j] < float("inf"):
                ans += G[i][j]
    return ans

N = int(input())
G = [[int(i) for i in input().split()] for i in range(N)]

flag, G = solve(N, G)

if flag:
    print(dist(G)//2)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys 
MOD = 10 ** 9 + 7
INF = 10**5
from collections import deque

def main():
    n = int(input())
    dist = []
    edge = []
    ans = 0
    for i in range(n):
        a = list(map(int,input().split()))
        dist.append(a)
        for j in range(n):
            if i < j:
                edge.append((a[j],i,j))
                ans += a[j]
    
    for k in range(n - 1):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j] ,dist[i][k] + dist[k][j])
    
    edge.sort(reverse = True,key = lambda x:x[0])
    for c,a,b in edge:
        if dist[a][b] < c:
            ans = -1
            break
        for i in range(n):
            if i != a and i != b:
                if c == dist[a][i] + dist[i][b]:
                    ans -= c
                    break
    print(ans)   

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
def main():
    N=int(input())
    road=[[float("inf") for _ in range(N)]for _ in range(N)]
    pq=[]
    ans=0
    for i in range(N):
        road[i][i]=0
        tmp=list(map(int,input().split()))
        for j in range(i+1,N):
            heappush(pq,(tmp[j],i,j))

    while pq:
        v=heappop(pq)
        d,i,j=v[0],v[1],v[2]
        tmp=road[i][j]
        for k in range(N):
            tmp=min(tmp,road[i][k]+road[k][j])
            if tmp==d:
                break
        if tmp>d:
            road[i][j]=d
            road[j][i]=d
            ans+=d
        elif tmp==d:
            road[i][j]=d
            road[j][i]=d
        else:
            print(-1)
            exit()
    print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
N=int(input())
road=[[float("inf") for _ in range(N)]for _ in range(N)]
pq=[]
ans=0
for i in range(N):
    road[i][i]=0
    tmp=list(map(int,input().split()))
    for j in range(i+1,N):
        heappush(pq,(tmp[j],i,j))

while pq:
    v=heappop(pq)
    d,i,j=v[0],v[1],v[2]
    tmp=road[i][j]
    for k in range(N):
        tmp=min(tmp,road[i][k]+road[k][j])
    if tmp>d:
        road[i][j]=d
        road[j][i]=d
        ans+=d
    elif tmp==d:
        road[i][j]=d
        road[j][i]=d
    else:
        print(-1)
        exit()
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
N=int(input())
road=[[float("inf") for _ in range(N)]for _ in range(N)]
pq=[]
ans=0
for i in range(N):
    road[i][i]=0
    tmp=list(map(int,input().split()))
    for j in range(N):
        heappush(pq,(tmp[j],i,j))

while pq:
    v=heappop(pq)
    d,i,j=v[0],v[1],v[2]
    tmp=road[i][j]
    for k in range(N):
        tmp=min(tmp,road[i][k]+road[k][j])
    if tmp>d:
        road[i][j]=d
        road[j][i]=d
        ans+=d
    elif tmp==d:
        road[i][j]=d
        road[j][i]=d
    else:
        print(-1)
        exit()
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

A = [[0]*N for i in range(N)]

for i in range(N):
    A[i] = list(map(int,input().split()))
B = [[A[i][j] for j in range(i+1,N)] for i in range(N-1)]
#print(A)
#print(B)

det = 0

for i in range(N-1):
    for j in range(i+1,N):
        for k in range(N):
            if A[i][j] > A[i][k] + A[k][j]:
                det = -1
                break
            elif i != k and j != k and A[i][j] == A[i][k] + A[k][j]:
                B[i][j-(i+1)] = 0
                #print(i,j,k,B)
        
        if det == -1:
            break

    if det == -1:
        break

if det == 0:
    ans = 0
    for i in range(N-1):
        for j in range(i+1,N):
            ans += B[i][j-(i+1)]
else:
    ans = -1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
try:
    from typing import List
except ImportError:
    pass


def solve(N: int, A: "List[List[int]]"):
    es = [
        (A[i][j], i, j)
        for i in range(N)
        for j in range(i)
    ]
    es.sort(reverse=True)
    ans = 0
    for d, i, j in es:
        for k in range(N):
            if k == i or k == j:
                continue
            nd = A[i][k] + A[k][j]
            if nd < d:
                print(-1)
                return
            if nd == d:
                break
        else:
            ans += d
    print(ans)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [[int(next(tokens)) for _ in range(N)] for _ in range(N)]  # type: "List[List[int]]"
    solve(N, A)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

ans = 0
for i in range(n):
    for j in range(i+1, n):
        keiyu = 10 ** 18
        for k in range(n):
            if k not in [i, j]:
                keiyu = min(keiyu, d[i][k] + d[k][j])
        if keiyu < d[i][j]:
            print(-1)
            exit()
        elif keiyu > d[i][j]:
            ans += d[i][j]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#074_D
from copy import deepcopy
n = int(input())
a = [list(map(int,input().split())) for _ in range(n)]

def warshall_floyd(d, v):
    for k in range(v):
        for i in range(v):
            for j in range(v):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])

b = deepcopy(a)
warshall_floyd(b, n)

flg = True
ans = 0
for i in range(n):
    for j in range(n):
        if b[i][j] < a[i][j]:
            flg = False
            break
        else:
            flg2 = True
            for k in range(n):
                if i == k or j == k:
                    continue
                elif b[i][j] == b[i][k] + b[k][j]:
                    flg2 = False
            ans += b[i][j] if flg2 else 0
                    
print(ans//2 if flg else -1)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
n=int(input())
table=[]
for i in range(n):
  table.append([int(i) for i in input().split()])
Chk=True
for k in range(n):
  for i in range(n):
    for j in range(n):
      if table[i][k]+table[k][j]<table[i][j]:
        Chk=False
        table[i][j]=table[i][k]+table[k][j]

ans=0
for i in range(n):
  for j in range(i+1,n):
    C=True
    for k in range(n):
      if k==i or k==j:
        continue
      else:
        if table[i][k]+table[k][j]==table[i][j]:
          C=False
    if C:
      ans+=table[i][j]
print(ans if Chk else -1)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()

from scipy.sparse.csgraph import floyd_warshall
n=int(input())
table=[]
for i in range(n):
  table.append([int(i) for i in input().split()])
d=floyd_warshall(csgraph=table, directed=False, return_predecessors=False)

Chk=True
for i in range(n):
  for j in range(n):
    if table[i][j]==int(d[i][j]):
      continue
    else:
      Chk=False
ans=0
for i in range(n):
  for j in range(i+1,n):
    C=True
    for k in range(n):
      if k==i or k==j:
        continue
      else:
        if table[i][k]+table[k][j]==table[i][j]:
          C=False
    if C:
      ans+=table[i][j]
print(ans if Chk else -1)

Submission status: Time Limit Exceeded

Solution code:
import sys
n = int(input())
road = [0]*n
for i in range(n):
  road[i] = [int(x) for x in input().split()]

road_judge = [[True]*n for i in range(n)]
for k in range(n):
  for i in range(n):
    for j in range(n):
      if road[i][j] > road[i][k]+road[k][j]:
        print(-1)
        sys.exit()
      if road[i][j] == road[i][k]+road[k][j] and i != k and j != k:
        road_judge[i][j] = False
ans = 0
for i in range(n):
  for j in range(n):
    if road_judge[i][j]:
      ans += road[i][j]
print(ans//2)

Submission status: Time Limit Exceeded

Solution code:
import sys

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

inf = float('inf')
for i in range(N):
	E[i][i] = inf

for k in range(N):
	for i in range(N):
		if i == k:
			continue
		for j in range(N):
			if k == j or i == j:
				continue
			direct = E[i][j]
			detour = E[i][k]+E[k][j]
			if direct == inf or detour == inf:
				continue

			if direct > detour:
				print(-1)
				sys.exit()

			elif direct == detour:		
				E[i][j] = inf
				E[j][i] = inf

answer = 0
for i in range(N):
	for j in range(N):
		if E[i][j] == inf:
			continue
		
		answer += E[i][j]

print(answer//2)

Submission status: Time Limit Exceeded

Solution code:
import sys

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

ans = [[E[i][j] 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):
			direct = E[i][j]
			detour = E[i][k]+E[k][j]
			if direct < detour:
				continue
			elif direct > detour:
				print(-1)
				sys.exit()

			else:
				if i != k and j != k:
					ans[i][j] = 0
					ans[j][i] = 0

answer = 0
for a in ans:
	answer += sum(a)

print(answer//2)