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 sys

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

    INF = float('INF')
    for i in range(N):
        A[i][i] = INF

    ans = 0
    for i in range(N):
        for j in range(i+1, N):
            bipas = min(map(sum, zip(A[i], A[j])))

            if A[i][j] > bipas:
                ans = -1
                break
            elif A[i][j] < bipas:
                ans += A[i][j]

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

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

    INF = float('INF')
    for i in range(N):
        A[i][i] = INF

    ans = 0
    for i in range(N):
        for j in range(i):
            bipas = min(map(sum, zip(A[i], A[j])))

            if A[i][j] > bipas:
                ans = -1
                break
            elif A[i][j] < bipas:
                ans += A[i][j]

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

def calc():
    ans=sum(map(sum,A))
    
    for i in range(N):
        for j in range(N):
            for k in range(N):
                if A[i][j]>A[i][k]+A[k][j]:
                    return -1
                if i==k or k==j:continue
                if A[i][j]==A[i][k]+A[k][j]:
                    ans-=A[i][j]

    return ans//2
                
print(calc())

Submission status: Wrong Answer

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

def calc():
    ans=sum(map(sum,A))
    
    for i in range(N):
        for j in range(N):
            for k in range(N):
                if i==k or k==j:continue
                if A[i][j]>A[i][k]+A[k][j]:
                    return -1
                if A[i][j]==A[i][k]+A[k][j]:
                    ans-=A[i][j]

    return ans//2
                
print(calc())

Submission status: Wrong Answer

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

def calc():
    ans=sum(map(sum,A))
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if i==j or i==k 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]:
                    return -1

    return ans//2
                
print(calc())

Submission status: Wrong Answer

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

def calc():
    ans=sum(map(sum,A))//2
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if i>=j or i==k 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]:
                    return -1
      
    return ans
                
print(calc())

Submission status: Wrong Answer

Solution code:
INF = 10 ** 20
n = int(input())
edges = []
for i in range(n):
    aList = list(map(int, input().split()))
    for j in range(i, n):
        edges.append((aList[j], i, j))

edges.sort()

dist = [[INF] * n for _ in range(n)]
ans = 0
for c, i, j in edges:
    minDist = INF
    for k in range(n):
        minDist = min(minDist, dist[i][k] + dist[k][j])
    if minDist < c:
        print(-1)
        break
    elif minDist == c:
        continue
    else:
        dist[i][j] = dist[j][i] = c
        ans += c
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

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

# 最短経路(仮)の全長
sm = 0
for i in range(N):
    for j in range(i+1, N):
        sm += A[i][j]

# ワーシャルフロイドで全頂点の最短距離
for k in range(N):
    for i in range(N):
        for j in range(N):
            # 最短 > 経由 があればNG
            if A[i][j] > A[i][k] + A[k][j]:
                print(-1)
                exit()
            # 最短 = 経由 があるなら、経由を使えば全長を減らせる
            elif A[i][j] == A[i][k] + A[k][j] and j != k and i != k and i < j:
                # 最短経路(仮)から直行ルートをなくす
                sm -= A[i][j]
print(sm)

Submission status: Wrong Answer

Solution code:
import copy
N = int(input())
A = [list(map(int,input().split())) for i in range(N)]
cost = copy.deepcopy(A)
edge = copy.deepcopy(A)
for i in range(N):
    for j in range(i):
        for k in range(N):
            if cost[i][j] > cost[i][k]+cost[k][j]:
                cost[i][j] = cost[i][k]+cost[k][j]
                cost[j][i] = cost[i][j]
ans = True
for i in range(N):
    for j in range(i):
        if A[i][j] != cost[i][j]:
            ans = False
            break
if not ans:
    print(-1)
else:
    ans = 0
    for i in range(N):
        for j in range(i):
            ans += edge[i][j]
    print(ans)

Submission status: Wrong Answer

Solution code:
import copy
N = int(input())
A = [list(map(int,input().split())) for i in range(N)]
cost = copy.deepcopy(A)
for k in range(N):
    for i in range(N):
        for j in range(N):
            if i != k and j != k:
                if cost[i][j] == cost[i][k]+cost[k][j]:
                    A[i][j] = 0
                if cost[i][j] > cost[i][k]+cost[k][j]:
                    cost[i][j] = cost[i][k]+cost[k][j]

if A != cost:
    print(-1)
else:
    print(sum(list(map(sum,zip(*A))))//2)

Submission status: Wrong Answer

Solution code:
import itertools
N = int(input())
A = [[int(i) for i in input().split()] for j in range(N)]
Node = [int(i) for i in range(N)]
Comb = list(itertools.combinations(Node, 2))

Possible = True
NoNeed = 0
count = 0
while Possible and count < N*(N-1):
    for c in Comb:
        count += 1
        for i in range(N):
            if i!=c[0] and i!=c[1]:
                if A[c[0]][c[1]] < A[c[0]][i] + A[c[1]][i]:
                    continue
                elif A[c[0]][c[1]] == A[c[0]][i] + A[c[1]][i]:
                    NoNeed += A[c[0]][c[1]]
                    break
                else:
                    Possible = False

if Possible:
    Total = 0
    for i in range(N):
        Total += sum(A[i])
    Total //= 2
    Total -= NoNeed
    print(Total)

else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import numpy
import itertools
N = int(input())
A = [[int(i) for i in input().split()] for j in range(N)]
print(A)
Node = [int(i) for i in range(N)]
Comb = list(itertools.combinations(Node, 2))

Possible = True
NoNeed = set()
count = 0
while Possible and count < len(Comb):
    for c in Comb:
        count += 1
        for i in range(N):
            if i!=c[0] and i!=c[1]:
                if A[c[0]][c[1]] < A[c[0]][i] + A[c[1]][i]:
                    continue
                elif A[c[0]][c[1]] == A[c[0]][i] + A[c[1]][i]:
                    NoNeed |= {(min(c[0], c[1]), max(c[0], c[1]))}
                else:
                    Possible = False

if Possible:
    Total = numpy.sum(A) // 2
    for a in NoNeed:
        Total -= A[a[0]][a[1]]
    print(Total)

else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import heapq

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

INF = float('inf')

def dijkstra(s, g, key):
    dist = [INF for i in range(n)]
    dist[s] = 0
    hq2 = [(0, s)]
    while hq2:
        cost, node = heapq.heappop(hq2)
        if cost > dist[node]:
            continue
        for v_next, d_next in enumerate(graph[node]):
            if d_next == INF:
                continue
            d = d_next + cost
            if d < dist[v_next]:
                dist[v_next] = d
                heapq.heappush(hq2, (dist[v_next], v_next))
    if dist[g] == INF:
        graph[s][g] = key
        graph[g][s] = key
        return key
    elif dist[g] == key:
        return 0
    else:
        return -1

ans = 0
hq = []
for i in range(n):
    for j in range(i+1, n):
        heapq.heappush(hq, (a[i][j], i, j))

graph = [[INF for i in range(n)] for j in range(n)]

while hq:
    dist, vs, vg = heapq.heappop(hq)
    flag = dijkstra(vs, vg, dist)
    if flag == -1:
        break
    else:
        ans += flag
if flag == -1:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
dist={}

for i in range(N):
    for j,x in enumerate(map(int,input().split())):
        dist[N*i+j]=x
ans=0
path = 0
for i in range(N):
    for j in range(i+1,N):
        min_=float('inf')
        for k in range(N):
            if k ==i or k ==j:
                continue
            min_=min(dist[N*i+k]+dist[N*k+j],min_)

        if min_<dist[N*i+j]:
            ans=-1
            break
        elif min_>dist[N*i+j]:
            path+=dist[N*i+j]
print(ans)

Submission status: Wrong Answer

Solution code:
from scipy.sparse.csgraph import floyd_warshall
n = int(input())
a = [[int(i) for i in input().split()] for i in range(n)]
d,ans = floyd_warshall(a,directed=False),0
if any(a[i][j]!=d[i][j] for i in range(n) for j in range(n)): print(-1)
else:
	for i in range(n):
		for j in range(i+1,n):
			for k in range(n):
				if k!=i and k!=j and d[i][k]+d[j][k]==d[i][j]:
					ans += d[i][j]
					break 
	print(int(ans))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
b = a[:]
def Warshall_Floyd(edges,N):
  ans = 0
  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])
        if (edges[i][k] + edges[k][j] == edges[i][j] and edges[i][k] != 0 and edges[k][j] != 0):
          ans += edges[i][k] + edges[k][j]
  return edges,ans
x,ans = Warshall_Floyd(a,n)
if x != b:
  print(-1)
else:
  x = sum(map(sum, x))
  print((x-ans)//2)

Submission status: Wrong Answer

Solution code:
import copy
N = int(input())
Map = [list(map(int, input().split())) for i in range(N)]

INF = float('inf')
shortest = copy.deepcopy(Map)

for k in range(N):
    for i in range(N):
        for j in range(N):
            if shortest[i][k] + shortest[k][j] < shortest[i][j]:
                shortest[i][j] = shortest[i][k] + shortest[k][j]

if Map != shortest:
    print(-1)
    exit()

ans = 0
for k in range(N):
    for i in range(N):
        for j in range(N):
            if shortest[i][k] + shortest[k][j] == shortest[i][j] and i != k and j != k:
                ans -= shortest[i][j]

for s in shortest:
    ans += sum(s)

print(ans // 2)

Submission status: Wrong Answer

Solution code:
import copy
N = int(input())
Map = [list(map(int, input().split())) for i in range(N)]

INF = float('inf')
shortest = copy.deepcopy(Map)

for k in range(N):
    for i in range(N):
        for j in range(N):
            if shortest[i][k] + shortest[k][j] < shortest[i][j]:
                shortest[i][j] = shortest[i][k] + shortest[k][j]

if Map != shortest:
    print(-1)
    exit()

ans = 0
for k in range(N):
    for i in range(N):
        for j in range(N):
            if shortest[i][k] + shortest[k][j] == shortest[i][j] and shortest[i][k] > 0 and shortest[k][j] > 0:
                ans -= shortest[i][j]

for s in shortest:
    ans += sum(s)

print(ans // 2)

Submission status: Wrong Answer

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

INF = float('inf')
shortest = [[INF]*N for i in range(N)]

ans = 0
for k in range(N):
    for i in range(N):
        for j in range(N):
            if Map[i][k] + Map[k][j] < Map[i][j]:
                print(-1)
                exit()

            elif Map[i][k] + Map[k][j] == Map[i][j] and i != k and k != j:
                ans -= Map[i][j]

for m in Map:
    ans += sum(m)

print(ans // 2)

Submission status: Wrong Answer

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

INF = float('inf')
shortest = [[INF]*N for i in range(N)]

ans = 0
for k in range(N):
    for i in range(N):
        for j in range(N):
            if Map[i][k] + Map[k][j] < Map[i][j]:
                print(-1)
                exit()
            elif Map[i][k] + Map[k][j] == Map[i][j] and Map[i][k] > 0 and Map[k][j] > 0:
                ans -= Map[i][j]

for m in Map:
    ans += sum(m)

print(ans // 2)

Submission status: Wrong Answer

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

INF = float('inf')
shortest = [[INF]*N for i in range(N)]

ans = 0
for k in range(N):
    for i in range(N):
        for j in range(N):
            if Map[i][k] == 0 or Map[k][j] == 0:
                continue

            if Map[i][k] + Map[k][j] < Map[i][j]:
                print(-1)
                exit()

            elif Map[i][k] + Map[k][j] == Map[i][j]:
                ans -= Map[i][j]

for m in Map:
    ans += sum(m)

print(ans // 2)

Submission status: Wrong Answer

Solution code:
#import numpy as np
import copy

N = int(input())
a = [[int(i) for i in input().split()] for i in range(N)]
b = [[False for i in range(N)] for i in range(N)]
ans = 0
boo = True
while(True):
  c = copy.deepcopy(b)
  for i in range(N):
    for j in range(i, N):
      for k in range(N):
        if(i == k):
          continue
        else:
          if(a[i][j] > a[i][k] + a[k][j]):
            boo = False
          elif(a[i][j] == a[i][k] + a[k][j]):
            b[i][j] = False or b[i][j]
            b[i][k] = False or b[i][k]
            b[k][j] = False or b[k][j]
          else:
            b[i][j] = True
  if(c == b):
    break
if(not boo):
  print("-1")
else:
  for i in range(N):
    for j in range(i, N):
      if(b[i][j]):
        ans += a[i][j]
  print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys

def read_data():
    try:
        LOCAL_FLAG
        import codecs
        import os

        lines = []
        file_path = os.path.join(os.path.dirname(__file__), 'data.dat')
        with codecs.open(file_path, 'r', 'utf-8') as f:
            n_lines = int(f.readline())
            for i in range(n_lines):
                lines.append(f.readline().rstrip("\r\n"))

    except NameError:
        lines = []
        n_lines = int(input())
        for i in range(n_lines):
            lines.append(input())
    return lines

raw_data = read_data()
tarray = []
for each in raw_data:
    tarray.append(each.split())
A = np.array(tarray, dtype='int32')
N = A.shape[0]


def Restoring_Road_Network2():

    not_available = False
    for k in range(0, N):
        for i in range(0, N):
            if(k==i): continue
            for j in range(0, N):
                if((i==j) or (j==k)): continue
                if(A[i][k] + A[k][j] < A[i][j]):
                    not_availabel = True
                if(A[i][k] + A[k][j] == A[i][j]):
                    B[i][j] = 1
                    B[j][i] = 1

    try:
        LOCAL_FLAG
        print(B)
    except NameError:
        pass

    if(not_available):
        print(-1)
    else:
        total_dis = 0
        for i in range(0, N):
            for j in range(i, N):
                if(B[i][j] == 0):
                    total_dis += A[i][j]
        print(total_dis)

def Restoring_Road_Network3():

    import scipy.sparse.csgraph as graph

    MAX = [10000000000]*N  # should be > 2*10**9
    d = np.diag(MAX)
    C = A.copy()
    C += d
    total_dis = 0
    n_path = 0
    for i in range(N-1):
        for j in range(i+1, N):
            dis_two_node = np.min(C[i] + C[j])
            if dis_two_node > C[i,j]:
                total_dis += C[i,j]
                # print(i, j)
            elif dis_two_node < C[i,j]:
                print(-1)
                exit()

    print(total_dis)

def AA():
    import numpy as np

    for i in range(N):
        A[i][i] = 10000000000

    result = 0
    for i in range(N-1):
        for j, d1 in enumerate(A[i][i+1:], start=i+1):
            d2 = np.min(A[i]+A[j])
            # print(A[i][i+1:])
            # print (i, j, d1, d2)
            if d1 >= d2:
                if d1 > d2:
                    print(-1)
                    exit()
            else:
                result += d1
    print(result)

AA()

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys

def read_data():
    try:
        LOCAL_FLAG
        import codecs
        import os

        lines = []
        file_path = os.path.join(os.path.dirname(__file__), 'data.dat')
        with codecs.open(file_path, 'r', 'utf-8') as f:
            n_lines = int(f.readline())
            for i in range(n_lines):
                lines.append(f.readline().rstrip("\r\n"))

    except NameError:
        lines = []
        n_lines = int(input())
        for i in range(n_lines):
            lines.append(input())
    return lines

raw_data = read_data()
tarray = []
for each in raw_data:
    tarray.append(each.split())
A = np.array(tarray, dtype='int32')
N = A.shape[0]


def Restoring_Road_Network2():

    not_available = False
    for k in range(0, N):
        for i in range(0, N):
            if(k==i): continue
            for j in range(0, N):
                if((i==j) or (j==k)): continue
                if(A[i][k] + A[k][j] < A[i][j]):
                    not_availabel = True
                if(A[i][k] + A[k][j] == A[i][j]):
                    B[i][j] = 1
                    B[j][i] = 1

    try:
        LOCAL_FLAG
        print(B)
    except NameError:
        pass

    if(not_available):
        print(-1)
    else:
        total_dis = 0
        for i in range(0, N):
            for j in range(i, N):
                if(B[i][j] == 0):
                    total_dis += A[i][j]
        print(total_dis)

def Restoring_Road_Network3():

    import scipy.sparse.csgraph as graph

    MAX = [10000000000]*N  # should be > 2*10**9
    d = np.diag(MAX)
    C = A.copy()
    C += d
    total_dis = 0
    n_path = 0
    for i in range(N-1):
        for j in range(i+1, N):
            dis_two_node = np.min(C[i] + C[j])
            if dis_two_node > C[i,j]:
                total_dis += C[i,j]
                # print(i, j)
            elif dis_two_node < C[i,j]:
                print(-1)
                exit()

    print(total_dis)

Restoring_Road_Network3()

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys

def read_data():
    try:
        LOCAL_FLAG
        import codecs
        import os

        lines = []
        file_path = os.path.join(os.path.dirname(__file__), 'data.dat')
        with codecs.open(file_path, 'r', 'utf-8') as f:
            n_lines = int(f.readline())
            for i in range(n_lines):
                lines.append(f.readline().rstrip("\r\n"))

    except NameError:
        lines = []
        n_lines = int(input())
        for i in range(n_lines):
            lines.append(input())
    return lines

raw_data = read_data()
tarray = []
for each in raw_data:
    tarray.append(each.split())
A = np.array(tarray, dtype='int32')
N = A.shape[0]


def Restoring_Road_Network2():

    not_available = False
    for k in range(0, N):
        for i in range(0, N):
            if(k==i): continue
            for j in range(0, N):
                if((i==j) or (j==k)): continue
                if(A[i][k] + A[k][j] < A[i][j]):
                    not_availabel = True
                if(A[i][k] + A[k][j] == A[i][j]):
                    B[i][j] = 1
                    B[j][i] = 1

    try:
        LOCAL_FLAG
        print(B)
    except NameError:
        pass

    if(not_available):
        print(-1)
    else:
        total_dis = 0
        for i in range(0, N):
            for j in range(i, N):
                if(B[i][j] == 0):
                    total_dis += A[i][j]
        print(total_dis)

def Restoring_Road_Network3():

    import scipy.sparse.csgraph as graph

    MAX = [10000000000]*N  # should be > 2*10**9
    d = np.diag(MAX)
    C = A.copy()
    C += d
    total_dis = 0
    n_path = 0
    for i in range(N):
        for j in range(i+1, N):
            dis_two_node = np.min(C[i] + C[j])
            if dis_two_node > C[i,j]:
                total_dis += C[i,j]
                # print(i, j)
            elif dis_two_node < C[i,j]:
                print(-1)
                exit()

    print(total_dis)

Restoring_Road_Network3()

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys

def read_data():
    try:
        LOCAL_FLAG
        import codecs
        import os

        lines = []
        file_path = os.path.join(os.path.dirname(__file__), 'data.dat')
        with codecs.open(file_path, 'r', 'utf-8') as f:
            n_lines = int(f.readline())
            for i in range(n_lines):
                lines.append(f.readline().rstrip("\r\n"))

    except NameError:
        lines = []
        n_lines = int(input())
        for i in range(n_lines):
            lines.append(input())
    return lines

raw_data = read_data()
tarray = []
for each in raw_data:
    tarray.append(each.split())
A = np.array(tarray, dtype='int32')
N = A.shape[0]


def Restoring_Road_Network2():

    not_available = False
    for k in range(0, N):
        for i in range(0, N):
            if(k==i): continue
            for j in range(0, N):
                if((i==j) or (j==k)): continue
                if(A[i][k] + A[k][j] < A[i][j]):
                    not_availabel = True
                if(A[i][k] + A[k][j] == A[i][j]):
                    B[i][j] = 1
                    B[j][i] = 1

    try:
        LOCAL_FLAG
        print(B)
    except NameError:
        pass

    if(not_available):
        print(-1)
    else:
        total_dis = 0
        for i in range(0, N):
            for j in range(i, N):
                if(B[i][j] == 0):
                    total_dis += A[i][j]
        print(total_dis)

def Restoring_Road_Network3():

    import scipy.sparse.csgraph as graph

    MAX = [10000000000]*N  # should be > 2*10**9
    d = np.diag(MAX)
    C = A.copy()
    C += d
    total_dis = 0
    n_path = 0
    for i in range(N):
        for j in range(i+1, N):
            dis_two_node = np.min(C[i] + C[j])
            if dis_two_node > C[i,j]:
                total_dis += C[i,j]
                n_path += 1
                # print(i, j)
            elif dis_two_node < C[i,j]:
                print(-1)
                exit()

    if(n_path >= N):
        print(-1)
    else:
        print(total_dis)


Restoring_Road_Network3()

Submission status: Wrong Answer

Solution code:
import numpy as np

def read_data():
    try:
        LOCAL_FLAG
        import codecs
        import os

        lines = []
        file_path = os.path.join(os.path.dirname(__file__), 'data.dat')
        with codecs.open(file_path, 'r', 'utf-8') as f:
            n_lines = int(f.readline())
            for i in range(n_lines):
                lines.append(f.readline().rstrip("\r\n"))

    except NameError:
        lines = []
        n_lines = int(input())
        for i in range(n_lines):
            lines.append(input())
    return lines

raw_data = read_data()
tarray = []
for each in raw_data:
    tarray.append(each.split())
A = np.array(tarray, dtype='int32')
N = A.shape[0]


def Restoring_Road_Network3():

    import scipy.sparse.csgraph as graph

    MAX = [10000000000]*N  # should be > 2*10**9
    d = np.diag(MAX)
    C = A.copy()
    C += d
    total_dis = 0
    for i in range(N):
        for j in range(i+1, N):
            dis_two_node = np.min(C[i] + C[j])
            if dis_two_node != C[i,j]:
                total_dis += C[i,j]
                # print(i, j)
            if dis_two_node < C[i,j]:
                print(-1)
                exit()

    print(total_dis)


Restoring_Road_Network3()

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys

def read_data():
    try:
        LOCAL_FLAG
        import codecs
        import os

        lines = []
        file_path = os.path.join(os.path.dirname(__file__), 'data.dat')
        with codecs.open(file_path, 'r', 'utf-8') as f:
            n_lines = int(f.readline())
            for i in range(n_lines):
                lines.append(f.readline().rstrip("\r\n"))

    except NameError:
        lines = []
        n_lines = int(input())
        for i in range(n_lines):
            lines.append(input())
    return lines

raw_data = read_data()
tarray = []
for each in raw_data:
    tarray.append(each.split())
A = np.array(tarray, dtype='int32')
N = A.shape[0]


def Restoring_Road_Network3():

    import scipy.sparse.csgraph as graph

    MAX = [sys.maxsize]*N  # should be > 2*10**9
    d = np.diag(MAX)
    C = A.copy()
    C += d
    total_dis = 0
    for i in range(N):
        for j in range(i+1, N):
            dis_two_node = np.min(C[i] + C[j])
            if dis_two_node != C[i,j]:
                total_dis += C[i,j]
                # print(i, j)
            if dis_two_node < C[i,j]:
                print(-1)
                exit()

    print(total_dis)

Restoring_Road_Network3()

Submission status: Wrong Answer

Solution code:
import numpy as np

def read_data():
    try:
        LOCAL_FLAG
        import codecs
        import os

        lines = []
        file_path = os.path.join(os.path.dirname(__file__), 'data.dat')
        with codecs.open(file_path, 'r', 'utf-8') as f:
            n_lines = int(f.readline())
            for i in range(n_lines):
                lines.append(f.readline().rstrip("\r\n"))

    except NameError:
        lines = []
        n_lines = int(input())
        for i in range(n_lines):
            lines.append(input())
    return lines



MAX = 10000000000

raw_data = read_data()
tarray = []
for each in raw_data:
    tarray.append(each.split())
A = np.array(tarray, dtype='int32')
B = np.zeros(A.shape, dtype='int32')

N = A.shape[0]

def Restoring_Road_Network2():

    not_available = False
    for k in range(0, N):
        for i in range(0, N):
            if(k==i): continue
            for j in range(0, N):
                if((i==j) or (j==k)): continue
                if(A[i][k] + A[k][j] < A[i][j]):
                    not_availabel = True
                if(A[i][k] + A[k][j] == A[i][j]):
                    B[i][j] = 1
                    B[j][i] = 1

    try:
        LOCAL_FLAG
        print(B)
    except:
        pass

    if(not_available):
        print(-1)
    else:
        total_dis = 0
        for i in range(0, N):
            for j in range(i, N):
                if(B[i][j] == 0):
                    total_dis += A[i][j]
        print(total_dis)

# Sugar_water()
Restoring_Road_Network2()

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

import sys
N=int(input())
A=[list(map(int,input().split())) for i in range(N)]
B=Warshall_Floyd(A,N)
if A!=B:
  print(-1)
  sys.exit()

ans=0
for i in range(N):
  for j in range(i):
    need=1
    for k in range(N):
      if k!=i and k!=j:
        if A[i][j]==A[i][k]+A[k][j]: need=0
    ans+=need*A[i][j]
print(ans)

Submission status: Wrong Answer

Solution code:
def Warshall_Floyd(edges,N):
  """頂点N個のグラフ上の隣接行列edgesが与えられたとき, 
  2点間の最短距離距離を隣接行列で返す"""
  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
 
import sys
N=int(input())
A=[list(map(int,input().split())) for i in range(N)]
B=Warshall_Floyd(A,N)
if A!=B:
  print(-1)
  sys.exit()
 
ans=0
for i in range(N):
  for j in range(i):
    need=1
    for k in range(N):
      if k!=i and k!=j:
        if A[i][j]==A[i][k]+A[k][j]: need=0
    if need: ans+=A[i][j]
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from sys import stdin
input = stdin.readline
N=int(input())
edges=[list(map(int,input().split())) for i in range(N)]
ans=0
for k in range(N):
  for i in range(N):
    for j in range(i):
      if edges[i][j]>edges[i][k]+edges[k][j]:
        print(-1)
        sys.exit()
      if k==0:
        need=1
        for l in range(N):
          if l!=i and l!=j and edges[i][j]==edges[i][l]+edges[l][j]:
            need=0
            break
        if need:ans+=edges[i][j]
        
print(ans+1)

Submission status: Wrong Answer

Solution code:
import sys
N=int(input())
edges=[list(map(int,input().split())) for i in range(N)]
for k in range(N):
  for i in range(N):
    for j in range(i):
      if edges[i][j]>edges[i][k]+edges[k][j]:
        print(-1)
        sys.exit()
 
ans=0
for i in range(N):
  for j in range(i):
    need=1
    for k in range(N):
      if k!=i and k!=j and edges[i][j]==edges[i][k]+edges[k][j]:
        need=0
        break
    if need:ans+=edges[i][j]
print(ans-1)

Submission status: Wrong Answer

Solution code:
import sys
from sys import stdin
input = stdin.readline
N=int(input())
edges=[list(map(int,input().split())) for i in range(N)]
for k in range(N):
  for i in range(N):
    for j in range(i):
      if edges[i][j]>edges[i][k]+edges[k][j]:
        print(-1)
        sys.exit()
 
ans=0
for i in range(N):
  for j in range(i):
    need=1
    for k in range(N):
      if k!=i and k!=j and edges[i][j]==edges[i][k]+edges[k][j]:
        need=0
        break
    if need:ans+=edges[i][j]
print(ans-1)