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
from itertools import product

read = sys.stdin.readline


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

    answer = 0
    for i, j in product(range(N), repeat=2):
        if i < j:
            continue
        edge = A[i][j]
        for k in range(N):
            if i == k or j == k:
                continue

            tmp = A[i][k] + A[k][j]
            if tmp < edge:
                print(-1)
                exit()
            elif tmp == edge:
                break
        else:
            answer += edge

    print(answer)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

n = int(sys.stdin.readline().rstrip())
A = np.array(sys.stdin.read().split(), dtype=np.int64).reshape(n, n)

def main():
    B = floyd_warshall(csr_matrix(A), directed=False)
    if np.any(A - B > 0):
        return -1

    will_subtract = []
    for v in range(n-1):
        for u in range(v+1, n):
            d = B[v, u]
            for w in range(v):
                if B[v, w] + B[w, u] == d:
                    will_subtract.append(d)
                    break
            else:
                for w in range(v+1, u):
                    if B[v, w] + B[w, u] == d:
                        will_subtract.append(d)
                        break
                else:
                    for w in range(u+1, n):
                        if B[v, w] + B[w, u] == d:
                            will_subtract.append(d)
                            break

    ans = np.sum(B) // 2 - sum(will_subtract)
    return int(ans)

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Time Limit Exceeded

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


n = int(sys.stdin.readline().rstrip())
A = np.array(sys.stdin.read().split(), dtype=np.int64).reshape(n, n)

def main():
    B = floyd_warshall(A, directed=False)
    if np.any(A - B > 0):
        return -1

    will_subtract = []
    for v, u in combinations(range(n), 2):
        d = B[v, u]
        for w in range(n):
            if w != v and w != u:
                if B[v, w] + B[w, u] == d:
                    will_subtract.append(d)
    
    ans = np.sum(B) // 2 - sum(will_subtract)
    return int(ans)

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Time Limit Exceeded

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

def Warshall_Floyd(edges,N):

  d=copy.deepcopy(edges)
  for k in range(N):
    for i in range(N):
      for j in range(N):
        d[i][j]=min(d[i][j],d[i][k]+d[k][j])
  return d
 

N=int(input())
A=[list(map(int, input().split())) for i in range(N)]
B=Warshall_Floyd(A,N)
if A!=B:
  print(-1)
  sys.exit()
 
ans=0
for i in range(N):
  for j in range(i):
    need=1
    for k in range(N):
      if k!=i and k!=j:
        if A[i][j]==A[i][k]+A[k][j]: need=0
    ans+=need*A[i][j]
print(ans)

Submission status: Time Limit Exceeded

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

    check = [[1] * N for _ in range(N)]

    for i in range(N):
        for j in range(i + 1, N):
            for k in range(N):
                if i == k or j == k:
                    pass
                else:                    
                    if d[i][j] > d[i][k] + d[k][j]:
                        print (-1)
                        exit()
                    elif d[i][j] == d[i][k] + d[k][j]:
                        check[i][j] = 0

    ans = 0
    for i in range(N):
        for j in range(i + 1, N):
            ans += d[i][j] * check[i][j]

    print (ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

check = [[1] * N for _ in range(N)]

for i in range(N):
    for j in range(i + 1, N):
        if i == j:
            continue
        for k in range(N):
            if i == k or j == k:
                pass
            else:                    
                if d[i][j] > d[i][k] + d[k][j]:
                    print (-1)
                    exit()
                elif d[i][j] == d[i][k] + d[k][j]:
                    check[i][j] = 0

ans = 0
for i in range(N):
    for j in range(i + 1, N):
        ans += d[i][j] * check[i][j]

print (ans)

Submission status: Time Limit Exceeded

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

check = [[1] * N for _ in range(N)]

for i in range(N):
    for j in range(N):
        if i == j:
            continue
        for k in range(N):
            if i == k or j == k:
                pass
            else:                    
                if d[i][j] > d[i][k] + d[k][j]:
                    print (-1)
                    exit()
                elif d[i][j] == d[i][k] + d[k][j]:
                    check[i][j] = 0

ans = 0
for i in range(N):
    for j in range(N):
        ans += d[i][j] * check[i][j]

print (ans // 2)

Submission status: Time Limit Exceeded

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

D = sorted([(A[i][j], i, j) for i in range(N) for j in range(i+1,N)])

INF = 10**20
E = [[INF]*N for _ in range(N)]

ans = 0

for a, i, j in D:
    # find shortest path from i to j
    p = [None]*N
    d = [INF]*N
    d[i] = 0
    visited = set()
    
    while len(visited)<N:
        du, u = INF, 0
        for v in range(N):
            if v in visited: continue
            if d[v]<du: du, u = d[v], v
        visited.add(u)

        update = False
        for v, e in enumerate(E[u]):
            if e==INF: continue
            if d[v] > d[u]+e:
                update = True
                d[v] = d[u]+e
                p[v] = u
            
        if not update: break

    if d[j]>a:
        E[i][j] = E[j][i] = a
        ans += a
    elif d[j]<a:
        print(-1)
        exit()

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import copy

def solve(N: int, A: "List[List[int]]"):
    B = copy.deepcopy(A)
    for start_node in range(0,N):
        for end_node in range(start_node+1,N):
            min_dist = 10**12
            for transit in range(N):
                if transit == start_node or transit == end_node:
                    continue
                min_dist = min(min_dist,A[start_node][transit]+A[transit][end_node])

            ## impossible
            if A[start_node][end_node] > min_dist:
                print(-1)
                return 
            elif A[start_node][end_node] == min_dist:
                B[start_node][end_node] = 0
            else:
                continue
    answer =0
    for i in range(N):
        for j in range(i+1,N):
            answer+=B[i][j]
    print(answer)
    return


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:
from scipy.sparse.csgraph import floyd_warshall, csgraph_from_dense
import sys
INF = 10**18
n = int(input())
a_ls = []
for i in range(n):
    a_ls.append([int(i) for i in sys.stdin.readline().split()])
graph = csgraph_from_dense(a_ls)
res = floyd_warshall(graph)
flg = True
score = 0
for i in range(n):
    a = a_ls[i]
    r = res[i]
    for j in range(n):
        if r[j] != a[j]:
            flg = False
            break
        best = INF
        for k in range(n):
            if k in [i, j]:
                continue
            best = min(best, res[i][k] + res[k][j])
        if best != r[j]:
            score += r[j]
if flg:
    print(int(score) // 2)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import copy
ans=0
n=int(input())
l=[list(map(int,input().split())) for _ in [0]*n]
o=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()
for k in range(n):
  for i in range(n):
    for j in range(n):
        if i==j or j==k or k==i :
            continue
        if o[i][j]==o[i][k]+o[k][j]:
            o[i][j]=float("inf")
for i in range(n):
    for j in range(n):
        if o[i][j] != float("inf") :
            ans+=o[i][j]
print(ans//2)

Submission status: Time Limit Exceeded

Solution code:
from heapq import *
from collections import defaultdict
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

n=int(input())
aa=LLI(n)

def main():
    ans=sum(sum(ar) for ar in aa)//2
    for w in range(n):
        for u in range(n):
            if u==w:continue
            aau=aa[u]
            for v in range(u):
                if v==w:continue
                d=aau[w]+aa[w][v]
                if d<aau[v]:
                    print(-1)
                    exit()
                if d==aau[v]:
                    ans-=d
    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
from heapq import *
from collections import defaultdict
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

class UnionFind:
    def __init__(self, n):
        self.state = [-1] * n
        # self.size_table = [1] * n
        # cntはグループ数
        # self.cnt = n

    def root(self, u):
        v = self.state[u]
        if v < 0: return u
        self.state[u] = res = self.root(v)
        return res

    def merge(self, u, v):
        ru = self.root(u)
        rv = self.root(v)
        if ru == rv: return
        du = self.state[ru]
        dv = self.state[rv]
        if du > dv: ru, rv = rv, ru
        if du == dv: self.state[ru] -= 1
        self.state[rv] = ru
        return

def main():
    inf = 10 ** 12
    n = int(input())
    aa = LLI(n)
    #二点間の距離をヒープに記録
    hp = []
    for v in range(n):
        for u in range(v):
            heappush(hp, [aa[u][v], u, v])

    #距離の短い順に取り出して処理
    uf=UnionFind(n)
    ans = 0
    first = [True] * n
    to = defaultdict(list)
    while hp:
        d, u, v = heappop(hp)
        #頂点が非連結のときはそのまま辺をはる
        if uf.root(u)!=uf.root(v):
            to[u].append([v, d])
            to[v].append([u, d])
            ans += d
            uf.merge(u,v)
        #頂点が連結のときはダイクストラで現在の距離を求める
        else:
            vis=[False]*n
            hp2=[]
            heappush(hp2,[0,u])
            while hp2:
                dtou,w=heappop(hp2)
                #現在の距離が作りたい距離より短いことが確定したときは辺を張る
                if dtou>d:
                    to[u].append([v, d])
                    to[v].append([u, d])
                    ans += d
                    break
                if w==v:
                    #現在の距離が作りたい距離より短いときは失敗
                    if dtou<d:
                        print(-1)
                        exit()
                    # 現在の距離が作りたい距離と同じときは何もしない
                    break
                if vis[w]:continue
                vis[w]=True
                for cw,cd in to[w]:
                    if vis[cw]:continue
                    heappush(hp2,[dtou+cd,cw])

    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
from heapq import *
from collections import defaultdict
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    inf = 10 ** 12
    n = int(input())
    aa = LLI(n)
    #二点間の距離をヒープに記録
    hp = []
    for v in range(n):
        for u in range(v):
            heappush(hp, [aa[u][v], u, v])
    #距離の短い順に取り出して処理
    ans = 0
    first = [True] * n
    to = defaultdict(list)
    while hp:
        d, u, v = heappop(hp)
        #どちらかの頂点が初登場のときはそのまま辺をはる
        if first[u] or first[v]:
            to[u].append([v, d])
            to[v].append([u, d])
            ans += d
            first[u], first[v] = False, False
        #両頂点共に登場済みのときはダイクストラで現在の距離を求める
        else:
            vis=[False]*n
            hp2=[]
            heappush(hp2,[0,u])
            while hp2:
                dtou,w=heappop(hp2)
                #現在の距離が作りたい距離より短いことが確定したときは辺を張る
                if dtou>d:
                    to[u].append([v, d])
                    to[v].append([u, d])
                    ans += d
                    break
                if w==v:
                    #現在の距離が作りたい距離より短いときは失敗
                    if dtou<d:
                        print(-1)
                        exit()
                    # 現在の距離が作りたい距離と同じときは何もしない
                    break
                if vis[w]:continue
                vis[w]=True
                for cw,cd in to[w]:
                    if vis[cw]:continue
                    heappush(hp2,[dtou+cd,cw])
            else:
                #uvが非連結のときは辺を張る
                to[u].append([v, d])
                to[v].append([u, d])
                ans += d

    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
dist = [list(map(int,input().split())) for i in range(n)]
use = [[True for i in range(n)] for j in range(n)]
ans = 0

for i in range(n):
    for j in range(n):
        for k in range(n):
            if dist[j][k] > dist[j][i] + dist[i][k]:
                print(-1)
                exit()
            elif j != i and j != k and i != k and dist[j][k] == dist[j][i] + dist[i][k]:
                use[j][k] = False

for i in range(n):
    for j in range(n):
        if use[i][j]:
            ans += dist[i][j]

print(ans//2)

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import permutations, combinations
  
def solve():
    input = sys.stdin.readline
    N = int(input())
    A = dict()
    for i in range(N):
        A[i] = dict()
        ain = [int(j) for j in input().split()]
        for j in range(N): A[i][j] = ain[j]

    length = 0
    possible = True
    for a, b in combinations(range(N), 2):
        Lab = A[a][b]
        create_pass = True
        for k in range(N):
            if k != a and k != b:
                if Lab >  A[a][k] + A[k][b]:
                    possible = False
                    break
                elif Lab ==  A[a][k] + A[k][b]:
                    create_pass = False
                    break
        if create_pass: length += Lab
        if not possible:
            print(-1)
            break
    else: print(length)
    
    return 0
  
if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import permutations, combinations
  
def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [[int(i) for i in input().split()] for _ in range(N)]

    length = 0
    possible = True
    for a, b in combinations(range(N), 2):
        Lab = A[a][b]
        create_pass = True
        for k in range(N):
            if k != a and k != b:
                compare = A[a][k] + A[k][b]
                if Lab > compare:
                    possible = False
                    break
                elif Lab == compare:
                    create_pass = False
                    break
        if create_pass: length += Lab
        if not possible:
            print(-1)
            break
    else: print(length)

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    import numpy as np
    import scipy.sparse.csgraph as sp
    n=int(input())
    p=np.array([np.array(list(map(int,input().split()))) for _ in [0]*n])
    abc=[]
    ans=0
    for i in range(n):
        for j in range(i+1,n):
            b=p[i][j]
            for k in range(n):
                if i==k or j==k:
                    continue
                if b==p[i][k]+p[k][j]:
                    break
            else:
                abc.append([i,j,b])
                abc.append([j,i,b])
                ans+=b
    inf=float('inf')
    d=np.full((n,n),inf)
    for i in range(n):d[i][i]=0
    for a,b,c in abc:
        d[a][b]=c
        d[b][a]=c
    s=sp.shortest_path(d)
    if (s==p).all():
        print(ans)
    else:
        print(-1)
main()

Submission status: Time Limit Exceeded

Solution code:
import heapq
from collections import deque

N = int(input())
A = [[int(a) for a in input().split()] for _ in range(N)]

def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**9+1] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d


Road = [[] for _ in range(N)]
h = []
for i in range(N):
    for j in range(i+1, N):
        heapq.heappush(h, (A[i][j], i, j))
        
m = h[0][0]
ans = 0
while h:
    t = heapq.heappop(h)
    cost = t[0]
    i = t[1]
    j = t[2]
    if cost < 2*m:
        Road[i].append((cost, j))
        Road[j].append((cost, i))
    else:
        d = dijkstra_heap(i, Road, N)
        if d[j] > cost:
            Road[i].append((cost, j))
            Road[j].append((cost, i))
        elif d[j] < cost:
            ans = -1
            break
            
if ans == 0:
    for i in range(N):
        for t in Road[i]:
            ans += t[0]
            
    ans //= 2
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq
from collections import deque

N = int(input())
A = [[int(a) for a in input().split()] for _ in range(N)]

def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**9+1] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d


Road = [[] for _ in range(N)]
h = []
for i in range(N):
    for j in range(i+1, N):
        heapq.heappush(h, (A[i][j], i, j))
        
m = h[0][0]
ans = 0
while h:
    t = heapq.heappop(h)
    cost = t[0]
    i = t[1]
    j = t[2]
    if cost < 2*m:
        Road[i].append((cost, j))
        Road[j].append((cost, i))
    else:
        d = dijkstra_heap(i, Road, N)
        if d[j] > cost:
            Road[i].append((cost, j))
            Road[j].append((cost, i))
        elif d[j] < cost:
            ans = -1
            break
            
if ans == 0:
    R = [[10**9+1]*N for _ in range(N)]
    for i in range(N):
        R[i][i] = 0
        for t in Road[i]:
            R[i][t[1]] = t[0]
            ans += t[0]
            
    for k in range(N):
        for i in range(N):
            for j in range(N):
                R[i][j] = min(R[i][j], R[i][k]+R[k][j])
                
    if R != A:
        ans = -1
    else:
        ans //= 2
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
mat = [list(map(int, input().split())) for _ in range(n)]
ans = 0
d = [[1] * n for _ in range(n)]
for i in range(n):
    for j, c2 in enumerate(row[i] for row in mat):
        for k, (c1, c3) in enumerate(zip(mat[j], mat[i])):
            if c1 > c2+c3:
                print(-1)
                exit(0)
            elif i != j and i != k and c1 == c2 + c3:
                d[j][k] = 0
for i in range(n):
    for j in range(n):
        if d[i][j]:
            ans += mat[i][j]
print(ans // 2)

Submission status: Time Limit Exceeded

Solution code:
import copy
N = int(input())
A = [list(map(int, input().split())) for i in range(N)]
B = copy.deepcopy(A)
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        for k in range(N):
            if k == i or k == j:
                continue
            else:
                B[i][k] = min(B[i][k], B[i][j]+B[j][k])

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

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np
#from scipy.sparse.csgraph import floyd_warshall,csgraph_from_dense
#from scipy.sparse import csr_matrix
import sys
input = sys.stdin.readline
def inputs():return [int(x) for x in input().split()]
N= int(input())
dist_mat=[inputs() for _ in range(N)]
ans=0
for i in range(N):
  for j in range(N):
    for k in range(N):
      if dist_mat[j][k]==dist_mat[j][i]+dist_mat[i][k] and dist_mat[j][i]>0 and dist_mat[i][k]>0:
        #ans+=dist_mat[j][k]
        dist_mat[j][k]=0
      elif dist_mat[j][k]>dist_mat[j][i]+dist_mat[i][k] and dist_mat[j][i]>0 and dist_mat[i][k]>0:
        print(-1)
        exit()
for i in range(N):
  for j in range(N):
    ans +=dist_mat[i][j]
print(ans//2)
#print(ans//2)

Submission status: Time Limit Exceeded

Solution code:
import heapq
INFTY = 10**12
def dist(cur,b):
    d = [INFTY for _ in range(N)]
    d[cur[1]] = 0
    hist = [0 for _ in range(N)]
    hist[cur[1]] = 1
    heap = [cur]
    while heap:
        cur = heapq.heappop(heap)
        hist[cur[1]] = 1
        for x in B[cur[1]]:
            if hist[x[1]]==0:
                if d[x[1]]>cur[0]+x[0]:
                    d[x[1]] = cur[0]+x[0]
                    heapq.heappush(heap,(d[x[1]],x[1]))
    return d[b]
N = int(input())
A = {(i,j):INFTY for i in range(N) for j in range(N)}
for i in range(N):
    row = list(map(int,input().split()))
    for j in range(N):
        A[(i,j)] = row[j]
G = list(A.items())
G = sorted(G,key=lambda x:x[1])
B = {i:[] for i in range(N)}
ind = 0
for x in G:
    a,b = x[0][0],x[0][1]
    d = x[1]
    if d>0:
        dmin = dist([0,a],b)
#         print("dmin({},{})={}".format(a,b,dmin))
        if dmin>d:
            if (d,b) not in B[a]:
                B[a].append((d,b))
            if (d,a) not in B[b]:
                B[b].append((d,a))
        elif d>dmin:
            ind = 1
            break
#         print("B={}".format(B))
if ind==1:
    print(-1)
else:
    cnt = 0
    for a in B:
        for x in B[a]:
            cnt += x[0]
    print(cnt//2)

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import floyd_warshall

n=int(input())
arr=[list(map(int,input().split())) for _ in range(n)]
edge=[]
for i in range(n):
  for j in range(n):
    if i>=j:
      continue
    edge.append((arr[i][j],(i,j)))
edge=sorted(edge,key=lambda x:x[0])
g=[[float('inf')]*n for _ in range(n)]
for i in range(n):
  for j in range(n):
    g[i][j]=arr[i][j]
d=floyd_warshall(g)
ans=0
for w,(a,b) in edge:
  if d[a][b]<w:
    print(-1)
    break
  else:
    tmp=10**10
    for k in range(n):
      if k==a or k==b:
        continue
      tmp=min(tmp,d[a][k]+d[k][b])
    if w==tmp:
      continue
    else:
      ans+=w
else:
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import dijkstra

class UnionFind():
  def __init__(self,n):
    self.n=n
    self.root=[-1]*(n+1)
    self.rank=[0]*(n+1)
  def FindRoot(self,x):
    if self.root[x]<0:
      return x
    else:
      self.root[x]=self.FindRoot(self.root[x])
      return self.root[x]
  def Unite(self,x,y):
    x=self.FindRoot(x)
    y=self.FindRoot(y)
    if x==y:
      return
    else:
      if self.rank[x]>self.rank[y]:
        self.root[x]+=self.root[y]
        self.root[y]=x
      elif self.rank[x]<=self.rank[y]:
        self.root[y]+=self.root[x]
        self.root[x]=y
        if self.rank[x]==self.rank[y]:
          self.rank[y]+=1
  def isSameGroup(self,x,y):
    return self.FindRoot(x)==self.FindRoot(y)
  def Count(self,x):
    return -self.root[self.FindRoot(x)]

n=int(input())
arr=[list(map(int,input().split())) for _ in range(n)]
edge=[]
for i in range(n):
  for j in range(n):
    if i>=j:
      continue
    edge.append((arr[i][j],(i,j)))
edge=sorted(edge,key=lambda x:x[0])
g=[[float('inf')]*n for _ in range(n)]
ans=0
cnt=0
i=0
t=UnionFind(n)
checked=[0]*((n*(n-1))//2)
while cnt<n-1:
  w,(a,b)=edge[i]
  if t.isSameGroup(a,b)==False:
    g[a][b]=w
    g[b][a]=w
    checked[i]=1
    ans+=w
    t.Unite(a,b)
    cnt+=1
  i+=1
for i in range((n*(n-1))//2):
  if checked[i]==1:
    continue
  w,(a,b)=edge[i]
  cost=int(dijkstra(g,indices=a)[b])
  if w==cost:
    continue
  elif w<cost:
    g[a][b]=w
    g[b][a]=w
    ans+=w
  elif w>cost:
    print(-1)
    break
else:
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    A = []
    d = []
    for i in range(N):
        Ai = list(map(int, input().split()))
        A.append(Ai)
        for j in range(i+1, N):
            if Ai[j] > 0:
                d.append((Ai[j], i, j))
    d.sort(key=lambda x: x[0])


    def wf(dist):
        for i in range(N):
            for j in range(N):
                for k in range(N):
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
        return dist


    ok = len(d)+1
    ng = 0
    mid = len(d)
    while ok - ng > 1:
        dist = [[10 ** 10 for _ in range(N)] for _ in range(N)]
        for i in range(N):
            dist[i][i] = 0
        for x, i, j in d[:mid]:
            dist[i][j] = x
            dist[j][i] = x
        if wf(dist) == A:
            ok = mid
        else:
            ng = mid
            if ng == len(d):
                print(-1)
                exit()
        mid = (ok+ng)//2

    ans = 0
    for i in range(ok):
        ans += d[i][0]
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    A = []
    d = []
    for i in range(N):
        Ai = list(map(int, input().split()))
        A.append(Ai)
        for j in range(i+1, N):
            if Ai[j] > 0:
                d.append((Ai[j], i, j))
    d.sort(key=lambda x: x[0])


    def wf(dist):
        for i in range(N):
            for j in range(N):
                for k in range(N):
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
        return dist


    ok = len(d)+1
    ng = 0
    mid = (ok+ng)//2
    while ok - ng > 1:
        dist = [[10 ** 10 for _ in range(N)] for _ in range(N)]
        for i in range(N):
            dist[i][i] = 0
        for x, i, j in d[:mid]:
            dist[i][j] = x
            dist[j][i] = x
        if wf(dist) == A:
            ok = mid
        else:
            ng = mid
            if ng == len(d):
                print(-1)
                exit()
        mid = (ok+ng)//2

    ans = 0
    for i in range(ok):
        ans += d[i][0]
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n=int(input())
d=[]
ans=0
for i in range(n):
    tmp=[int(j) for j in input().split()]
    d.append(tmp)
for i in range(n):
    for j in range(i+1,n):
        ans+=d[i][j]

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 d[i][j]>d[i][k]+d[k][j]:
                print(-1)
                exit()
            elif d[i][j]==d[i][k]+d[k][j]:
                ans-=d[i][j]
                break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
d=[]
ans=0
for i in range(n):
    tmp=[int(j) for j in input().split()]
    d.append(tmp)
for i in range(n):
    for j in range(i+1,n):
        ans+=d[i][j]

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 d[i][j]>d[i][k]+d[k][j]:
                print(-1)
                exit()
            elif d[i][j]==d[i][k]+d[k][j]:
                ans-=d[i][j]
                break
print(ans)