Problem:


Score : 500 points

Problem Statement

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

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

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

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

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

Constraints

1 \leq N \leq 300

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

A_{i, i} = 0

Inputs

Input is given from Standard Input in the following format:

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

Outputs

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

Sample Input 1

3
0 1 3
1 0 2
3 2 0

Sample Output 1

3

The network below satisfies the condition:

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

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

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

Sample Input 2

3
0 1 3
1 0 1
3 1 0

Sample Output 2

-1

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

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

Sample Input 3

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

Sample Output 3

82

Sample Input 4

3
0 1000000000 1000000000
1000000000 0 1000000000
1000000000 1000000000 0

Sample Output 4

3000000000



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


Sample output:
3

Submission status: Wrong Answer

Solution code:
def Warshall_Floyd(edges,N):
  """頂点N個のグラフ上の隣接行列edges(空欄はinfとせよ)が与えられたとき, 
  2点間の最短距離距離を隣接行列で返す"""
  for k in range(N):
    for i in range(min(70,N)):
      for j in range(i):
        if edges[i][j]>edges[i][k]+edges[k][j]: return 1
  return 0
 
import sys
from sys import stdin
input = stdin.readline
N=int(input())
A=[list(map(int,input().split())) for i in range(N)]
if Warshall_Floyd(A,N):
  print(-1)
  sys.exit()
 
ans=0
for i in range(min(100,N)):
  for j in range(i):
    need=1
    for k in range(N):
      if k!=i and k!=j and A[i][j]==A[i][k]+A[k][j]:
        need=0
        break
    if need:ans+=A[i][j]
print(ans)

Submission status: Wrong Answer

Solution code:
def Warshall_Floyd(edges,N):
  """頂点N個のグラフ上の隣接行列edges(空欄はinfとせよ)が与えられたとき, 
  2点間の最短距離距離を隣接行列で返す"""
  for k in range(0,N,2):
    for i in range(N):
      for j in range(i):
        if edges[i][j]>edges[i][k]+edges[k][j]: return 1
  return 0
 
import sys
from sys import stdin
input = stdin.readline
N=int(input())
A=[list(map(int,input().split())) for i in range(N)]
if Warshall_Floyd(A,N):
  print(-1)
  sys.exit()
 
ans=0
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
def Warshall_Floyd(edges,N):
  """頂点N個のグラフ上の隣接行列edgesが与えられたとき, 
  2点間の最短距離距離を隣接行列で返す"""
  import copy
  d=copy.deepcopy(A)
  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
N=int(input())
A=[list(map(int,input().split())) for i in range(N)]
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 main():
    """
    ワーシャルフロイドで経由したときに変更がないことを確認する
    変更がある場合、
        最短経路ではないため条件を満たさない
    変更がない場合、
        経由の経路でも最短距離になるケースを除いて距離を計算する
    """
    N = int(input())
    a = [None] * N
    total = 0
    for i in range(N):
        a[i] = list(map(int, input().split()))
        total += sum(a[i])

    for k in range(N):
        for i in range(N):
            for j in range(N):
                # compare from-to / from-経由地点-to
                d = a[i][k] + a[k][j]
                if a[i][j] > d:
                    return -1
                a[i][j] = min(a[i][j],
                              a[i][k] + a[k][j])

    no_need = 0
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if i == k or j == k:
                    continue
                if a[i][j] == a[i][k] + a[k][j]:
                    no_need += a[i][j]

    # 対称なので半分にする
    return (total - no_need) // 2

if __name__ == '__main__':
    answer = main()
    print(answer)

Submission status: Wrong Answer

Solution code:
def main():
    """
    ワーシャルフロイドで経由したときに変更がないことを確認する
    変更がある場合、
        最短経路ではないため条件を満たさない
    変更がない場合、
        経由の経路でも最短距離になるケースを除いて距離を計算する
    """
    N = int(input())
    a = [None] * N
    total = 0
    no_need = 0
    for i in range(N):
        a[i] = list(map(int, input().split()))
        total += sum(a[i])

    for k in range(N):
        # from
        for i in range(N):
            # to
            for j in range(N):
                # compare from-to / from-経由地点-to
                if i == k or j == k:
                    continue
                d = a[i][k] + a[k][j]
                if a[i][j] > d:
                    return -1
                elif a[i][j] == d:
                    # 経由して同じであれば必要ない
                    no_need += d

    # 対称なので半分にする
    return (total - no_need) // 2

if __name__ == '__main__':
    answer = main()
    print(answer)

Submission status: Wrong Answer

Solution code:
import numpy as np

n = int(input())
a_all = []
for i in range(n):
    a_list = input().split()
    a_list = [int(a) for a in a_list]
    a_all.append(a_list)

a_array = np.array(a_all)
# for i in range(n):
#     a_array[i][:i] = 0

a_goukeiyou = np.copy(a_array)
    
huseiritsu = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        for k in range(j+1,n):
            hen1 = a_array[i][j]
            hen2 = a_array[j][k]
            hen3 = a_array[i][k]
            if hen1 <= hen2 + hen3 and hen2 <= hen1+hen3 and hen3 <= hen1 + hen2:
                if hen1 == hen2 + hen3:
                    a_goukeiyou[i][j]=0
                    a_goukeiyou[j][i]=0
                elif hen2 == hen3 + hen1:
                    a_goukeiyou[j][k]=0
                    a_goukeiyou[k][j]=0
                elif hen3 == hen1 + hen2:
                    a_goukeiyou[i][k]=0
                    a_goukeiyou[k][i]=0
            else:
                huseiritsu = 1
                break
        if huseiritsu ==1:
            break
    if huseiritsu == 1:
        break

if huseiritsu == 1:
    print("-1")
else:
    print(a_goukeiyou.sum()/2)

Submission status: Wrong Answer

Solution code:
import sys

n = int(input())

def check(field):
    row, col = [], [[] for x in range(n)]
    for i in range(n):
        ff, fb = field[i][:i], field[i][i:]
        if fb[0]:
            return False
        row.append(fb[1:])
        for i, v in enumerate(ff):
            col[i].append(v)
    return row == col, sum(map(sum, row))

field = [list(map(int, input().split())) for x in range(n)]
ch, su = check(field)
if not ch:
    print(-1)

calc = [[0 for x in range(n)] for xx in range(n)]
calc[0] = field[0][:]
for i, f in enumerate(field[1:], 2):
    for j, v in enumerate(f[i:]):
        s = calc[i - 2][i - 1 + j] + f[i + j]
        target = calc[i - 2][i + j]
        # print(calc[i - 2][i - 1 + j], f[i + j], calc[i - 2][i + j], "@")
        # print(s, calc[i-2][i+j])
        # for c in calc:
        #     print(c)
        if s < target:
            # no
            print(-1)
            sys.exit()
        else:
            # yes
            calc[i - 1][i + j] = s


for i in range(n):
    for j in range(i + 1, n):
        for k in range(n):
            # print(i + 1, j + 1, k + 1)
            if k in [i, j]:
                continue
            # i - j in k ?
            if field[i][j] == field[i][k] + field[j][k]:
                # print(field[i][j])
                su -= field[i][j]
            # print("----")
print(su)

Submission status: Wrong Answer

Solution code:
def print_path(prev, cost):
    for i in range(len(prev)):
        print("%d, prev = %d, cost = %d" %  (i, prev[i], cost[i]))

def get_path(start, goal, prev):
    path = []
    now = goal
    path.append(now)
    while True:
        path.append(prev[now])
        if prev[now] == start: break
        now = prev[now]
    path.reverse()
    return path


def search(glaph, start, goal):
    MAX_VAL = 0x10000000
    g_size = len(glaph)
    visited = [False] * g_size
    cost = [MAX_VAL] * g_size
    prev = [None] * g_size
    cost[start] = 0
    prev[start] = start
    now = start
    while True:
        min = MAX_VAL
        next = -1
        visited[now] = True
        for i in range(g_size):
            if visited[i]: continue
            if glaph[now][i]:
                tmp_cost = glaph[now][i] + cost[now]
                if cost[i] > tmp_cost:
                    cost[i] = tmp_cost
                    prev[i] = now
            if min > cost[i]:
                min = cost[i]
                next = i
        if next == -1: break
        now = next
    return cost[goal]

def solve():
    N = int(input())
    A = []
    for _ in range(N):
        tmp = list(map(int, input().split()))
        A.append(tmp)
        
    cnt = 0
    min_v = 1e10
    flag = False
    for i in range(N):
        for j in range(N):
            if i == j:
                pass
            elif A[i][j] == search(A, i, j):
                B = search(A, i, j)
                if B <= min_v:
                    min = B
                cnt += 1
            else:
                flag = True
                break
            if flag:
                break
    
    if cnt == N**2 - N:
        print(min)
    else:
        print(-1)
        
solve()

Submission status: Wrong Answer

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

for i in range(int((n/2) + 0.5)):
    for j in range(i+1,n):
        s += a[i][j]
if s >= a[0][n-1] * 2:
    ans = s - a[0][n-1]
else:
    ans = -1
print(ans)

Submission status: Wrong Answer

Solution code:
def print_path(prev, cost):
    for i in range(len(prev)):
        print("%d, prev = %d, cost = %d" %  (i, prev[i], cost[i]))

def get_path(start, goal, prev):
    path = []
    now = goal
    path.append(now)
    while True:
        path.append(prev[now])
        if prev[now] == start: break
        now = prev[now]
    path.reverse()
    return path


def search(glaph, start, goal):
    MAX_VAL = 0x10000000
    g_size = len(glaph)
    visited = [False] * g_size
    cost = [MAX_VAL] * g_size
    prev = [None] * g_size
    cost[start] = 0
    prev[start] = start
    now = start
    while True:
        min = MAX_VAL
        next = -1
        visited[now] = True
        for i in range(g_size):
            if visited[i]: continue
            if glaph[now][i]:
                tmp_cost = glaph[now][i] + cost[now]
                if cost[i] > tmp_cost:
                    cost[i] = tmp_cost
                    prev[i] = now
            if min > cost[i]:
                min = cost[i]
                next = i
        if next == -1: break
        now = next
    return cost[goal]

def solve():
    N = int(input())
    A = []
    for _ in range(N):
        tmp = list(map(int, input().split()))
        A.append(tmp)
        
    cnt = 0
    min_v = 1e10
    for i in range(N):
        for j in range(N):
            if i == j:
                pass
            else:
                B = search(A, i, j)
                if A[i][j] == B:
                    if B <= min_v:
                        min = B
                    cnt += 1
    
    if cnt == N**2 - N:
        print(min)
    else:
        print(-1)
        
solve()

Submission status: Wrong Answer

Solution code:
n = int(input())
M = []
Sum = 0
for _ in range(n):
  m = list(map(int, input().split()))
  M.append(m)

def wf():
    for k in range(n):
        for i in range(n):
            for j in range(n):
              if M[i][j] > M[i][k] + M[k][j]:
                return True
    return False

def prim():
 color = [0] * n
 d = [float("inf")] * n
 d[0] = 0
 
 while True:
  minv = float("inf")
  u = -1
  for i in range(n):
   if minv > d[i] and color[i] != 2:
    u = i
    minv = d[i]
  if u == -1: break
  color[u] = 2
  for v in range(n):
   if color[v] != 2 and M[u][v] != float("inf"):
    if d[v] > M[u][v]:
     d[v] = M[u][v]
 return sum(d)
  
if wf(): print(-1)
else:
  print(prim())

Submission status: Wrong Answer

Solution code:
def get_path(start, goal, prev):
    path = []
    now = goal
    path.append(now)
    while True:
        path.append(prev[now])
        if prev[now] == start: break
        now = prev[now]
    path.reverse()
    return path

def search(glaph, start, goal):
    MAX_VAL = 10**9 + 1
    g_size = len(glaph)
    visited = [False] * g_size
    cost = [MAX_VAL] * g_size
    prev = [None] * g_size
    cost[start] = 0
    prev[start] = start
    now = start
    while True:
        min = MAX_VAL
        next = -1
        visited[now] = True
        for i in range(g_size):
            if visited[i]: continue
            if glaph[now][i]:
                tmp_cost = glaph[now][i] + cost[now]
                if cost[i] > tmp_cost:
                    cost[i] = tmp_cost
                    prev[i] = now
            if min > cost[i]:
                min = cost[i]
                next = i
        if next == -1: break
        now = next
    #return [get_path(start, goal, prev), cost[goal]]
    return cost[goal]


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

#入力を辺の重みとして、ベルマンフォードやって、入力と一致するかどうか調べる
# 閉路でそのへんが必要かどうか→その辺を落としたときに、
# その両端の点の最短距離が変更されないなら、その辺は不必要
# もし途中で入力より短くなってしまったらそのグラフは存在しない
# そうすればベルマンフォード 不要

#いらない辺、不正を探す
for i in range(n):
    for j in range(i + 1, n):
        no = a[i][j]
        a[i][j] = 0
        a[j][i] = 0
        #path, cost = search(test, i, j)
        cost = search(a, i, j)
        #不正
        if cost < a[i][j]:
            print(-1)
            exit()
        #必要な辺
        elif cost > a[i][j]:
            a[i][j] = no
            a[j][i] = no
ans = 0
for i in range(n):
    ans += sum(a[i])
print(int(ans/2))

Submission status: Wrong Answer

Solution code:
import copy

def get_path(start, goal, prev):
    path = []
    now = goal
    path.append(now)
    while True:
        path.append(prev[now])
        if prev[now] == start: break
        now = prev[now]
    path.reverse()
    return path

def search(glaph, start, goal):
    MAX_VAL = 0x10000000
    g_size = len(glaph)
    visited = [False] * g_size
    cost = [MAX_VAL] * g_size
    prev = [None] * g_size
    cost[start] = 0
    prev[start] = start
    now = start
    while True:
        min = MAX_VAL
        next = -1
        visited[now] = True
        for i in range(g_size):
            if visited[i]: continue
            if glaph[now][i]:
                tmp_cost = glaph[now][i] + cost[now]
                if cost[i] > tmp_cost:
                    cost[i] = tmp_cost
                    prev[i] = now
            if min > cost[i]:
                min = cost[i]
                next = i
        if next == -1: break
        now = next
    #return [get_path(start, goal, prev), cost[goal]]
    return cost[goal]


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

#入力を辺の重みとして、ベルマンフォードやって、入力と一致するかどうか調べる
# 閉路でそのへんが必要かどうか→その辺を落としたときに、
# その両端の点の最短距離が変更されないなら、その辺は不必要
# もし途中で入力より短くなってしまったらそのグラフは存在しない
# そうすればベルマンフォード 不要

#いらない辺、不正を探す
for i in range(n):
    for j in range(i + 1, n):
        test = copy.deepcopy(a)
        test[i][j] = 0
        test[j][i] = 0
        #path, cost = search(test, i, j)
        cost = search(test, i, j)
        #不正
        if cost < a[i][j]:
            print(-1)
            exit()
        #なくても良い辺
        elif cost == a[i][j]:
            a = test
ans = 0
for i in range(n):
    ans += sum(a[i])
print(int(ans/2))

Submission status: Wrong Answer

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# coding: utf-8

import sys

N = int(input())
M = [[int(x) for x in input().split()] for _ in range(N)]

ret = 0
for i in range(N):
    ret += sum(M[i])

for k in range(N):
    for i in range(N):
        for j in range(N):
            if i == j or i == k or j == k:
                continue
            if M[i][j] > M[i][k] + M[k][j]:
                print(-1)
                sys.exit()
            if M[i][j] == M[i][k] + M[k][j]:
                ret -= M[i][j]

print(ret//2)

Submission status: Time Limit Exceeded

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

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

f = 0
r = [[1] * N 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]:
                f = 1
            elif A[i][j] == A[i][k] + A[k][j] and i != k and j != k:
                r[i][j] = 0

if f == 1:
    print("-1")
else:
    #print(r)
    ans = 0
    for i in range(N):
        for j in range(i+1, N):
            ans += A[i][j] * r[i][j]

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
INF = 10**10
cost = [[INF]*N for _ in range(N)] # INFで初期化v

for u in range(N):
    C = list(map(int, input().split()))
    for v in range(N):
        if u==v: # 自身への道路はINFのままにする
            continue
        cost[u][v] = C[v]
 
ans = 0
for u in range(N):
    for v in range(u+1,N): # u < v
        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: Time Limit Exceeded

Solution code:
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

answer = 0
for i in range(N):
    for j in range(i+1, N):
  
        count = INF
        for k in range(N):   
            count = min(count, A[i][k] + A[k][j])
        
        if A[i][j] > count:
            print(-1)
            exit()

        if A[i][j] < count:
            answer += A[i][j]
        
print(answer)

Submission status: Time Limit Exceeded

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

e=[[True]*N for _ in range(N)]
ans=0
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()
      elif (A[i][j]==A[i][k]+A[k][j]) and (A[i][k]!= 0) and (A[k][j]!= 0):
        e[i][j]=False

ans=0
for i in range(N):
  for j in range(N):
    if e[i][j]: ans+=A[i][j]

print(ans//2)

Submission status: Time Limit Exceeded

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

for i in r: A[i][i] = float('inf')
possible = True
ans = 0
for i in r :
    for j in range(i+1,N):
        for k in r:
            if A[i][j] < A[i][k] + A[k][j]:
                continue
            elif A[i][j] == A[i][k] + A[k][j]:
                break
            else:
                possible = False
                break
        else:
            ans += A[i][j]
print(ans if possible else -1)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product

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

for i in r: A[i][i] = float('inf')
possible = True
ans = 0
for i in r :
    for j in range(i+1,N):
        for k in r:
            if A[i][j] < A[i][k] + A[k][j]:
                continue
            elif A[i][j] == A[i][k] + A[k][j]:
                break
            else:
                possible = False
            break
        else:
            ans += A[i][j]
print(ans if possible else -1)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product

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

for i in r: A[i][i] = float('inf')
possible = True
ans = 0
for i,j in product(r, r) :
    if j <= i: continue
    for k in r:
        if A[i][j] < A[i][k] + A[k][j]:
            continue
        elif A[i][j] == A[i][k] + A[k][j]:
            break
        else:
            possible = False
        break
    else:
        ans += A[i][j]
print(ans if possible else -1)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product

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

possible = True
ans = 0
for i,j in product(r, r) :
    if j <= i: continue
    for k in r:
        if k == i or k == j:
            continue
        if A[i][j] < A[i][k] + A[k][j]:
            continue
        elif A[i][j] == A[i][k] + A[k][j]:
            break
        else:
            possible = False
        break
    else:
        ans += A[i][j]
print(ans if possible else -1)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product

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

possible = True
ans = 0
for i,j in product(r, r) :
    for k in r:
        if k == i or k == j:
            continue
        if A[i][j] < A[i][k] + A[k][j]:
            continue
        elif A[i][j] == A[i][k] + A[k][j]:
            break
        else:
            possible = False
        break
    else:
        ans += A[i][j]
print(ans//2 if possible else -1)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
with open(0) as f:
    N = int(f.readline())
    A = [list(map(int, line.split())) for line in f.readlines()]

possible = True
ans = 0
r = range(N)
for i,j in product(r, r) :
    for k in r:
        if k == i or k == j:
            continue
        if A[i][j] < A[i][k] + A[k][j]:
            continue
        elif A[i][j] == A[i][k] + A[k][j]:
            break
        else:
            possible = False
        break
    else:
        ans += A[i][j]
print(ans//2 if possible else -1)

Submission status: Time Limit Exceeded

Solution code:

with open(0) as f:
    N = int(f.readline())
    A = [list(map(int, line.split())) for line in f.readlines()]

possible = True
ans = 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
            if A[i][j] < A[i][k] + A[k][j]:
                continue
            elif A[i][j] == A[i][k] + A[k][j]:
                break
            else:
                possible = False
                break
        else:
            ans += A[i][j]
print(ans if possible else -1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

with open(0) as f:
    N = int(f.readline())
    A = [list(map(int, line.split())) for line in f.readlines()]

possible = True
ans = 0
for i in range(N):
    for j in range(i+1, N):
        for k in range(N):
            if k in (i, j):
                continue
            if A[i][j] < A[i][k] + A[k][j]:
                continue
            elif A[i][j] == A[i][k] + A[k][j]:
                break
            else:
                possible = False
                break
        else:
            ans += A[i][j]
print(ans if possible else -1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

with open(0) as f:
    N = int(f.readline())
    A = [list(map(int, line.split())) for line in f.readlines()]

A = np.array(A, dtype='int64')
possible = True
ans = 0
for i in range(N):
    for j in range(i+1, N):
        for k in range(N):
            if k in (i, j):
                continue
            if A[i, j] < A[i, k] + A[k, j]:
                continue
            if A[i, j] == A[i, k] + A[k, j]:
                break
            if A[i, j] > A[i, k] + A[k, j]:
                possible = False
                break
        else:
            ans += A[i, j]
print(ans if possible else -1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse.csgraph import dijkstra
from itertools import count

with open(0) as f:
    N = int(f.readline())
    A = [list(map(int, line.split())) for line in f.readlines()]

A = np.array(A, dtype='int64')
shortcut = dijkstra(A, directed=False)
if not np.array_equal(A, shortcut):
    print(-1)
    exit()

ans = 0
for i in range(N):
    for j in range(i+1, N):
        for k in range(N):
            if k in (i, j):
                continue
            if A[i, j] < A[i, k] + A[k, j]:
                continue
            if A[i, j] == A[i, k] + A[k, j]:
                break
        else:
            ans += A[i, j]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse.csgraph import dijkstra
from itertools import count

with open(0) as f:
    N = int(f.readline())
    A = [list(map(int, line.split())) for line in f.readlines()]

A = np.array(A, dtype='int64')
shortcut = dijkstra(A, directed=False)
if not np.array_equal(A, shortcut):
    print(-1)
    exit()

for i in count():
    if i == N:
        break
    for j in count(i+1):
        if j == N:
            break
        if A[i, j] == 0:
            continue
        for k in count():
            if k == N:
                break
            if A[i, k] == 0 or A[j, k] == 0:
                continue
            if A[i, j] == A[i, k] + A[k, j]:
                A[i, j] = A[j, i] = 0

print(sum(sum(A))//2)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse.csgraph import dijkstra

with open(0) as f:
    N = int(f.readline())
    A = [list(map(int, line.split())) for line in f.readlines()]

A = np.array(A, dtype='int64')
shortcut = dijkstra(A, directed=False)
if not np.array_equal(A, shortcut):
    print(-1)
    exit()

for i in range(N):
    for j in range(i+1,N):
        if A[i, j] == 0:
            continue
        for k in range(N):
            if A[i, k] == 0 or A[j, k] == 0:
                continue
            if A[i, j] == A[i, k] + A[k, j]:
                A[i, j] = A[j, i] = 0

print(sum(sum(A))//2)

Submission status: Time Limit Exceeded

Solution code:
import sys
import copy
n = int(input())
dist = [list(map(int,input().split())) for _ in range(n)]
e = copy.deepcopy(dist)
for k in range(n):
    for i in range(n):
        for j in range(n):
            if dist[i][j]>dist[i][k] + dist[k][j]:
                print(-1)
                sys.exit()
            if i!=j and i!=k and j!=k and dist[i][j]==dist[i][k] + dist[k][j]:
                #print(i,j,k)
                e[i][j]=float("inf")

#[print(*dist[l]) for l in range(n)]
ans = 0
for i in range(n):
    for j in range(n):
        if e[i][j]!=float("inf"):
            ans += dist[i][j]
print(ans//2)

Submission status: Time Limit Exceeded

Solution code:
import sys
import copy
n = int(input())
dist = [list(map(int,input().split())) for _ in range(n)]
e = copy.deepcopy(dist)
for k in range(n):
    for i in range(n):
        for j in range(n):
            if dist[i][j]>dist[i][k] + dist[k][j]:
                print(-1)
                sys.exit()
            if dist[i][j]==dist[i][k] + dist[k][j] and i!=j and i!=k and j!=k:
                #print(i,j,k)
                e[i][j]=float("inf")

#[print(*dist[l]) for l in range(n)]
ans = 0
for i in range(n):
    for j in range(n):
        if e[i][j]!=float("inf"):
            ans += dist[i][j]
print(ans//2)

Submission status: Time Limit Exceeded

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify, heappop, heappush

def dijkstra_heap(s,edge): #edgeが複数パターンある場合には引数に入れることも可能 dijkstra_heap(s,edge)
    #始点sから各頂点への最短距離
    d = [float("inf")] * N
    used = [True] * N #True:未確定。始点として探索されたか。というかdが更新されたか。
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heappush(edgelist,e)
    while len(edgelist):
        minedge = heappop(edgelist)
        #まだ使われてない頂点の中からスタートから最小の距離のものを探す
        if not used[minedge[1]]: #すでに探索済みの場合にはスキップして次のプライオリティーキューへ。
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False #ここで始点として探索済みにする。
        for e in edge[v]:
            if used[e[1]]: #行き先がすでに始点として探索済みでない場合には値を更新。
                heappush(edgelist,(e[0]+d[v],e[1])) #重みをスタートからの最短重みにするため+d[v]
    return d ##始点sから各頂点への最短距離がアウトプットとなる。

N = int(input())
HQ = [];A = []
for i in range(N):
  temp = list(map(int,input().split()))
  A.append(temp)
  for j in range(i+1,N):
    heappush(HQ,(temp[j],i,j))
#print(HQ)
G = [[] for _ in range(N)]
ans = 0
while HQ:
  dis, start, goal = heappop(HQ)
  d = dijkstra_heap(start,G)
  if d[goal] < dis: #既に近い距離で到達できるなら矛盾
    print(-1); exit()
  elif d[goal] == dis:
    continue
  else: #d[goal] > dis:
    ans += dis
    G[start].append((dis,goal))
    G[goal].append((dis,start))
print(ans)