Problem:


Score : 500 points

Problem Statement

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

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

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

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

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

Constraints

1 \leq N \leq 300

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

A_{i, i} = 0

Inputs

Input is given from Standard Input in the following format:

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

Outputs

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

Sample Input 1

3
0 1 3
1 0 2
3 2 0

Sample Output 1

3

The network below satisfies the condition:

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

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

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

Sample Input 2

3
0 1 3
1 0 1
3 1 0

Sample Output 2

-1

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

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

Sample Input 3

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

Sample Output 3

82

Sample Input 4

3
0 1000000000 1000000000
1000000000 0 1000000000
1000000000 1000000000 0

Sample Output 4

3000000000



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


Sample output:
3

Submission status: Wrong Answer

Solution code:
def warshall_floyd(d,ans):
    p = ans
    for k in range(n):
        for i in range(n):
            for j 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]:
                    p -= d[i][j]
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return p

##############################
n = int(input())

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

print(warshall_floyd(d,ans)//2)

Submission status: Wrong Answer

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


    def warshall_floyd(adj_mat_with_weight):
        '''
        Warshall-Floyd 法 (O(V^3), 1 sec だと v~500 とかが限界)
        全点対間の最短経路を三次元 DP で求める
            - 定式化
            - dp[k+1][i][j] を 0...k, i, j なる頂点を使用できる時の i~j 最短距離とする (k+1=0 の時は e(i,j))
            - dp[k+1][i][j] = min(dp[k][i][j], dp[k][i][k+1]+dp[k][k+1][j])
            - 最後に必要なのは dp[V][i][j] 。上の漸化式をみるに 2 次元 array があれば使いまわしてメモリ節約できる。
        Args:
            adj_mat_with_weight (list): 重みを記録した隣接行列 (非接続頂点は inf)
        Returns:
            dp (list): dp[i][j] を見れば全頂点を使用可能な時の i j 最短距離がわかる。最後に dp[i][i] が負になっていたら負サイクルが存在するということ
        '''
        V = len(adj_mat_with_weight)
        # テーブル初期化
        dp = deepcopy(adj_mat_with_weight)
        for i in range(V):
            dp[i][i] = 0
        # 漸化式を解く
        for k in range(1, V+1):
            for i in range(V):
                for j in range(V):
                    # new 2d-table # old 2d-table
                    dp[i][j] = min(dp[i][j], dp[i][k-1]+dp[k-1][j])
        return dp

    def check_possible_structure(dp, adj_mat):
        n = len(adj_mat)
        for i in range(n):
            for j in range(i+1, n):
                if dp[i][j] < adj_mat[i][j]:
                    return False
        return True

    def calc_minimum_street(dp, adj_mat):
        n = len(adj_mat)
        total_dist = 0
        for i in range(n):
            for j in range(i+1, n):
                total_dist += adj_mat[i][j]
        # 削除していく
        for i in range(n):
            for j in range(i+1, n):
                # (i, j) の距離について
                dist = adj_mat[i][j]
                for k in range(n):
                    if k != i and k != j and dp[i][k] + dp[k][j] == dist:
                        total_dist -= dist
        return total_dist
    
    
    n = ii()
    adj_mat = [lmi() for _ in range(n)]
    dp = warshall_floyd(adj_mat)

    if not check_possible_structure(dp, adj_mat):
        print(-1)
    else:
        print(calc_minimum_street(dp, adj_mat))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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 が非連結な時)
        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:
                assert fixed_dist_matrix[s][t] == inf
                new_dist = 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: Wrong Answer

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 update_matrix(fixed_dist_matrix, i, j, w):
        """
        i, j 間に新たに w の距離の道をはる。距離行列を更新する。
        """
        n = len(fixed_dist_matrix)
        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 struct_street(edges):
        n = len(adj_mat)
        total_length = 0
        # adj_list = [[] for _ in range(n)]
        
        fixed_dist_matrix = [[inf] * n for _ in range(n)]

        for (i, j), w in edges:
            # dist = dijkstra(adj_list, start=i, goal=j)
            dist = fixed_dist_matrix[i][j]
            if dist > w:
                # 辺をはる
                # adj_list[i].append((j, w))
                # adj_list[j].append((i, w))
                update_matrix(fixed_dist_matrix, i, j, 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: Wrong Answer

Solution code:
N = int(input())
INF = 10**100
A = []

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

def check():
    ans = 0
    for i in range(N):
        for j in range(i+1,N):
            min_dist = INF
            for k in range(N):
                if k != i and k != j:
                    min_dist = min(min_dist,A[i][k]+A[k][j])
            if A[i][j] == min_dist:
                A[i][j] = INF
                A[j][i] = INF
            elif A[i][j] > min_dist:
                return -1
            else:
                ans += A[i][j]
    return ans

print(check())

Submission status: Wrong Answer

Solution code:
N = int(input())
INF = 10**15
A = []

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

def check():
    ans = 0
    for i in range(N):
        for j in range(i+1,N):
            min_dist = INF
            for k in range(N):
                if k != i and k != j:
                    min_dist = min(min_dist,A[i][k]+A[k][j])
            if A[i][j] == min_dist:
                A[i][j] = INF
                A[j][i] = INF
            elif A[i][j] > min_dist:
                return -1
            else:
                ans += A[i][j]
    return ans

print(check())

Submission status: Wrong Answer

Solution code:
N = int(input())
INF = 10**15
A = []

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

def check():
    ans = 0
    for i in range(N):
        for j in range(i+1,N):
            min_dist = INF
            for k in range(N):
                if k != i and k != j:
                    min_dist = min(min_dist,A[i][k]+A[k][j])
            print(i+1,j+1,min_dist)
            if A[i][j] == min_dist:
                A[i][j] = INF
                A[j][i] = INF
            elif A[i][j] > min_dist:
                return -1
            else:
                ans += A[i][j]
    return ans

print(check())

Submission status: Wrong Answer

Solution code:
N=int(input())
A=[list(map(int,input().split())) for _ in range(N)]
inf=10**11
g=[[inf]*N for _ in range(N)]
B=[]

for i in range(N):
    g[i][i]=0
    for j in range(i+1,N):
        B.append((A[i][j],i,j))

B.sort(key=lambda x:x[0])
ans=0
for i in range(len(B)):
    w,u,v=B[i]
    g[u][v]=min(g[u][v],w)
    g[v][u]=min(g[v][u],w)
    ans+=w

    for j in range(N):
        for k in range(N):
            g[j][k]=min(g[j][k],g[j][u]+g[u][v]+g[v][k])
            g[j][k]=min(g[j][k],g[j][v]+g[v][u]+g[u][k])

    flag=True
    for j in range(N):
        for k in range(N):
            if g[j][k]!=A[j][k]:
                flag=False
                break
        if flag==False:
            break

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

Submission status: Wrong Answer

Solution code:
import heapq
import sys
N = int(input())

HQ = []
g = [[]*N for _ in range(N)]
all = 0
for i in range(N):
  temp = list(map(int,(input().split())))
  g[i] = temp
  all += sum(temp)
#print(g,all)

for k in range(N):
  for i in range(N):
    for j in range(N):
      if g[i][j] > g[i][k] + g[k][j]:
        print("-1")
        sys.exit()
      elif g[i][j] == g[i][k] + g[k][j] and i != j and j != k and k != i:
        all -= g[i][j]
ans = all//2
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
import sys
N = int(input())

HQ = []
g = [[]*N for _ in range(N)]
all = 0
for i in range(N):
  temp = list(map(int,(input().split())))
  g[i] = temp
  all += sum(temp)
#print(g,all)

for k in range(N):
  for i in range(N):
    for j in range(N):
      if g[i][j] > g[i][k] + g[k][j]:
        print("-1")
        sys.exit()
      elif g[i][j] == g[i][k] + g[k][j] and i != j and j != k and k != i:
        #print(i,j,g[i][j])
        all -= g[i][j]
print(all//2)

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n = inp()
a = [inpl() for _ in range(n)]
res = 0
fin = set()
for k in range(n):
    for i in range(n):
        for j in range(n):
            d = a[i][k] + a[k][j]
            if a[i][j] > d:
                print(-1)
                quit()
            if a[i][j] == d and i != k and j != k:
                if i > j: i,j = j,i
                fin.add((i,j))

for i in range(n):
    for j in range(i+1,n):
        if (i,j) in fin: continue
        res += a[i][j]
print(res)

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n = inp()
a = [inpl() for _ in range(n)]
res = sum(sum(i) for i in a)//2
fin = set()
for k in range(n):
    for i in range(n):
        for j in range(n):
            d = a[i][k] + a[k][j]
            if a[i][j] > d:
                print(-1)
                quit()
            if a[i][j] == d and i != k and j != k:
                if i > j: i,j = j,i
                fin.add((i,j))

for i,j in list(fin):
    # print(i,j)
    res -= a[i][j]
print(res)

Submission status: Wrong Answer

Solution code:
n=int(input())
abc=list("abcdefghijklmnopqrstuvwxyz")

D={}
for a in abc:
    D[a]=0

for i in range(n):
    s=input()
    for a in abc:
        now=D[a]
        num=s.count(a)
        if i==0:
            D[a]=num
        else:
            D[a]=min(now,num)
ans=""
#print(D)
for s,v in D.items():
    ans+=s*v
    #print(s)
#ans="".join(sorted(ans))
print(ans)