Problem:


Score : 500 points

Problem Statement

In Takahashi Kingdom, which once existed, there are N cities, and some pairs of cities are connected bidirectionally by roads.
The following are known about the road network:

People traveled between cities only through roads. It was possible to reach any city from any other city, via intermediate cities if necessary.

Different roads may have had different lengths, but all the lengths were positive integers.

Snuke the archeologist found a table with N rows and N columns, A, in the ruin of Takahashi Kingdom.
He thought that it represented the shortest distances between the cities along the roads in the kingdom.

Determine whether there exists a road network such that for each u and v, the integer A_{u, v} at the u-th row and v-th column of A is equal to the length of the shortest path from City u to City v.
If such a network exist, find the shortest possible total length of the roads.

Constraints

1 \leq N \leq 300

If i ≠ j, 1 \leq A_{i, j} = A_{j, i} \leq 10^9.

A_{i, i} = 0

Inputs

Input is given from Standard Input in the following format:

N
A_{1, 1} A_{1, 2} ... A_{1, N}
A_{2, 1} A_{2, 2} ... A_{2, N}
...
A_{N, 1} A_{N, 2} ... A_{N, N}

Outputs

If there exists no network that satisfies the condition, print -1.
If it exists, print the shortest possible total length of the roads.

Sample Input 1

3
0 1 3
1 0 2
3 2 0

Sample Output 1

3

The network below satisfies the condition:

City 1 and City 2 is connected by a road of length 1.

City 2 and City 3 is connected by a road of length 2.

City 3 and City 1 is not connected by a road.

Sample Input 2

3
0 1 3
1 0 1
3 1 0

Sample Output 2

-1

As there is a path of length 1 from City 1 to City 2 and City 2 to City 3, there is a path of length 2 from City 1 to City 3.
However, according to the table, the shortest distance between City 1 and City 3 must be 3.

Thus, we conclude that there exists no network that satisfies the condition.

Sample Input 3

5
0 21 18 11 28
21 0 13 10 26
18 13 0 23 13
11 10 23 0 17
28 26 13 17 0

Sample Output 3

82

Sample Input 4

3
0 1000000000 1000000000
1000000000 0 1000000000
1000000000 1000000000 0

Sample Output 4

3000000000



Sample input:
3
0 1 3
1 0 2
3 2 0


Sample output:
3

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import heapq


def dijkstra(N, adj_nodes, A, from_node, to_node):
    INF = 10**12
    dist = [INF for _ in range(N)]
    dist[from_node] = 0
    frontier = [(0, from_node)]
    while len(frontier) > 0:
        d, node = heapq.heappop(frontier)
        for next_node in adj_nodes[node]:
            next_d = dist[node] + A[node][next_node]
            if dist[next_node] > next_d:
                dist[next_node] = next_d
                heapq.heappush(frontier, (next_d, next_node))
    return dist[to_node]


def main():
    N = int(input())
    A = [list(map(int, input().split(' '))) for _ in range(N)]
    edges = list()
    for i in range(N):
        for j in range(i + 1, N):
            edges.append((A[i][j], i, j))  # (cost, from, to)
    edges.sort(key=lambda e: e[0])
    adj_nodes = defaultdict(list)
    ans = 0
    for edge in edges:
        cost, from_node, to_node = edge
        d = dijkstra(N, adj_nodes, A, from_node, to_node)
        if d < cost:
            print(-1)
            return
        elif d > cost:
            ans += cost
            adj_nodes[from_node].append(to_node)
            adj_nodes[to_node].append(from_node)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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


def main():
    N = int(input())
    A = [None for _ in range(N)]
    INF = 10**12
    for i in range(N):
        A[i] = list(map(int, input().split()))

    adj = [[0]*N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            flag = True
            for k in range(N):
                if k == i or k == j:
                    continue
                if A[i][j] > A[i][k] + A[k][j]:
                    print(-1)
                    exit()
                elif A[i][j] == A[i][k] + A[k][j]:
                    flag = False
                    break
            if flag:
                adj[i][j] = A[i][j]
    ans = 0
    for i in range(N):
        ans += sum(adj[i])
    print(ans//2)
    # print(adj)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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


def main():
    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 range(N):
            if c == a or c == b:
                continue
            if matr[a][b] == matr[a][c] + matr[c][b]:
                break
        else:
            ans += matr[a][b]
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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 range(N):
        if c == a or c == b:
            continue
        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:
import itertools
import numpy as np
from scipy.sparse.csgraph import floyd_warshall

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

way.tolist()
ans = 0
for a, b in itertools.combinations(range(N), 2):
    for c in range(N):
        if c == a or c == b:
            continue
        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:
def main():
    N = int(input())
    dist = [list(map(int, input().split())) for _ in range(N)]

    update = False
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if not (dist[i][k] and dist[k][j]): continue  # パスなし
                d = dist[i][k] + dist[k][j]
                if dist[i][j] > d:
                    dist[i][j] = d
                    update = True

    if update:
        print(-1)
        return

    ans = 0
    for j in range(N):
        for i in range(j):
            for k in range(N):
                if not (dist[i][k] and dist[k][j]): continue  # パスなし
                d = dist[i][k] + dist[k][j]
                if d == dist[i][j]: break  # divisible
            else:
                ans += dist[i][j]
    print(ans)


if __name__ == '__main__':
    main()

# import sys
# input = sys.stdin.readline
# 
# sys.setrecursionlimit(10 ** 7)
# 
# (int(x)-1 for x in input().split())
# rstrip()
#
# def binary_search(*, ok, ng, func):
#     while abs(ok - ng) > 1:
#         mid = (ok + ng) // 2
#         if func(mid):
#             ok = mid
#         else:
#             ng = mid
#     return ok

Submission status: Time Limit Exceeded

Solution code:
import copy

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

B = copy.deepcopy(A)
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        for k in range(N):
            if j == k:
                continue
            if k == i:
                continue
            if A[i][j] > A[i][k] + A[k][j]:
                print(-1)
                exit()
            if A[i][j] == A[i][k] + A[k][j]:
                B[i][j] = 0

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

print(ans)

Submission status: Time Limit Exceeded

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

for k in range(n):
    for i in range(n):
        for j in range(n):
            if k != i and k != j:
                if A[i][j] > A[i][k] + A[k][j]:
                    print(-1)
                    exit()
                elif A[i][j] == A[i][k] + A[k][j]:
                    B[i][j] = 0

ans = 0
for i in range(n):
    for j in range(i):
        if B[i][j]:
            ans += A[i][j]

print(ans)

Submission status: Time Limit Exceeded

Solution code:

def warshall_floyd(cost):
    ret = [[1]*N for _ in [0]*N]
    for k in range(N):
        for i, c_left in enumerate(cost[i][k] for i in range(N)):
            for j, (c_now, c_right) in enumerate(zip(cost[i], cost[k])):
                if c_left + c_right < c_now:
                    print(-1)
                    exit()
                if i == j or j == k or k == i:
                    continue
                if c_left + c_right == c_now:
                    ret[i][j] = ret[j][i] = 0
    return ret


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


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

road = warshall_floyd(A)
ans = 0
for cost, i, j in E:
    if not road[i][j]:
        continue
    ans += cost

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def solve():
    N = int(input())
    d = [[float('inf')]*N for _ in range(N)]
    A = [list(map(int, input().split())) for _ in range(N)]
    for i in range(N):
        for j in range(N):
            d[i][j] = A[i][j]

    #三重ループ
    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])

    for i in range(N):
        for j in range(N):
            if d[i][j] < A[i][j]:
                return -1
    ans = 0
    for i in range(N):
        for j in range(i+1,N):
            ans += A[i][j]
            for k in range(N):
                if k!= i and k!=j and A[i][j]==A[i][k]+A[k][j]:
                    ans -= A[i][j]
                    break
    return ans
print(solve())

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=[list(map(int,input().split())) 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)
        exit(0)

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

Submission status: Time Limit Exceeded

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

def warshall_floyd(G):
    h=len(G)

    res=0
    for x in range(h):
        for y in range(x+1,h):
            res+=G[x][y]

    check=[[0]*h for z in range(h)]
    for k in range(h):
        for i in range(h):
            for j in range(h):
                temp=G[i][k]+G[k][j]
                if temp==G[i][j]:
                   if i!=j and j!=k and k!=i:
                       check[i][j]=1
                elif temp<G[i][j]:
                    if i!=j and j!=k and k!=i:
                        check[i][j]=-1
    decrease=0             
    for p in range(h):
        for q in range(h):
            if check[p][q]==-1:
                return [False]
            elif check[p][q]==1:
                decrease+=G[p][q]
    else:
        return [True,res-decrease//2]


ans=warshall_floyd(A)
if not ans[0]:
    print(-1)
else:
    print(ans[1])

Submission status: Time Limit Exceeded

Solution code:
#restoring read network
import numpy as np
from scipy.sparse import csr_matrix 
from scipy.sparse.csgraph import floyd_warshall
def main():
    n=int(input())
    mat=np.array([[0 for i in range(n)] for j in range(n)],dtype=np.int)
    data=np.array([[0 for i in range(n)] for j in range(n)],dtype=np.int)
    for _ in range(n):
        x=list(map(int,input().split()))
        for j in range(n):
            mat[_][j]=x[j]
            data[_][j]=x[j]

    csr=csr_matrix(mat)
    csr=floyd_warshall(csr)
    if np.array_equal(csr,data):
        ans=0
        for i in range(n):
            for j in range(i+1,n):
                ans+=data[i][j]*int(all(data[i][j]<data[i][k]+data[k][j] for k in range(i))&all(data[i][j]<data[i][k]+data[k][j] for k in range(i+1,j))&all(data[i][j]<data[i][k]+data[k][j] for k in range(j+1,n)))     
        print(ans)            
    else:
        print(-1)
if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#restoring read network
ans=0
import numpy as np
from scipy.sparse import csr_matrix 
from scipy.sparse.csgraph import floyd_warshall
n=int(input())
mat=np.array([[0 for i in range(n)] for j in range(n)],dtype=np.int)
data=np.array([[0 for i in range(n)] for j in range(n)],dtype=np.int)
for _ in range(n):
    x=list(map(int,input().split()))
    for j in range(n):
        mat[_][j]=x[j]
        data[_][j]=x[j]
        
csr=csr_matrix(mat)
csr=floyd_warshall(csr)
if np.array_equal(csr,data):
    ans=0
    for i in range(n):
        for j in range(i+1,n):
            cnt=0
            for k in range(n):
                if data[i][j]>=data[i][k]+data[k][j]:
                    cnt+=1
            if cnt==2:
                ans+=data[i][j]                
    print(ans)            
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, setrecursionlimit

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


def main():
    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):
            required = True
            for k in range(N):
                if k == i or k == j:
                    continue
                if A[i][j] > A[i][k] + A[k][j]:
                    print(-1)
                    return
                if A[i][j] == A[i][k] + A[k][j]:
                    required = False
                    break
            if required:
                ans += A[i][j]

    print(ans)

    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys, copy
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def warshall_floyd(d):
    V = len(d)
    d = d
    for i in range(V):
        d[i][i] = 0
    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])
    return d

def resolve():
    N = I()
    A = [LI() for _ in range(N)]

    min_cost = copy.deepcopy(A)
    min_cost = warshall_floyd(min_cost)
    ans = copy.deepcopy(min_cost)

    if A == min_cost:
        for i in range(N):
            for j in range(N):
                if i!=j:
                    for k in range(N):
                        if k!=i and k!=j:
                            if min_cost[i][j]==min_cost[i][k]+min_cost[k][j]:
                                ans[i][j] = 0
        print(sum([sum(i) for i in ans])//2)
    else:
        print(-1)

if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import scipy.sparse as sps
import sys,math


n = int(input())
a = np.array([list(map(int,input().split())) for i in range(n)])

wf = sps.csgraph.floyd_warshall(a, directed=0).astype(int)
dks = []
for i in range(n): dk = sps.csgraph.dijkstra(a, indices=i, directed=0) ; dks.append(dk)
dks = np.array(dks).astype(int)


#print(a)
#print(wf)

ans = 0
for i in range(n):
    for j in range(i+1):
        if a[i][j] != wf[i][j]: ans =  -1 ;break
        flag = 1
        for k in range(n):
            if flag and i!=k!=j:
                if a[i][j] == a[i][k] + a[k][j]: flag = 0
        if flag: ans += a[i][j]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    l = []
    for i in range(N):
        a = list(map(int, input().split()))
        l.append(a)
    ans = 0
    for i in range(N):
        for j in range(i+1, N):
            if i == j:
                continue
            for k in range(N):
                if k == i or k == j:
                    continue
                if l[i][j] == l[i][k] + l[k][j]:
                    break
                if l[i][j] > l[i][k] + l[k][j]:
                    return -1
            else:
                ans += l[i][j]
    return ans
print(main())

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    d = {}
    for i in range(N):
        a = list(map(int, input().split()))
        for j in range(N):
            d[(i, j)] = a[j]
            d[(j, i)] = a[j]
    ans = 0
    for i in range(N):
        for j in range(i+1, N):
            if i == j:
                continue
            for k in range(N):
                if k == i or k == j:
                    continue
                if d[(i,j)] == d[(i,k)] + d[(k, j)]:
                    break
                if d[(i,j)] > d[(i,k)] + d[(k, j)]:
                    return -1
            else:
                ans += d[(i,j)]
    return ans
print(main())

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    A = [list(map(int, input().split())) for _ in range(N)]
    r = 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][k] + A[k][j] < A[i][j]:
                    return -1
                if A[i][k] + A[k][j] == A[i][j]:
                    break
            else:
                r += A[i][j]
    return r

print(main())

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
    def size(self, x):
        return -self.parents[self.find(x)]
        
    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())
    
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())



def main():
    N = int(input())
    l = []
    u = UnionFind(N)
    for i in range(N):
        a = list(map(int, input().split()))
        for j in range(N):
            if i < j:
                l.append((a[j], i, j))
    l.sort()
    r = [[0]*N for _ in range(N)]
    ans = 0
    for k, i, j in l:
        if not u.same(i,j):
            r[i][j] = k
            r[j][i] = k
            ans += k
            u.union(i,j)
            continue
        G = csr_matrix(r)
        d = dijkstra(G, indices=i)
        if d[j] < k:
            return -1
        elif d[j] == k:
            continue
        else:
            r[i][j] = k
            r[j][i] = k
            ans += k
    return ans
print(main())

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
def main():
    N = int(input())
    l = []
    for i in range(N):
        a = list(map(int, input().split()))
        for j in range(N):
            if i < j:
                l.append((a[j], i, j))
    l.sort()
    r = [[0]*N for _ in range(N)]
    ans = 0
    for k, i, j in l:
        G = csr_matrix(r)
        d = dijkstra(G, indices=i)
        if d[j] < k:
            return -1
        elif d[j] == k:
            continue
        else:
            r[i][j] = k
            r[j][i] = k
            ans += k
    return ans
print(main())

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
def main():
    N = int(input())
    l = []
    for i in range(N):
        a = list(map(int, input().split()))
        for j in range(N):
            if i < j:
                l.append((a[j], i, j))
    l.sort()
    r = [[0]*N for _ in range(N)]
    ans = 0
    for k, i, j in l:
        G = csr_matrix(r)
        d = dijkstra(G)
        if d[i][j] < k:
            return -1
        elif d[i][j] == k:
            continue
        else:
            r[i][j] = k
            r[j][i] = k
            ans += k
    return ans
print(main())

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush,heappop,heapify
INF=10**18

def find(x):
    if(par[x]==x):
        return x
    else:
        par[x]=find(par[x])
        return par[x]
def union(a,b):
    a=find(a)
    b=find(b)
    if(a==b):
        return 0
    else:
        if rank[a]>rank[b]:
            par[b]=a
            siz[a]+=siz[b]
        else:
            par[a]=b
            siz[b]+=siz[a]
            if rank[a]==rank[b]:
                rank[b]+=1
def size(a):
    return siz[find(a)]
def same(a,b):
    return find(a)==find(b)

def dijkstra(G,s,g,n):
    que=[(0,s)]
    dist=[INF]*n
    dist[s]=0
    while que:
        mincost,u=heappop(que)
        if(mincost>dist[u]):
            continue
        if(u==g):
            return dist
        if(G[u]):
            for c,v in G[u]:
                if(dist[u]+c<dist[v]):
                    dist[v]=dist[u]+c
                    heappush(que,(dist[v],v))
    return dist

N=int(input())
par=[i for i in range(N)]
siz=[1 for _ in range(N)]
rank=[0 for _ in range(N)]

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

G=[set() for i in range(N)]
Edges=[]
for i in range(N):
    for j in range(N):
        if(i==j):
            continue
        Edges.append([A[i][j],i,j])
Edges.sort(key=lambda x:x[0])

res=0
for i in range(len(Edges)):
    cost,fr,to=Edges[i]
    if not same(fr,to):
        union(fr,to)
        G[fr].add((cost,to))
        G[to].add((cost,fr))
        res+=cost
    else:
        di=dijkstra(G,fr,to,N)
        if di[to]<A[fr][to]:
            print(-1)
            exit()
        if di[to]>cost:
            G[fr].add((cost,to))
            G[to].add((cost,fr))
            res+=cost
print(res)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush,heappop,heapify
INF=10**18

def find(x):
    if(par[x]==x):
        return x
    else:
        par[x]=find(par[x])
        return par[x]
def union(a,b):
    a=find(a)
    b=find(b)
    if(a==b):
        return 0
    else:
        if rank[a]>rank[b]:
            par[b]=a
            siz[a]+=siz[b]
        else:
            par[a]=b
            siz[b]+=siz[a]
            if rank[a]==rank[b]:
                rank[b]+=1
def size(a):
    return siz[find(a)]
def same(a,b):
    return find(a)==find(b)

def dijkstra(G,s,g,n):
    que=[(0,s)]
    dist=[INF]*n
    dist[s]=0
    while que:
        mincost,u=heappop(que)
        if(mincost>dist[u]):
            continue
        if(u==g):
            return dist
        if(G[u]):
            for c,v in G[u]:
                if(dist[u]+c<dist[v]):
                    dist[v]=dist[u]+c
                    heappush(que,(dist[v],v))
    return dist

N=int(input())
par=[i for i in range(N)]
siz=[1 for _ in range(N)]
rank=[0 for _ in range(N)]

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

G=[[] for i in range(N)]
Edges=[]
for i in range(N):
    for j in range(N):
        if(i==j):
            continue
        Edges.append([A[i][j],i,j])
heapify(Edges)

res=0
while Edges:
    cost,fr,to=heappop(Edges)
    if not same(fr,to):
        union(fr,to)
        G[fr].append((cost,to))
        G[to].append((cost,fr))
        res+=cost
    else:
        di=dijkstra(G,fr,to,N)
        if di[to]<A[fr][to]:
            print(-1)
            exit()
        if di[to]>cost:
            G[fr].append((cost,to))
            G[to].append((cost,fr))
            res+=cost
print(res)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush,heappop,heapify
INF=10**18

def find(x):
    if(par[x]==x):
        return x
    else:
        par[x]=find(par[x])
        return par[x]
def union(a,b):
    a=find(a)
    b=find(b)
    if(a==b):
        return 0
    else:
        if rank[a]>rank[b]:
            par[b]=a
            siz[a]+=siz[b]
        else:
            par[a]=b
            siz[b]+=siz[a]
            if rank[a]==rank[b]:
                rank[b]+=1
def size(a):
    return siz[find(a)]
def same(a,b):
    return find(a)==find(b)

def dijkstra(G,s,g,n):
    que=[(0,s)]
    dist=[INF]*n
    dist[s]=0
    while que:
        mincost,u=heappop(que)
        if(mincost>dist[u]):
            continue
        if(u==g):
            return dist
        if(G[u]):
            for c,v in G[u]:
                if(dist[u]+c<dist[v]):
                    dist[v]=dist[u]+c
                    heappush(que,(dist[v],v))
    return dist

N=int(input())
par=[i for i in range(N)]
siz=[1 for _ in range(N)]
rank=[0 for _ in range(N)]

A=[list(map(int,input().split())) for i 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)
                exit()

G=[[] for i in range(N)]
Edges=[]
for i in range(N):
    for j in range(N):
        if(i==j):
            continue
        Edges.append([A[i][j],i,j])
heapify(Edges)

res=0
while Edges:
    cost,fr,to=heappop(Edges)
    if not same(fr,to):
        union(fr,to)
        G[fr].append((cost,to))
        G[to].append((cost,fr))
        res+=cost
    else:
        di=dijkstra(G,fr,to,N)
        if di[to]>cost:
            G[fr].append((cost,to))
            G[to].append((cost,fr))
            res+=cost
print(res)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
d=[list(map(int,input().split())) for i in range(n)]
def fill(l,x):
    w=len(l[0])
    return [[x]*(w+2)]+[[x]+i+[x] for i in l]+[[x]*(w+2)]
def swap(a,b):
    if a>b:
        return b,a
    return a,b
d=fill(d,0)
edge=[{} for i in range(n+1)]
for j in range(1,n+1):
    for i in range(j+1,n+1):
        edge[j][i]=d[i][j]
for k in range(1,n+1):
    for i in range(1,n+1):
        for j in range(1,n+1):
            if  d[i][j]>d[i][k]+d[k][j]:
                print(-1)
                quit()
            elif d[i][j]==d[i][k]+d[k][j]:
                if k==i or k==j:
                    continue
                x,y=swap(i,j)
                if y in edge[x]:
                    del edge[x][y]
ans=0
for i in edge:
    ans+=sum(i.values())
print(ans)

Submission status: Time Limit Exceeded

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

#sys.setrecursionlimit(10**9)

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def LI(): return list(map(int,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode('utf-8')

import copy

def main():
	n=II()
	A=[]
	for _ in range(n):
		a=LI()
		A.append(a)

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

	B=copy.deepcopy(A)

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

	if A!=B:
		print(-1)
		exit(0)

	for k in range(n):
		for i in range(n):
			for j in range(n):
				if B[i][j]==B[i][k]+B[k][j]:
					A[i][j]=0

	ans=0

	for i in range(n):
		for j in range(i,n):
			if i!=j:
				ans+=A[i][j]

	print(ans)


if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    N = int(readline())
    A = [[int(i) for i in readline().split()] for _ in range(N)]

    via_min = [[10**15] * N for _ in range(N)]

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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    N = int(readline())
    A = [[int(i) for i in readline().split()] for _ in range(N)]

    via_min = [[10**15] * N for _ 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
                via_min[i][j] = min(via_min[i][j], A[i][k] + A[k][j]) 

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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
import math
#from collections import defaultdict
#d = defaultdict(int)
#import fractions
#import math
#import collections
#from collections import deque
#from bisect import bisect_left
#from bisect import insort_left
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
#import itertools
#import heapq
#import numpy as np
#INF = float("inf")
N = int(input())
A = [list(map(int,input().split())) for _ in range(N)]
flag = 1
s = 0
for i in range(N-1):
    if flag == 0:
        break
    for j in range(i+1,N):
        judge = 1
        if flag == 0:
            break
        a = A[i][j]
        s += a
        for k in range(N):
            if k == i or k == j:
                continue
            elif a > A[i][k] + A[k][j]:
                flag = 0
                break
            elif a == A[i][k] + A[k][j]:
                s -= a
                break
            else:
                continue
if flag == 0:
    print(-1)
else:
    print(s)