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:
#!/usr/bin/env python3

import sys
# import time
# import math
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)



def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1             # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())


    # class PQueueMin:
    #     def __init__(self):
    #         self.pq = []    # 第一要素に cost、第二要素に ind が来る様にする
        
    #     def push(self, ind, cost):
    #         heappush(self.pq, [cost, ind])
        
    #     def pop(self):
    #         cost, ind = heappop(self.pq)
    #         return [ind, cost]

    #     def is_empty(self):
    #         return len(self.pq)==0



    # def dijkstra(adj_with_weight, start, goal):
    #     '''
    #     Dijkstra 法 O((E+V)lgV) (頂点を回るときに最小のものを取り出していくのに VlgV, cost の更新で ElgV)
    #     負辺を含まぬ重みつきグラフについて、ある頂点から他の頂点までの最短コストを貪欲に計算する
    #     '''
    #     V = len(adj_with_weight)
    #     cost = [inf] * V
    #     cost[start] = 0
    #     fixed = [False] * V
    #     pq = PQueueMin()
    #     # 最初は始点が必ずコスト最小。pq に突っ込む
    #     pq.push(start, cost[start])
    #     while not pq.is_empty():
    #         # 現段階で最短のコストとなっている頂点を選択
    #         u, cost_of_u = pq.pop()
    #         fixed[u] = True
    #         # 枝刈り
    #         if u == goal:
    #             return cost[goal]
    #         for v, weight_of_uv in adj_with_weight[u]:
    #             if not fixed[v] and cost[v] > cost_of_u + weight_of_uv:
    #                 cost[v] = cost_of_u + weight_of_uv
    #                 pq.push(v, cost[v])
    #     return inf


    class UnionFindTree:
        def __init__(self, num_of_elm):
            '''
            0 ... num_of_elem - 1 まで数字で表される (0-index) グループを管理する union find tree を作成する (O(n))
            '''
            self.n = num_of_elm
            self.table = [i for i in range(self.n)]    # table[ind] は ind の親の index を表す。ind == table[ind] の時そのグループの root である。
            self.rank = [0] * self.n    # root となる ind について rank[ind] はその木の深さを表す。それ以外の ind については意味を持たない。
            self.group_size = [1] * self.n    # root となる ind について group_size[ind] はそのグループに属するメンバの個数を表す。それ以外の ind については意味を持たない。
        
        def _find_set(self, x):
            '''
            x の属するグループ番号を O(α(n)) で求める
            '''
            parent = self.table[x]
            if x == parent:
                return x
            else:
                root = self._find_set(parent)
                # 経路圧縮
                self.table[x] = root
                return root
        
        def is_same(self, x, y):
            '''
            x と y が同じグループに属するか O(α(n)) で判定する
            '''
            return self._find_set(x) == self._find_set(y)
    
        def union(self, x, y):
            '''
            x と y の属するグループを O(α(n)) で統合する
            '''
            shallow_root = self._find_set(x)
            deep_root = self._find_set(y)
            if self.rank[shallow_root] > self.rank[deep_root]:
                shallow_root, deep_root = deep_root, shallow_root
            # そもそも同一グループだった時
            if shallow_root == deep_root:
                return False
            # グループが異なるので union
            else:
                self.table[shallow_root] = deep_root
                self.group_size[deep_root] += self.group_size[shallow_root]
                # 深さが等しかったときはつけ加えられた側の rank をインクリメントする
                if self.rank[shallow_root] == self.rank[deep_root]:
                    self.rank[deep_root] += 1
                return True
    
        def akin_num(self, x):
            '''
            x の属するグループのサイズを O(1) で計算する
            '''
            x_root = self._find_set(x)
            return self.group_size[x_root]
    
        def print_group_id(self):
            print([self._find_set(x) for x in self.table])


    # def update_matrix_joint(fixed_dist_matrix, i, j, w):
    #     """
    #     (i, j がすでに連結な時)
    #     i, j 間に新たに w の距離の道をはる。距離行列を更新する。
    #     """
    #     fixed_dist_matrix[i][j] = w
    #     fixed_dist_matrix[j][i] = w
    #     for k in range(n):
    #         if k != i:
    #             new_dist = min(fixed_dist_matrix[k][i], fixed_dist_matrix[k][j] + w)
    #             fixed_dist_matrix[k][i] = new_dist
    #             fixed_dist_matrix[i][k] = new_dist
    #         if k != j:
    #             new_dist = min(fixed_dist_matrix[k][j], fixed_dist_matrix[k][i] + w)
    #             fixed_dist_matrix[k][j] = new_dist
    #             fixed_dist_matrix[j][k] = new_dist
    
    def update_matrix_disjoint(fixed_dist_matrix, i, j, w, i_group, j_group):
        """
        i, j 間に新たに w の距離の道をはる。距離行列を更新する。        
        """
        fixed_dist_matrix[i][j] = w
        fixed_dist_matrix[j][i] = w
        for s, t in product(i_group, j_group):
            if s != i or t != j:
                new_dist = min(fixed_dist_matrix[s][t], fixed_dist_matrix[s][i] + w + fixed_dist_matrix[j][t])
                # print(f"{s} {t} {new_dist}")
                fixed_dist_matrix[s][t] = new_dist
                fixed_dist_matrix[t][s] = new_dist


    
    def struct_street(edges):
        n = len(adj_mat)
        total_length = 0
        # adj_list = [[] for _ in range(n)]
        
        uf = UnionFindTree(n)
        fixed_dist_matrix = [[inf] * n for _ in range(n)]
        for i in range(n):
            fixed_dist_matrix[i][i] = 0

        for (i, j), w in edges:
            # dist = dijkstra(adj_list, start=i, goal=j)
            # print(fixed_dist_matrix)
            dist = fixed_dist_matrix[i][j]
            if dist > w:
                # 辺をはる
                # adj_list[i].append((j, w))
                # adj_list[j].append((i, w))
                # if uf.is_same(i, j):
                #     update_matrix_joint(fixed_dist_matrix, i, j, w)
                # else:
                i_group = []
                j_group = []
                for ind in range(n):
                    if uf.is_same(i, ind):
                        i_group.append(ind)
                    if uf.is_same(j, ind):
                        j_group.append(ind)
                update_matrix_disjoint(fixed_dist_matrix, i, j, w, i_group, j_group)
                uf.union(i, j)
                total_length += w
            elif dist == w:
                # スルー
                continue
            else:
                # 構築不可能
                return -1
        return total_length

    


    n = ii()
    adj_mat = [lmi() for _ in range(n)]

    edges = []
    for i in range(n):
        for j in range(i+1, n):
            tmp = [(i, j), adj_mat[i][j]]
            edges.append(tmp)
    edges.sort(key=itemgetter(1))

    print(struct_street(edges))



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

#n =5
#ab =[[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]]

import itertools
ax = list(itertools.combinations(range(n),3))
res = 0

for i in ax:
    x =ab[i[0]][i[1]]
    y =ab[i[1]][i[2]]
    z =ab[i[2]][i[0]]
    u = max(x,y,z)
    if x+y+z -u < u:
        print(-1)
        exit()
    if  x+y+z -u == u:
        res += u

result = sum(map(sum, ab))

print(result//2-res)

Submission status: Time Limit Exceeded

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

#n =5
#ab =[[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]]

import itertools
ax = list(itertools.combinations(range(n),3))
res = 0

for i in ax:
    x =ab[i[0]][i[1]]
    y =ab[i[1]][i[2]]
    z =ab[i[2]][i[0]]
    if x+y+z -max(x,y,z) < max(x,y,z):
        print(-1)
        exit()
    if  x+y+z -max(x,y,z) == max(x,y,z):
        res += max(x,y,z)

result = sum(map(sum, ab))

print(result//2-res)

Submission status: Time Limit Exceeded

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

#n =5
#ab =[[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]]
f_inf = float("inf")
dp =[[f_inf for i in range(n)] for j in range(n)]
res = 0
for i in range(n):
    for j in range(i+1,n):
        for k in range(j+1,n):  
            x = ab[i][j]
            y = ab[i][k]
            z = ab[j][k]
            if x+y+z -max(x,y,z) < max(x,y,z):
                print(-1)
                exit()
            if  x+y+z -max(x,y,z) == max(x,y,z):
                res += max(x,y,z)
                

result = sum(map(sum, ab))

print(result//2-res)

Submission status: Time Limit Exceeded

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

#n =5
#ab =[[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]]
dp =[[0 for i in range(n)] for j in range(n)]
res = 0
for i in range(n):
    for j in range(i+1,n):
        for k in range(j+1,n):  
            x = ab[i][j]
            y = ab[i][k]
            z = ab[j][k]
            if x+y+z -max(x,y,z) < max(x,y,z):
                print(-1)
                exit()
            if x + y == z :
                if dp[i][j] == 0:
                    dp[i][j] = x
                    res += x
                if dp[i][k] ==0:
                    dp[i][k] =y
                    res += y
                dp[j][k] = z
            if y + z == x :
                if dp[i][k] == 0:
                    dp[i][k] = y
                    res += y
                if dp[j][k] ==0:
                    dp[j][k] =z
                    res += z
                dp[i][j] = x
            if z + x == y :
                if dp[j][k] == 0:
                    dp[j][k] = z
                    res += z
                if dp[i][j] ==0:
                    dp[i][j] =x
                    res += x
                dp[i][k] = y
                
for i in range(n):
    for j in range(i+1,n):
        if dp[i][j]==0:
            res +=ab[i][j]

print(res)

Submission status: Time Limit Exceeded

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

import sys
# import time
# import math
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)



def main():
    mod = 1000000007                # 10^9+7
    # inf = float('inf')              # sys.float_info.max = 1.79...e+308
    inf = 2 ** 64 - 1             # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())


    class PQueueMin:
        def __init__(self):
            self.pq = []    # 第一要素に cost、第二要素に ind が来る様にする
        
        def push(self, ind, cost):
            heappush(self.pq, [cost, ind])
        
        def pop(self):
            cost, ind = heappop(self.pq)
            return [ind, cost]

        def is_empty(self):
            return len(self.pq)==0



    def dijkstra(adj_with_weight, start, goal):
        '''
        Dijkstra 法 O((E+V)lgV) (頂点を回るときに最小のものを取り出していくのに VlgV, cost の更新で ElgV)
        負辺を含まぬ重みつきグラフについて、ある頂点から他の頂点までの最短コストを貪欲に計算する
        '''
        V = len(adj_with_weight)
        cost = [inf] * V
        cost[start] = 0
        fixed = [False] * V
        pq = PQueueMin()
        # 最初は始点が必ずコスト最小。pq に突っ込む
        pq.push(start, cost[start])
        while not pq.is_empty():
            # 現段階で最短のコストとなっている頂点を選択
            u, cost_of_u = pq.pop()
            fixed[u] = True
            # 枝刈り
            if u == goal:
                return cost[goal]
            
            for v, weight_of_uv in adj_with_weight[u]:
                if not fixed[v] and cost[v] > cost_of_u + weight_of_uv:
                    cost[v] = cost_of_u + weight_of_uv
                    pq.push(v, cost[v])
        return inf

    
    def struct_street(edges):
        n = len(adj_mat)
        total_length = 0
        adj_list = [[] for _ in range(n)]

        for (i, j), w in edges:
            dist = dijkstra(adj_list, start=i, goal=j)
            if dist > w:
                # 辺をはる
                adj_list[i].append((j, w))
                adj_list[j].append((i, w))
                total_length += w
            elif dist == w:
                # スルー
                continue
            else:
                # 構築不可能
                return -1
        return total_length

    


    n = ii()
    adj_mat = [lmi() for _ in range(n)]

    edges = []
    for i in range(n):
        for j in range(i+1, n):
            tmp = [(i, j), adj_mat[i][j]]
            edges.append(tmp)
    edges.sort(key=itemgetter(1))

    print(struct_street(edges))



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

import sys
# import time
# import math
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)



def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1             # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())


    class PQueueMin:
        def __init__(self):
            self.pq = []    # 第一要素に cost、第二要素に ind が来る様にする
        
        def push(self, ind, cost):
            heappush(self.pq, [cost, ind])
        
        def pop(self):
            cost, ind = heappop(self.pq)
            return [ind, cost]

        def is_empty(self):
            return len(self.pq)==0



    def dijkstra(adj_with_weight, start, goal):
        '''
        Dijkstra 法 O((E+V)lgV) (頂点を回るときに最小のものを取り出していくのに VlgV, cost の更新で ElgV)
        負辺を含まぬ重みつきグラフについて、ある頂点から他の頂点までの最短コストを貪欲に計算する
        '''
        V = len(adj_with_weight)
        cost = [float('inf')] * V
        cost[start] = 0
        fixed = [False] * V
        pq = PQueueMin()
        # 最初は始点が必ずコスト最小。pq に突っ込む
        pq.push(start, cost[start])
        while not pq.is_empty():
            # 現段階で最短のコストとなっている頂点を選択
            u, cost_of_u = pq.pop()
            fixed[u] = True
            for v, weight_of_uv in adj_with_weight[u]:
                if not fixed[v] and cost[v] > cost_of_u + weight_of_uv:
                    cost[v] = cost_of_u + weight_of_uv
                    pq.push(v, cost[v])
        return cost[goal]

    
    
    def struct_street(adj_mat):
        n = len(adj_mat)
        total_length = 0
        adj_list = [[] for _ in range(n)]
        edges = []
        for i in range(n):
            for j in range(i+1, n):
                tmp = [(i, j), adj_mat[i][j]]
                edges.append(tmp)
        edges.sort(key=itemgetter(1))

        for (i, j), w in edges:
            dist = dijkstra(adj_list, start=i, goal=j)
            if dist > w:
                # 辺をはる
                adj_list[i].append((j, w))
                adj_list[j].append((i, w))
                total_length += w
            elif dist == w:
                # スルー
                continue
            else:
                # 構築不可能
                return -1
        return total_length

    
        


    n = ii()
    adj_mat = [lmi() for _ in range(n)]
    print(struct_street(adj_mat))



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import floyd_warshall


def main():
    N = int(input())
    A = [list(map(int, input().split(' '))) for _ in range(N)]
    wf = floyd_warshall(A)
    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()
    ans = 0
    for edge in edges:
        cost, from_node, to_node = edge
        if A[from_node][to_node] > wf[from_node][to_node]:
            print(-1)
            return
        to_be_added = True
        for via_node in range(N):
            if via_node in [from_node, to_node]:
                continue
            if wf[from_node][to_node] == wf[from_node][via_node] + wf[via_node][to_node]:
                to_be_added = False
                break
        if to_be_added:
            ans += A[from_node][to_node]
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import floyd_warshall


def main():
    N = int(input())
    A = [list(map(int, input().split(' '))) for _ in range(N)]
    wf = floyd_warshall(A)
    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])
    ans = 0
    for edge in edges:
        cost, from_node, to_node = edge
        if A[from_node][to_node] > wf[from_node][to_node]:
            print(-1)
            return
        to_be_added = True
        for via_node in range(N):
            if via_node in [from_node, to_node]:
                continue
            if wf[from_node][to_node] == wf[from_node][via_node] + wf[via_node][to_node]:
                to_be_added = False
                break
        if to_be_added:
            ans += A[from_node][to_node]
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def warshall_floyd(N, A):
    dist = [[A[i][j] for i in range(N)] for j in range(N)]
    for i in range(N):
        for j in range(N):
            for k in range(N):
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist


def main():
    N = int(input())
    A = [list(map(int, input().split(' '))) for _ in range(N)]
    wf = warshall_floyd(N, A)
    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])
    ans = 0
    for edge in edges:
        cost, from_node, to_node = edge
        if A[from_node][to_node] > wf[from_node][to_node]:
            print(-1)
            return
        to_be_added = True
        for via_node in range(N):
            if via_node in [from_node, to_node]:
                continue
            if wf[from_node][to_node] == wf[from_node][via_node] + wf[via_node][to_node]:
                to_be_added = False
                break
        if to_be_added:
            ans += A[from_node][to_node]
    print(ans)


if __name__ == '__main__':
    main()

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)
        if node == to_node:
            break
        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()