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:
import copy
n = int(input())

alist = []
blist = []
ans = 0
for i in range(n):
    a = list(map(int,input().split()))
    ans += sum(a)
    alist.append(copy.copy(a))
    blist.append(copy.copy(a))
def warshall_floyd(d,ans):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if i == k or j == k or i == j:
                    continue
                elif d[i][j] > d[i][k] + d[k][j]:
                    return -1
                elif d[i][j] == d[i][k] + d[k][j]:
                    ans -= blist[i][j]
    return ans//2

print(warshall_floyd(alist,ans))

Submission status: Wrong Answer

Solution code:
import copy
n = int(input())

ans = 0
def warshall_floyd(d):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if i == k or j == k:
                    continue
                elif d[i][j] > d[i][k] + d[k][j]:
                    print(i,j,k)
                    print(d)
                    print(d[i][j],d[i][k],d[k][j])
                    return -1
                elif d[i][j] == d[i][k] + d[k][j]:
                    blist[i][j] = 0
    return sum([sum(l) for l in blist])//2

alist = []
blist = []
for i in range(n):
    a = list(map(int,input().split()))
    alist.append(copy.copy(a))
    blist.append(copy.copy(a))


ans = warshall_floyd(alist)
print(ans)

Submission status: Wrong Answer

Solution code:
import copy
n = int(input())
alist = []
blist = []
A = []
ans = 0
def warshall_floyd(d):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j], d[i][k]+d[k][j])

for i in range(n):
    a = list(map(int,input().split()))
    alist.append(copy.copy(a))
    blist.append(copy.copy(a))
    for j in range(i+1,n):
        ans += a[j]
        A.append((a[j],i,j))

warshall_floyd(blist)

A.sort()
for l in A:
    a,i,j = l[0],l[1],l[2]
    if blist[i][j] < alist[i][j]:
        print(-1)
        quit()
    for k in range(n):
        if i == k or j == k:
            continue
        elif blist[i][j] == alist[i][j]:
            if a == blist[i][k] + blist[k][j]:
                ans -= a


print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
alist = []
A = []
ans = 0
for i in range(n):
    a = list(map(int,input().split()))
    alist.append(a)
    for j in range(i+1,n):
        ans += a[j]
        A.append((a[j],i,j))
A.sort()
for l in A:
    a,i,j = l[0],l[1],l[2]
    for k in range(n):
        if i == k or j == k:
            continue
        elif a > alist[i][k] + alist[k][j]:
            print(-1)
            quit()
        elif a == alist[i][k] + alist[k][j]:
            ans -= a
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [list(map(int,input().split())) for _ in range(n)]
ans = 0
for i in range(n-1):
    for j in range(i+1,n):
        for k in range(n):
            if k == i or k == j:
                continue
            if a[i][j] == a[i][k] + a[k][j]:
                ans -= a[i][j]
            elif a[i][j] > a[i][k] + a[k][j]:
                print(-1)
                quit()
for i in range(n-1):
    for j in range(i+1,n):
        ans += a[i][j]
print(ans)

Submission status: Wrong Answer

Solution code:
def warshall_floyd(d,n):
    ans = sum([sum(i) for i in d])
    for i in range(n):
        d[i][i] = 10 ** 18
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if i == j:
                    continue
                if d[i][k] + d[k][j] < d[i][j]:
                    return -1 
                elif d[i][k] + d[k][j] == d[i][j]:
                    ans -= d[i][j]
    return ans // 2
  
n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
ans = warshall_floyd(a,n)
print(ans)

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    A = [list(map(int, input().split())) for _ in range(N)]
    B = [{} for _ in range(N)]
    T = []
    for i in range(N):
        for j in range(i + 1, N):
            T.append((A[i][j], i, j))
    T.sort()
    r = 0
    for t, a, b in T:
        if b in B[a]:
            if B[a][b] == t:
                continue
            if B[a][b] < t:
                return -1
        S = [(a, b, t)]
        r += t
        for k, v in B[a].items():
            S.append((b, k, v + t))
        for k, v in B[b].items():
            S.append((a, k, v + t))
        for i, j, v in S:
            if i == j:
                continue
            if A[i][j] > v:
                return -1
            if j in B[i] and B[i][j] <= v:
                continue
            B[i][j] = B[j][i] = v
    return r

print(main())

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    A = [list(map(int, input().split())) for _ in range(N)]
    B = [{} for _ in range(N)]
    T = []
    for i in range(N):
        for j in range(i + 1, N):
            T.append((A[i][j], i, j))
    T.sort()
    r = 0
    for t, a, b in T:
        if b in B[a]:
            if B[a][b] == t:
                continue
            if B[a][b] < t:
                return -1
        S = [(a, b, t)]
        r += t
        for k, v in B[a].items():
            S.append((b, k, v + t))
        for k, v in B[b].items():
            S.append((a, k, v + t))
        for i, j, v in S:
            if A[i][j] > v:
                return -1
            if j in B[i] and B[i][j] <= v:
                continue
            B[i][j] = B[j][i] = v
    return r

print(main())

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    A = [list(map(int, input().split())) for _ in range(N)]
    B = [{} for _ in range(N)]
    T = []
    for i in range(N):
        for j in range(i + 1, N):
            T.append((A[i][j], i, j))
    T.sort()
    r = 0
    for t, a, b in T:
        if b in B[a]:
            if B[a][b] == t:
                continue
        S = [(a, b, t)]
        r += t
        for k, v in B[a].items():
            S.append((b, k, v + t))
        for k, v in B[b].items():
            S.append((a, k, v + t))
        for i, j, v in S:
            if A[i][j] > v:
                return -1
            if j in B[i] and B[i][j] <= v:
                continue
            B[i][j] = B[j][i] = v
    return r

print(main())

Submission status: Wrong Answer

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

# dは隣接頂点間のコスト、Nは頂点の個数
def warshall_floyd(d):
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if d[i][j] > d[i][k] + d[k][j]:
                    print(-1)
                    sys.exit()
                elif d[i][j] == d[i][k] + d[k][j] and k != i and k != j:
                    delete.append((i, j))
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d
delete = []
# input
N = int(input())
inf = float("inf")

# d[i][v]:辺(i, v)間のコスト、存在しなければinf
d = [[int(x) for x in input().split()] for _ in range(N)]
from copy import deepcopy
d_ = deepcopy(d)
d = warshall_floyd(d)

ans = 0

for i in range(N):
    for j in range(i + 1, N):
        ans += d_[i][j]
for i, j in delete:
    if i > j:
        ans -= d_[i][j]
print(ans)

Submission status: Wrong Answer

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

dis = 0
for k in range(n):
    for i in range(n):
        for j in range(n):
            if i == j:continue
            temp = a[i][k] + a[k][j]
            if a[i][j] > temp:
                print(-1)
                exit()
            if temp == a[i][j] and k != i and k != j:
                #print(k, i, j, temp)
                dis -= temp

for i in range(n):
    for j in range(n):
        dis += a[i][j]

print(dis // 2)

Submission status: Wrong Answer

Solution code:
n = int(input())

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

# d[i][j]は2頂点間i, j間の移動コストを格納, Vは頂点数
ans = 0
def warshall_floyd(d, V):
    global ans
    for k in range(V):
        for i in range(V):
            for j in range(V):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d  # d[i][j]に頂点i, j間の最短距離を格納


d = warshall_floyd(dl, n)

if d != dl:
    print(-1)
    exit()

ans = 0
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        flag = True
        for k in range(n):
            if i == k or k == j:
                continue
            if d[i][j] == d[i][k] + d[k][j]:
                flag = False
        if flag:
            ans += d[i][j]
print(ans//2)

Submission status: Wrong Answer

Solution code:
n,*a = map(int,open(0).read().split())
a = [(a[i*n+j],i,j) for i in range(n) for j in range(i+1,n)]
asort = sorted(a)

shortest_path = [[float('inf')]*n for _ in range(n)]
for i in range(n):
    shortest_path[i][i] = 0

ans = 0

for d,i,j in asort:
    if  shortest_path[i][j] < d:
        print(-1)
        break
    elif shortest_path[i][j] > d:
        shortest_path[i][j] = d
        shortest_path[j][i] = d
        ans += d
        for k in range(n):
            shortest_path[i][k] = min(shortest_path[i][k], d + shortest_path[j][k])
            shortest_path[k][i] = shortest_path[i][k]
            shortest_path[j][k] = min(shortest_path[j][k], d + shortest_path[i][k])
            shortest_path[k][j] = shortest_path[j][k]
        
else:
    print(ans)

Submission status: Wrong Answer

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

n = int(input())


import copy

def warshall_floyd(dp):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dp[i][j] = min(dp[i][j] , dp[i][k] + dp[k][j])
    return dp

d = [[0]*n for _ in range(n)]

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

hyou = copy.deepcopy(d)
d = warshall_floyd(d)

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


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def root(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.root(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.root(x)
        y = self.root(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.root(x)]

    def is_same(self, x, y):
        return self.root(x) == self.root(y)

    def members(self, x):  # 計算量n
        root = self.root(x)
        return [i for i in range(self.n) if self.root(i) == root]

    def all_roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.all_roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.all_roots()}

    def __str__(self):
        return ''.join('{}: {}'.format(r, self.members(r)) for r in self.all_roots())

edges = []
for i in range(n):
    for j in range(i+1,n):
        edges.append((d[i][j], i, j))
edges.sort()

def kruskal(n, edges):#edges: wでソート済み
    U = UnionFind(n)
    res = 0
    for e in edges:
        w, s, t = e
        if not U.is_same(s, t):
            res+=w
            U.union(s, t)
    return res


print(kruskal(n, edges))

Submission status: Wrong Answer

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

from scipy.sparse.csgraph import floyd_warshall
wf=floyd_warshall(a)

if not (a==wf).all() :
    print(-1)
    exit()

Submission status: Wrong Answer

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

for u in range(N):
    C = list(map(int, input().split()))
    for v in range(N):
        if u==v: # INFのままにする
            continue
        cost[u][u] = C[u]
 
ans = 0
for u in range(N):
    for v in range(u+1,N):
        mn = INF # u-w-vのような経路の中で最小の距離を求める
        for w in range(N):
            mn = min(mn, cost[u][w]+cost[w][v])    
        if (cost[u][v] > mn): # 与えられた行列が最短経路ではない
            print (-1)
            exit()
        elif (cost[u][v] < mn): # 等しくない場合はu-vを直接結ぶ橋が必要 
            ans += cost[u][v]                      
print (ans)

Submission status: Wrong Answer

Solution code:
from copy import copy
n = int(input())
INF = 10**12

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

B = [[1]*n for _ in range(n)]
G = copy(A)

for k in range(n):
  for i in range(n):
    for j in range(n):
      G[i][j] = min(G[i][j], G[i][k]+G[k][j])
      if not (i==j or j==k or k==i):
        if G[i][j] == G[i][k]+G[k][j]:
          B[i][j] = 0
      
if A==G:
  ans = 0
  for i in range(n):
    for j in range(i+1,n):      
      ans += G[i][j] * B[i][j]
  print(ans)
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall

n = int(readline())
memo_graph = [list(map(int, readline().split())) for _ in range(n)]
cost = floyd_warshall(csr_matrix(memo_graph))
cnt_1 = 0
cnt_2 = 0
for i in range(n):
    for j in range(n):
        if int(cost[i][j]) != memo_graph[i][j]:
            print(-1)
            exit()
        if cost[i][j] == 0:
            continue
        cnt_1 += cost[i][j]
s = set()
for k in range(n):
    for i in range(n):
        for j in range(n):
            # 3頂点が異なってかつ、経由のが近い場合は直接の辺は不要
            if i != j and j != k and k != i and cost[i][k] + cost[k][j] == cost[i][j]:
                if (i, j) not in s:
                    s.add((i, j))
                    cnt_2 += cost[i][j]
print((cnt_1 - cnt_2) // 2)

Submission status: Wrong Answer

Solution code:
def warshall_floyd(G, n):
    global c
    for k in range(n):
        for i in range(n):
            if i == k:
                continue
            for j in range(n):
                if j == k:
                    continue
                if G[i][j] == G[i][k] + G[k][j]:
                    c += G[i][j]
                elif G[i][j] > G[i][k] + G[k][j]:
                    print(-1)
                    exit()

n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
c = 0
warshall_floyd(a, n)
sum = 0
for i in a:
    for j in i:
        sum += j
print((sum - c) // 2)

Submission status: Wrong Answer

Solution code:
# ワーシャルフロイド　全点最短経路、負の距離あっても可　o(n**3)
def warshall_floyd(d,ans):
    #d[i][j]: iからjへの最短距離
    flag=True
    for k in range(n):
        for i in range(n):
            for j in range(n):
                x = d[i][j]
                y = d[i][k] + d[k][j]
                if x==y and k!=i and k!=j:
                    ans-=y
                elif x<y or (x==y and (k==i or k==j)) :
                    continue
                else:
                    flag=False
                    break

    return flag,ans

##############################
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])


a1,a2=warshall_floyd(d,ans)

if a1:
    print(a2//2)
else:
    print(-1)

Submission status: Wrong Answer

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

for k in range(n):
  for i in range(n):
    for j in range(n):
      if A[i][j] > A[i][k]+ A[k][j]:
        print(-1)
        exit()
        
ans = 0     
for i in range(n-1):
  ans += min(A[i][i+1:])
print(ans)

Submission status: Wrong Answer

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

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

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

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

        return d,prev

    def shortestpaths(self):
        paths = []
        for i in range(self.v):
            paths.append(self.dijkstra(i)[0])
        return paths

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

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

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

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

    print(s//2)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

def sol():
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d = A[i][k] + A[k][j]
                if d < A[i][j]:
                    return - 1

    INF = 10**18
    ret = 0
    for i in range(N):
        for j in range(i + 1, N):
            if A[i][j] == INF:
                continue
            for k in range(N):
                if k == i or k == j:
                    continue
                d = A[i][k] + A[k][j]
                if d == A[i][j]:
                    A[i][j] = INF
                    break
            else:
                ret += A[i][j]
    return ret

print(sol())

Submission status: Wrong Answer

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

def sol():
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d = A[i][k] + A[k][j]
                if d < A[i][j]:
                    return - 1

    INF = 10**18
    ret = 0
    for i in range(N):
        for j in range(i + 1, N):
            for k in range(N):
                if k == i or k == j:
                    continue
                d = A[i][k] + A[k][j]
                if d == A[i][j]:
                    A[i][j] = INF
                    break
            else:
                ret += A[i][j]
    return ret

print(sol())

Submission status: Wrong Answer

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

def sol():
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d = A[i][k] + A[k][j]
                if d < A[i][j]:
                    return - 1

    INF = 10**18
    ret = 0
    for i in range(N):
        for j in range(i + 1, N):
            for k in range(N):
                if k == i or k == j:
                    continue
                d = A[i][k] + A[k][j]
                if d == A[i][j]:
                    ret += A[i][j]
                    A[i][j] = INF
                    break
    return ret

print(sum(sum(a) for a in A) // 2 - sol())

Submission status: Wrong Answer

Solution code:
"""from collections import *
from itertools import *
from bisect import *
from heapq import *

import math
from fractions import gcd"""
from heapq import*
N=int(input())
A=[list(map(int,input().split())) for i in range(N)]
for k in range(N):
    for i in range(N):
        for j in range(N):
            if A[i][j]>A[i][k]+A[k][j]:
                print(-1)
                exit()
res = 0
for i in range(N-1):
    for j in range(i+1, N):
        for k in range(N):
            if k==i or k == j:
                continue
            if A[i][j]==A[i][k]+A[k][j]:
                break
            else:
                res += A[i][j]
print(res)

Submission status: Wrong Answer

Solution code:
"""from collections import *
from itertools import *
from bisect import *
from heapq import *

import math
from fractions import gcd"""
#from heapq import*
N=int(input())
A=[list(map(int,input().split())) for i in range(N)]

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

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

Alst=[[A[i][m],i,m] for i in range(N) for m in range(N)]
Alst=sorted(Alst,key=lambda x:x[0])
uf=UnionFind(N)
usedpath=set()
value=0

for B,i,m in Alst:
    if not uf.same(i,m):
        uf.union(i,m)
        usedpath.add(i*300+m)
        value+=B
        if uf.group_count()==1:
            break

idle_max=10**18
d=[[idle_max for i in range(N)] for m in range(N)]
for i in range(N):
    d[i][i]=0
for i in usedpath:
    i,m=i//300,i%300
    d[i][m]=A[i][m]
    d[m][i]=A[m][i]

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

for B,i,m in Alst:
    if d[i][m]<A[i][m]:
        print(-1)
        exit()
    if d[i][m]>A[i][m]:
        d[i][m]=A[i][m]
        d[m][i]=A[m][i]
        value+=A[i][m]

        for i1 in range(N):
            for j in range(N):
                 d[i1][j] = min(d[i1][j], d[i1][i] + d[i][j])
                 #d[i1][j] = min(d[i1][j], d[i1][m] + d[m][j])


print(value)