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:
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]

graph_mins = []
for i in range(n):
    for j in range(i+1, n):
        graph_mins.append([i, j, a[i][j]])
graph_mins = sorted(graph_mins, key=lambda x:x[2])

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

f = True
ans = 0
for i in range(len(graph_mins)):
    v, t, d = graph_mins[i][0], graph_mins[i][1], graph_mins[i][2]
    if min_dists[v][t] < d:
        f = False
        break
    elif min_dists[v][t] > d:
        ans += d

        for j in range(n):
            min_dists[v][j] = min(d + min_dists[t][j], min_dists[v][j])
            min_dists[j][v] = min_dists[v][j]

        for j in range(n):
            min_dists[t][j] = min(d + min_dists[v][j], min_dists[t][j])
            min_dists[j][t] = min_dists[t][j]

if f:
    print(ans)
else:
    print(-1)

Submission status: Wrong Answer

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

graph_mins = []
for i in range(n):
    for j in range(i+1, n):
        graph_mins.append([i, j, a[i][j]])

graph_mins = sorted(graph_mins, key=lambda x:x[2])

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

f = True
ans = 0
for i in range(len(graph_mins)):
    v, t, d = graph_mins[i][0], graph_mins[i][1], graph_mins[i][2]
    # print(graph_mins[i], min_dists)
    if min_dists[v][t] < d:
        f = False
        break
    elif min_dists[v][t] > d:
        ans += d

        # update min_dists
        for j in range(n):
            min_dists[v][j] = min(d + min_dists[t][j], min_dists[v][j])
            min_dists[t][j] = min(d + min_dists[v][j], min_dists[t][j])
            min_dists[j][v] = min_dists[v][j]
            min_dists[j][t] = min_dists[t][j]

if f:
    print(ans)
else:
    print(-1)

Submission status: Wrong Answer

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

graph_mins = []
for i in range(n):
    for j in range(i+1, n):
        graph_mins.append([i, j, a[i][j]])

graph_mins = sorted(graph_mins, key=lambda x:x[2])

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

f = True
ans = 0
for i in range(len(graph_mins)):
    v, t, d = graph_mins[i][0], graph_mins[i][1], graph_mins[i][2]
    # print(graph_mins[i], min_dists)
    if min_dists[v][t] == d:
        continue
    elif min_dists[v][t] < d:
        f = False
    elif min_dists[v][t] > d:
        ans += d

        # update min_dists
        for i in range(n):
            min_dists[v][i] = min(d + min_dists[t][i], min_dists[v][i])
            min_dists[t][i] = min(d + min_dists[v][i], min_dists[t][i])
            min_dists[i][v] = min_dists[v][i]
            min_dists[i][t] = min_dists[t][i]

if f:
    print(ans)
else:
    print(-1)

Submission status: Wrong Answer

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

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

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

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

main()

Submission status: Wrong Answer

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

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

def main():
    inf = 10 ** 12
    n = int(input())
    aa = LLI(n)
    hp = []
    for v in range(n):
        for u in range(v):
            heappush(hp, [aa[u][v], u, v])
    ans = 0
    first = [True] * n
    bb = [[inf] * n for _ in range(n)]
    for i in range(n):
        bb[i][i] = 0
    while hp:
        d, u, v = heappop(hp)
        if first[u] or first[v]:
            bb[u][v] = bb[v][u] = d
            ans += d
            first[u], first[v] = False, False
        else:
            min_d = inf
            for w in range(n):
                duv = bb[u][w] + bb[w][v]
                if duv < min_d: min_d = duv
            if d < min_d:
                bb[u][v] = bb[v][u] = d
                ans += d
            elif d > min_d:
                print(-1)
                exit()
    #p2D(bb)
    print(ans)

main()

Submission status: Wrong Answer

Solution code:
import sys
inf = float('inf')
N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
edges = []
for i in range(N):
    for j in range(i+1, N):
        edges.append((A[i][j], i, j))
edges.sort()
d = [[inf]*N for _ in range(N)]
for i in range(N):
    d[i][i] = 0
ans= 0
for a, i, j in edges:
    if d[i][j] > a:
        ans+=a
        d[i][j] = a
        d[j][i] = a
        for k in range(N):
            d[i][k] = min(d[i][k], d[i][j]+d[j][k])
            d[j][k] = min(d[j][k], d[i][j]+d[i][k])
            d[k][i] = min(d[k][i], d[i][j]+d[k][j])
            d[k][j] = min(d[k][j], d[i][j]+d[k][i])
    elif d[i][j] < a:
        print(-1)
        sys.exit()
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
inf = float('inf')
N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
edges = []
for i in range(N):
    for j in range(i+1, N):
        edges.append((A[i][j], i, j))
edges.sort()
d = [[inf]*N for _ in range(N)]
ans= 0
for a, i, j in edges:
    if d[i][j] > a:
        ans+=a
        d[i][j] = a
        d[j][i] = a
        for k in range(N):
            d[i][k] = min(d[i][k], d[i][j]+d[j][k])
            d[j][k] = min(d[j][k], d[i][j]+d[i][k])
            d[k][i] = min(d[k][i], d[i][j]+d[k][j])
            d[k][j] = min(d[k][j], d[i][j]+d[k][i])
    elif d[i][j] < a:
        print(-1)
        sys.exit()
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
inf = 10**10
N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
edges = []
for i in range(N):
    for j in range(i+1, N):
        edges.append((A[i][j], i, j))
edges.sort()
d = [[inf]*N for _ in range(N)]
ans= 0
for a, i, j in edges:
    if d[i][j] > a:
        ans+=a
        d[i][j] = a
        d[j][i] = a
        for k in range(N):
            d[i][k] = min(d[i][k], d[i][j]+d[j][k])
            d[j][k] = min(d[j][k], d[i][j]+d[i][k])
            d[k][i] = min(d[k][i], d[i][j]+d[k][j])
            d[k][j] = min(d[k][j], d[i][j]+d[k][i])
    elif d[i][j] < a:
        print(-1)
        sys.exit()
print(ans)

Submission status: Wrong Answer

Solution code:
def warshall_floyd(n,d):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d
##############################################
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')

N = I()
cur = 0
ans = int(0)
A = [LI() for _ in range(N)]
d = [[float("inf") for i in range(N)] for i in range(N)]
v = [[] for _ in range(N)]
k=int(0)
NewA = [None]*(N*(N-1)//2)
for i in range(N):
    for j in range(i+1,N):
        v[i].append((j,A[i][j]))
        v[j].append((i,A[i][j]))
        d[i][j] = A[i][j]
        d[j][i] = A[j][i]
        NewA[k] = [A[i][j],i,j]
        k +=1
for i in range(N):
    d[i][i] = 0 #自身のところに行くコストは０
#print(warshall_floyd(N,d))
W = warshall_floyd(N,d)

for i,minL in enumerate(W):
    if minL!=A[i]:
        ans = -1

#print(ans)
NewA.sort()
#print(NewA)
if ans==0:
    lowerN = 1
    upperN = N
    Ncandi = (lowerN+upperN)//2
    while(True):
        cur = 1
        dcandi = [[float("inf") for i in range(N)] for i in range(N)]
        for i in range(Ncandi):
            dcandi[NewA[i][1]].append((NewA[i][2],NewA[i][0]))
            dcandi[NewA[i][2]].append((NewA[i][1],NewA[i][0]))
        for i in range(N):
            d[i][i] = 0  # 自身のところに行くコストは０
        W = warshall_floyd(N, dcandi)
        for i in W:
            if inf in i:
                lowerN = Ncandi
                Ncandi = (Ncandi+upperN)//2
                cur = -1
        if cur==1:
            upperN = Ncandi
            Ncandi = (Ncandi + lowerN) // 2

        if upperN-lowerN<=1:
            if cur==1:
                cur = lowerN
            else:
                cur = upperN
#            print(cur)
#            print(lowerN,upperN)
            for i in range(min(cur+1,N*(N-1)//2)):
                ans += NewA[i][0]
            break

print(ans)

Submission status: Wrong Answer

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

if A == B:
    print(ans//2)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import numpy as np
from scipy.sparse.csgraph import floyd_warshall,csgraph_from_dense
from scipy.sparse import csr_matrix
import sys
input = sys.stdin.readline
def inputs():return [int(x) for x in input().split()]
N= int(input())
A=np.array([inputs() for _ in range(N)])
#A[A==0]=[10**13]
#print(A)
G = csgraph_from_dense(A, null_value=0)
dist_mat = floyd_warshall(G,directed=False)

if not np.allclose(A,dist_mat):
  print(-1)
else:
  ans=0
  for i in range(N):
    for j in range(N):
      for k in range(N):
        if dist_mat[j][k]==dist_mat[j][i]+dist_mat[i][k] and dist_mat[j][i]>0 and dist_mat[i][k]>0:
          dist_mat[j][k]=0
#print(dist_mat)
print(int(np.sum(dist_mat)//2))
"""
graph2 = [[10**13]*(N+1) for _ in range(N+1)]
np.fill_diagonal(graph2,0)
graph2[distmat<=L]=1
dist_mat2 = floyd_warshall(graph2,directed=False)
dist_mat2[dist_mat2==10**13]=0
Q = int(input())
for i in range(Q):
    s,t = inputs()
    print(int(dist_mat[s,t])-1)
"""

Submission status: Wrong Answer

Solution code:
import sys
from copy import deepcopy as dc
input = sys.stdin.buffer.readline
N = int(input())
d = [list(map(int, input().split())) for _ in range(N)]
d2 = dc(d)
for k in range(N):
  for i in range(N):
    for j in range(N):
      d2[i][j] = min(d2[i][k] + d2[k][j], d2[i][j])
f = 0
for i in range(N):
  for j in range(N):
    if d[i][j] != d2[i][j]:
      f = 1
if f:
  print(-1)
else:
  res = 0
  e = [[float("inf")] * (N) for _ in range(N)]
  ff = [[0] * N for _ in range(N)]
  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] and d[i][k] > 0 and d[k][j] > 0 and i != j and j != k and k != i:
          if e[i][k] > d[i][k]:
            ff[i][k] = 1
            e[i][k] = d[i][k]
          if e[k][j] > d[k][j]:
            ff[k][j] = 1
            e[k][j] = d[k][j]
  for k in range(N):
    for i in range(N):
      for j in range(N):
        e[i][j] = min(e[i][k] + e[k][j], e[i][j])
  for i in range(N):
    for j in range(N):
      if d[i][j] < e[i][j]:
        res += d[i][j]
      elif ff[i][j]:
        res += e[i][j]
  #print(e)
  print(res // 2)

Submission status: Wrong Answer

Solution code:
import sys
from copy import deepcopy as dc
input = sys.stdin.buffer.readline
N = int(input())
d = [list(map(int, input().split())) for _ in range(N)]
d2 = dc(d)
for k in range(N):
  for i in range(N):
    for j in range(N):
      d2[i][j] = min(d2[i][k] + d2[k][j], d2[i][j])
f = 0
for i in range(N):
  for j in range(N):
    if d[i][j] != d2[i][j]:
      f = 1
if f:
  print(-1)
else:
  res = 0
  e = [[float("inf")] * (N) for _ in range(N)]
  for i in range(N):
    for j in range(N):
      ff = 0
      for k in range(N):
        if d[i][j] == d[i][k] + d[k][j] and d[i][k] > 0 and d[k][j] > 0 and i != j and j != k and k != i:
          e[i][k] = min(e[i][k], d[i][k])
          e[k][j] = min(e[k][j], d[k][j])
          ff = 1
        if k == N - 1 and ff == 0:
          e[i][j] = d[i][j]
  for i in range(N):
    for j in range(N):
      if e[i][j] != float("inf"):
        res += e[i][j]
  #print(e)
  print(res // 2)

Submission status: Wrong Answer

Solution code:
import sys
from copy import deepcopy as dc
input = sys.stdin.buffer.readline
N = int(input())
d = [list(map(int, input().split())) for _ in range(N)]
d2 = dc(d)
for k in range(N):
  for i in range(N):
    for j in range(N):
      d2[i][j] = min(d2[i][k] + d2[k][j], d2[i][j])
f = 0
for i in range(N):
  for j in range(N):
    if d[i][j] != d2[i][j]:
      f = 1
if f:
  print(-1)
else:
  res = 0
  e = [[float("inf")] * (N) for _ in range(N)]
  fff = [[0] * N for _ in range(N)]
  for i in range(N):
    for j in range(N):
      ff = 0
      for k in range(N):
        if d[i][j] == d[i][k] + d[k][j] and d[i][k] > 0 and d[k][j] > 0:
          e[i][k] = min(e[i][k], d[i][k])
          e[k][j] = min(e[k][j], d[k][j])
          ff = 1
          fff[i][k] = 1
          fff[k][i] = 1
        if k == N - 1 and ff == 0:
          e[i][j] = d[i][j]
          fff[i][j] = 1
  for k in range(N):
    for i in range(N):
      for j in range(N):
        e[i][j] = min(e[i][k] + e[k][j], e[i][j])
  for i in range(N):
    for j in range(N):
      if e[i][j] > d[i][j]:
        res += d[i][j]
      elif fff[i][j] == 1:
        res += e[i][j]
  #print(e)
  print(res // 2)

Submission status: Wrong Answer

Solution code:
import sys
from copy import deepcopy as dc
input = sys.stdin.buffer.readline
N = int(input())
d = [list(map(int, input().split())) for _ in range(N)]
d2 = dc(d)
for k in range(N):
  for i in range(N):
    for j in range(N):
      d2[i][j] = min(d2[i][k] + d2[k][j], d2[i][j])
f = 0
for i in range(N):
  for j in range(N):
    if d[i][j] != d2[i][j]:
      f = 1
if f:
  print(-1)
else:
  res = 0
  e = [[float("inf")] * (N) for _ in range(N)]
  for i in range(N):
    for j in range(N):
      ff = 0
      for k in range(N):
        if d[i][j] == d[i][k] + d[k][j] and d[i][k] > 0 and d[k][j] > 0:
          e[i][k] = min(e[i][k], d[i][k])
          e[k][j] = min(e[k][j], d[k][j])
          ff = 1
        if k == N - 1 and ff == 0:
          e[i][j] = d[i][j]
  for i in range(N):
    for j in range(N):
      if e[i][j] != float("inf"):
        res += e[i][j]
  #print(e)
  print(res // 2)

Submission status: Wrong Answer

Solution code:
import sys
from copy import deepcopy as dc
input = sys.stdin.buffer.readline
N = int(input())
d = [list(map(int, input().split())) for _ in range(N)]
res = 0
e = [[float("inf")] * (N) for _ in range(N)]
for i in range(N):
  for j in range(N):
    ff = 0
    for k in range(N):
      if d[i][j] == d[i][k] + d[k][j] and d[i][k] > 0 and d[k][j] > 0:
        if i == 0 and k == 2: print("a")
        e[i][k] = min(e[i][k], d[i][k])
        e[k][j] = min(e[k][j], d[k][j])
        ff = 1
      if k == N - 1 and ff == 0:
        e[i][j] = d[i][j]
for i in range(N):
  for j in range(N):
    if e[i][j] != float("inf"):
      res += e[i][j]
for k in range(N):
  for i in range(N):
    for j in range(N):
      e[i][j] = min(e[i][j], e[i][k] + e[k][j])
if e != d:
  res = -1
#print(e)
print(res // 2)

Submission status: Wrong Answer

Solution code:
import sys
from copy import deepcopy as dc
input = sys.stdin.buffer.readline
N = int(input())
d = [list(map(int, input().split())) for _ in range(N)]
d2 = dc(d)
for k in range(N):
  for i in range(N):
    for j in range(N):
      d2[i][j] = min(d2[i][k] + d2[k][j], d2[i][j])
f = 0
for i in range(N):
  for j in range(N):
    if d[i][j] != d2[i][j]:
      f = 1
if f:
  print(-1)
else:
  res = 0
  e = [[float("inf")] * (N) for _ in range(N)]
  for i in range(N):
    for j in range(N):
      ff = 0
      for k in range(N):
        if d[i][j] == d[i][k] + d[k][j] and d[i][k] > 0 and d[k][j] > 0:
          if i == 0 and k == 2: print("a")
          e[i][k] = min(e[i][k], d[i][k])
          e[k][j] = min(e[k][j], d[k][j])
          ff = 1
        if k == N - 1 and ff == 0:
          e[i][j] = d[i][j]
  for i in range(N):
    for j in range(N):
      if e[i][j] != float("inf"):
        res += e[i][j]
  #print(e)
  print(res // 2)

Submission status: Wrong Answer

Solution code:
import sys
from copy import deepcopy as dc
input = sys.stdin.buffer.readline
N = int(input())
d = [list(map(int, input().split())) for _ in range(N)]
d2 = dc(d)
for k in range(N):
  for i in range(N):
    for j in range(N):
      d2[i][j] = min(d2[i][k] + d2[k][j], d2[i][j])
f = 0
for i in range(N):
  for j in range(N):
    if d[i][j] != d2[i][j]:
      f = 1
if f:
  print(-1)
else:
  res = 0
  e = [[float("inf")] * N for _ in range(N)]
  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] and d[i][k] > 0 and d[k][j] > 0:
          if i == 0 and k == 2: print("a")
          e[i][k] = min(e[i][k], d[i][k])
          e[k][j] = min(e[k][j], d[k][j])
  d2 = dc(e)
  for k in range(N):
    for i in range(N):
      for j in range(N):
        d2[i][j] = min(e[i][k] + e[k][j], d2[i][j])
  for i in range(N):
    for j in range(N):
      if d2[i][j] > d[i][j] and e[i][j] == float("inf"):
        res += d[i][j]
      if e[i][j] != float("inf"):
        res += e[i][j]
  #print(e)
  print(res // 2)

Submission status: Wrong Answer

Solution code:
def Warshall_Floyd(edges,N):
  for k in range(N):
    for i in range(N):
      for j in range(N):
        edges[i][j]=min(edges[i][j],edges[i][k]+edges[k][j])
  return edges

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

Submission status: Wrong Answer

Solution code:
from scipy.sparse.csgraph import dijkstra

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

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

Submission status: Wrong Answer

Solution code:
def Warshall_Floyd(edges,N):
  for k in range(N):
    for i in range(N):
      for j in range(N):
        edges[i][j]=min(edges[i][j],edges[i][k]+edges[k][j])
  return edges

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

Submission status: Wrong Answer

Solution code:
from scipy.sparse.csgraph import dijkstra

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

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

Submission status: Wrong Answer

Solution code:
n = int(input())
dp = [list(map(int,input().split())) for _ in range(n)]
ans = []
for i in range(n):
    for j in range(n):
        if dp[i][j] == 0:continue
        a = 0
        for k in range(n):
            if dp[i][k] == 0:continue
            if j == k:continue
            if dp[i][k]+dp[k][j] < dp[i][j]:print(-1);exit()
            if dp[i][k] + dp[k][j] == dp[i][j]:
                ans.append([i,k])
                a = 1
        if a == 0:
            ans.append([i,j])
s = set()
for i in ans:
    if i[0] > i[1]:s.add(tuple([i[1],i[0]]))
    else:s.add(tuple([i[0],i[1]]))
print(sum([dp[i[0]][i[1]] for i in s]))

Submission status: Wrong Answer

Solution code:
import heapq as hp
import sys
input = sys.stdin.readline


def main():
    N = int(input())
    q = []
    for n in range(N):
        A = list(map(int, input().split()))
        for i, a in enumerate(A):
            if i > n:
                hp.heappush(q, (a, i, n))

    INF = int(1E17)
    D = [[INF for _ in range(N)] for _ in range(N)]
    using = []
    ok = True
    while q:
        d, a, b = hp.heappop(q)
        if D[a][b] < d:
            ok = False
            break
        elif D[a][b] > d:
            D[a][b] = d
            D[b][a] = d
            using.append((a, b))
            for n in range(N):
                if n == a or n == b:
                    continue
                if D[a][n] > D[b][n] + d:
                    D[a][n] = D[b][n] + d
                    D[n][a] = D[n][b] + d
                elif D[b][n] > D[a][n] + d:
                    D[b][n] = D[a][n] + d
                    D[n][b] = D[n][a] + d
    ans = 0
    for a, b in using:
        ans += D[a][b]
    if ok:
        print(ans)
    else:
        print(-1)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import heapq as hp
import sys
input = sys.stdin.readline


def main():
    N = int(input())
    q = []
    G = []
    for n in range(N):
        A = list(map(int, input().split()))
        G.append(A)
        for i, a in enumerate(A):
            if i > n:
                hp.heappush(q, (a, i, n))

    INF = int(1E17)
    D = [[INF for _ in range(N)] for _ in range(N)]
    ans = 0
    ok = True
    while q:
        d, a, b = hp.heappop(q)
        if D[a][b] < d and D[a][b] < G[a][b]:
            ok = False
            break
        elif D[a][b] > d:
            D[a][b] = d
            D[b][a] = d
            ans += d
            for n in range(N):
                if n == a or n == b:
                    continue
                if D[a][n] > D[b][n] + d:
                    D[a][n] = D[b][n] + d
                    D[n][a] = D[n][b] + d
                    hp.heappush(q, (D[a][n], a, n))
                elif D[b][n] > D[a][n] + d:
                    D[b][n] = D[a][n] + d
                    D[n][b] = D[n][a] + d
                    hp.heappush(q, (D[b][n], b, n))
    if ok:
        print(ans)
    else:
        print(-1)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import heapq as hp
import sys
input = sys.stdin.readline


def main():
    N = int(input())
    q = []
    G = []
    for n in range(N):
        A = list(map(int, input().split()))
        G.append(A)
        for i, a in enumerate(A):
            if i > n:
                hp.heappush(q, (a, i, n))

    INF = int(1E17)
    D = [[INF for _ in range(N)] for _ in range(N)]
    ans = 0
    ok = True
    while q:
        d, a, b = hp.heappop(q)
        if D[a][b] < d and D[a][b] != G[a][b]:
            ok = False
            break
        elif D[a][b] > d:
            D[a][b] = d
            D[b][a] = d
            ans += d
            for n in range(N):
                if n == a or n == b:
                    continue
                if D[a][n] > D[b][n] + d:
                    D[a][n] = D[b][n] + d
                    D[n][a] = D[n][b] + d
                    hp.heappush(q, (D[a][n], a, n))
                elif D[b][n] > D[a][n] + d:
                    D[b][n] = D[a][n] + d
                    D[n][b] = D[n][a] + d
                    hp.heappush(q, (D[b][n], b, n))
    if ok:
        print(ans)
    else:
        print(-1)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import heapq as hp
import sys
input = sys.stdin.readline


def main():
    N = int(input())
    graph = [[] for _ in range(N)]
    q = []
    for n in range(N):
        A = list(map(int, input().split()))
        for i, a in enumerate(A):
            if i > n:
                hp.heappush(q, (a, i, n))

    INF = 1E17
    D = [[INF for _ in range(N)] for _ in range(N)]
    ans = 0
    ok = True
    while q:
        d, a, b = hp.heappop(q)
        if D[a][b] < d:
            ok = False
            break
        elif D[a][b] > d:
            D[a][b] = d
            D[b][a] = d
            ans += d
            for n in range(N):
                if D[a][n] > D[b][n] + d:
                    D[a][n] = D[b][n] + d
                    D[n][a] = D[n][b] + d
                elif D[b][n] > D[a][n] + d:
                    D[b][n] = D[a][n] + d
                    D[n][b] = D[n][a] + d
    if ok:
        print(ans)
    else:
        print(-1)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

for i in range(n):
    for j in range(i+1,n):
        for k in range(n):
            if i==k or j==k:
                continue
            if d[i][j]>d[i][k]+d[k][j]:
                print(-1)
                exit()
            elif d[i][j]==d[i][k]+d[k][j]:
                ans-=d[i][j]
                
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[]
b=[]
ans=0
for i in range(n):
    tmp=[int(j) for j in input().split()]
    a.append(tmp)
    ans+=sum(tmp)
import copy
b=copy.deepcopy(a)
def warshall_floyd(d):
    global 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]:
                    ans-=d[i][j]
                    d[i][j] = d[i][k] + d[k][j]
                    
                    
    return d

a=warshall_floyd(a)

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

print(ans//2)