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: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop

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

dist = [[INF] * n for _ in range(n)]
ans = 0
while que:
    c, i, j = heappop(que)
    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: Time Limit Exceeded

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

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

flag = True
for i in range(N):
    for j in range(N):
        if A[i][j] != B[i][j]:
            flag = False
            break
    if not flag:
        break

if not flag:
    print(-1)
    exit()


for i in range(N):
    for j in range(N):
        for k in range(N):
            if i == k or j == k:
                continue
            if A[i][k] + A[k][j] == A[i][j]:
                B[i][j] = 0
print(sum(map(sum, B))//2)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n = int(input())
"""a = []
for i in range(n):#h:高さ
    a.append([int(m) for m in input().split()])"""
a = [np.array(input().split(), dtype=np.int64) for _ in [0]*n]
"""d = [[float("inf") for i in range(n + 1)] for i in range(n + 1)]
#d[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(n):
    for j in range(n):
        d[x][y] = z
        d[y][x] = z"""


def warshall_floyd(n,d):
    e = [[0 for i in range(n)] for i in range(n)]
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if d[i][j] > d[i][k] + d[k][j]:
                    print(-1)
                    exit()
                elif d[i][j] == d[i][k] + d[k][j] and i != j and i != k and j != k:
                    e[i][j] = float("INF")
    return (d, e)

##############################
b = warshall_floyd(n,a)[0]
c = warshall_floyd(n,a)[1]
ans = 0
for i in range(n):
    for j in range(n):
        if c[i][j] != float("INF"):
            ans += b[i][j]
ans = ans // 2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
INF = 10 ** 12

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

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]:
                print(-1)
                exit()

res = 0
for i in range(N):
    for j in range(i + 1, N):
        for k in range(N):
            if i != k and j != k and a[i][j] == a[i][k] + a[k][j]:
                break
        else:
            res += a[i][j]

print(res)

Submission status: Time Limit Exceeded

Solution code:
def warshall_floyd(graph):
    num_v = len(graph)

    for k in range(num_v):
        for i in range(num_v):
            for j in range(num_v):
                if graph[i][j] > graph[i][k] + graph[k][j]:
                    graph[i][j] = graph[i][k] + graph[k][j]
    return graph

N = int(input())
graph = [[float("inf") for _ in range(N)] for _ in range(N)]
for i in range(N):
    a_list = list(map(int, input().split()))
    for j in range(N):
        if i == j:
            continue
        graph[i][j] = a_list[j]
# import copy
# a_list = copy.deepcopy(graph)
from scipy.sparse.csgraph import floyd_warshall
w_graph = floyd_warshall(graph, directed=False)
result = 0
for i in range(N):
     w_graph[i][i] = float("inf")
for i in range(N):
    for j in range(i):
        if i == j:
            continue
        if w_graph[i][j] != graph[i][j]:
            print(-1)
            exit()
        d = []
        for k in range(N):
            d.append(w_graph[i][k] + w_graph[j][k])
        if min(d) > w_graph[i][j]:
            result += w_graph[i][j]
print(int(result))

Submission status: Time Limit Exceeded

Solution code:
def warshall_floyd(graph):
    num_v = len(graph)

    for k in range(num_v):
        for i in range(num_v):
            for j in range(num_v):
                if graph[i][j] > graph[i][k] + graph[k][j]:
                    graph[i][j] = graph[i][k] + graph[k][j]
    return graph

N = int(input())
graph = [[float("inf") for _ in range(N)] for _ in range(N)]
for i in range(N):
    a_list = list(map(int, input().split()))
    for j in range(N):
        if i == j:
            continue
        graph[i][j] = a_list[j]
import copy
a_list = copy.deepcopy(graph)
from scipy.sparse.csgraph import floyd_warshall
w_graph = floyd_warshall(graph, directed=False)
result = 0
for i in range(N):
     w_graph[i][i] = float("inf")
for i in range(N):
    for j in range(i):
        if i == j:
            continue
        if w_graph[i][j] != a_list[i][j]:
            print(-1)
            exit()
        d = []
        for k in range(N):
            d.append(w_graph[i][k] + w_graph[j][k])
        if min(d) > w_graph[i][j]:
            result += w_graph[i][j]
print(int(result))

Submission status: Time Limit Exceeded

Solution code:
def warshall_floyd(graph):
    num_v = len(graph)

    for k in range(num_v):
        for i in range(num_v):
            for j in range(num_v):
                if graph[i][j] > graph[i][k] + graph[k][j]:
                    graph[i][j] = graph[i][k] + graph[k][j]
    return graph

N = int(input())
graph = [[float("inf") for _ in range(N)] for _ in range(N)]
for i in range(N):
    a_list = list(map(int, input().split()))
    for j in range(N):
        if i == j:
            continue
        graph[i][j] = a_list[j]
import copy
a_list = copy.deepcopy(graph)
w_graph = warshall_floyd(graph)
result = 0
for i in range(N):
    for j in range(i+1, N):
        if i == j:
            continue
        if w_graph[i][j] != a_list[i][j]:
            print(-1)
            exit()
        d = []
        for k in range(N):
            d.append(w_graph[i][k] + w_graph[j][k])
        if min(d) > w_graph[i][j]:
            result += w_graph[i][j]
print(result)

Submission status: Time Limit Exceeded

Solution code:
import sys
n=int(input())
A=[]
kyori=[]
for i in range(n):
    tmp=list(map(int,input().split()))
    A.append(tmp)
for i in range(n):
    kyori.append([x for x in A[i]])


for i in range(n):
    for j in range(n):
        for k in range(n):
            if(kyori[j][i] + kyori[i][k] < kyori[j][k]):
                print(-1)
                sys.exit()
            elif (kyori[j][i] + kyori[i][k] == kyori[j][k] and j!=i and i!=k):
                A[j][k]=0
                A[k][j]=0
ans=0
for i in range(n):
    for j in range(n):
        ans+=A[i][j]
print(ans//2)

Submission status: Time Limit Exceeded

Solution code:
import heapq
N = int(input())
A = [[] for i in range(N)]
Q = []
for i in range(N):
  A[i] = [int(x) for x in input().split()]
  for j in range(i + 1, N):
    heapq.heappush(Q, [A[i][j], i, j])
G = [[10 ** 9 + 1 for j in range(N)] for i in range(N)]
for i in range(N):
  G[i][i] = 0
cnt = 0
while Q:
  [d, s, t] = heapq.heappop(Q)
  add = True
  for k in range(N):
    if d > G[s][k] + G[k][t]:
      break
    if d == G[s][k] + G[k][t]:
      add = False
  else:
    G[s][t] = d
    G[t][s] = d
    cnt += d if add else 0
    continue
  print(-1)
  break
else:
  print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import heapq
import sys

class Dijkstra(object):
    def dijkstra(self, adj, start, goal=None):
        '''
        ダイクストラアルゴリズムによる最短経路を求めるメソッド
        入力
        adj: adj[i][j]の値が頂点iから頂点jまでの距離(頂点iから頂点jに枝がない場合，値はfloat('inf'))となるような2次元リスト(正方行列)
        start: 始点のID
        goal: オプション引数．終点のID
        出力
        goalを引数に持つ場合，startからgoalまでの最短経路を格納したリストを返す
        持たない場合は，startから各頂点までの最短距離を格納したリストを返す
        '''
        num = len(adj)          # グラフのノード数
        dist = [float('inf') for i in range(num)] # 始点から各頂点までの最短距離を格納する
        prev = [float('inf') for i in range(num)] # 最短経路における，その頂点の前の頂点のIDを格納する
        
        dist[start] = 0
        q = []                  # プライオリティキュー．各要素は，(startからある頂点vまでの仮の距離, 頂点vのID)からなるタプル
        heapq.heappush(q, (0, start)) # 始点をpush

        while len(q) != 0:
            prov_cost, src = heapq.heappop(q) # pop
            
            # プライオリティキューに格納されている最短距離が，現在計算できている最短距離より大きければ，distの更新をする必要はない
            if dist[src] < prov_cost:
                continue

            # 他の頂点の探索
            for dest in range(num):
                cost = adj[src][dest]
                if(cost != float('inf') and dist[dest] >= dist[src] + cost):
                    if(dest!=src):
                        prev[dest]=src
                if cost != float('inf') and dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost # distの更新
                    heapq.heappush(q, (dist[dest], dest)) # キューに新たな仮の距離の情報をpush

                    
        if goal is not None:
            return self.get_path(goal, prev)
        else:
            return (dist,prev)

    def get_path(self, goal, prev):
        '''
        始点startから終点goalまでの最短経路を求める
        '''
        path = [goal]           # 最短経路
        dest = goal

        # 終点から最短経路を逆順に辿る
        while prev[dest] != float('inf'):
            path.append(prev[dest])
            dest = prev[dest]

        # 経路をreverseして出力
        return list(reversed(path))


n=int(input())
G=[]
for _ in range(n):
    tmp=list(map(int,input().split()))
    G.append(tmp)

Dij=Dijkstra()
for i in range(n):
    result=Dij.dijkstra(G,i)
    dis=result[0]
    pre=result[1]
    for j in range(n):
        if(dis[j] < G[i][j]):
            print(-1)
            sys.exit()
        if(dis[j] == G[i][j] and pre[j]!=i):
            G[i][j]=float("inf")

ans=0
for i in range(n):
    for j in range(n):
        if(G[i][j]!=float("inf")):
            ans+=G[i][j]
print(ans//2)

Submission status: Time Limit Exceeded

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


num = 0

for i in range(N):
    for j in range(i + 1, N):
        flag = True
        for k in range(N):
            if i == k or k == j:
                continue
            if A[i][j] > A[i][k] + A[k][j]:
                print(-1)
                exit()
            elif A[i][j] == A[i][k] + A[k][j]:
                flag = False

        if flag:
            num += A[i][j]

print(num)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

dp = [[int(x) for x in input().split()] for _ in range(n)]

if n == 1:
    print(0)
    exit()
elif n == 2:
    print(dp[0][1])
    exit()

ans = 0
for i in range(n - 1):
    for j in range(i + 1, n):
        check = 0
        for k in range(n):
            if k != i and k != j:
                if dp[i][k] + dp[k][j] < dp[i][j]:
                    print(-1)
                    exit()
                elif dp[i][k] + dp[k][j] == dp[i][j]:
                    check = 1
                    break
        if check == 0:
            ans += dp[i][j]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

dp = [[int(x) for x in input().split()] for _ in range(n)]

if n == 1:
    print(0)
    exit()
elif n == 2:
    print(dp[0][1])
    exit()

ans = 0
for i in range(n - 1):
    for j in range(i + 1, n):
        temp = 2000000001
        for k in range(n):
            if k != i and k != j:
                temp = min(temp, (dp[i][k] + dp[k][j]))
        if temp < dp[i][j]:
            print(-1)
            exit()
        if temp > dp[i][j]:
            ans += dp[i][j]

print(ans)

Submission status: Time Limit Exceeded

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 k in range(N):
    for i in range(N):
        for j in range(i):
            if i != k and j != k:
                if cost[i][j] == cost[i][k]+cost[k][j]:
                    edge[i][j] = 0
                if cost[i][j] > cost[i][k]+cost[k][j]:
                    cost[i][j] = cost[i][k]+cost[k][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: Time Limit Exceeded

Solution code:
import copy
N = int(input())
A = [list(map(int,input().split())) for i in range(N)]
cost = copy.deepcopy(A)
edge = [[True for i in range(N)] for i in range(N)]
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]:
                    edge[i][j] = False
                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:
    import numpy as np
    A = np.array(A)
    edge = np.array(edge)
    print(A[edge].sum()//2)

Submission status: Time Limit Exceeded

Solution code:
import itertools
N = int(input())
A = [[int(i) for i in input().split()] for j in range(N)]
for i in range(N):
    A[i][i] = float("inf")
Node = [int(i) for i in range(N)]
Comb = list(itertools.combinations(Node, 2))
 
Total, Possible = 0, True
for c in Comb:
    a = A[c[0]][c[1]]
    for i in range(N):
        if A[c[0]][i] + A[c[1]][i] == a:
            break
        elif A[c[0]][i] + A[c[1]][i] < a:
            Possible = False
            break
    else:
        Total += a
    if not Possible:
        print(-1)
        break
else:
    print(Total)

Submission status: Time Limit Exceeded

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))
 
Total = 0
count = 0
while count < N * (N-1) // 2:
    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]:
                    break
                elif A[c[0]][c[1]] > A[c[0]][i] + A[c[1]][i]:
                    count = N**2
                    break
        else:
            Total += A[c[0]][c[1]]
                    
if count == N * (N-1) // 2:
    print(Total)
else:
    print(-1)

Submission status: Time Limit Exceeded

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
Total, count = 0, 0
while count < N * (N-1) // 2:
    for c in Comb:
        a, i, j = A[c[0]][c[1]], c[0], c[1]
        count += 1
        MinDist = float("inf")
        for k in range(N):
            if k != i and k != j:
                if a > A[i][k] + A[k][j]:
                    count = N**2
                    break
                else:
                    MinDist = min(MinDist, A[i][k] + A[k][j])
        else:
            Total += (a if MinDist > a else 0)
        
if count == N*(N-1)//2:
    print(Total)
else:
    print(-1)

Submission status: Time Limit Exceeded

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) // 2:
    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
                    break
                    
if Possible:
    Total = 0
    for i in range(N):
        Total += sum(A[i])
    Total //= 2
    Total -= NoNeed
    print(Total)
else:
    print(-1)

Submission status: Time Limit Exceeded

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) // 2:
    for c in Comb:
        a, i, j = A[c[0]][c[1]], c[0], c[1]
        count += 1
        MinDist = float("inf")
        for k in range(N):
            if k != i and k != j:
                MinDist = min(MinDist, A[i][k] + A[k][j])
        if MinDist < a:
            Possible = False
        elif MinDist == a:
            NoNeed += a
        

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

else:
    print(-1)

Submission status: Time Limit Exceeded

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) // 2:
    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: Time Limit Exceeded

Solution code:
N = int(input())
A = [[int(i) for i in input().split()] for j in range(N)]

Possible = True
NoNeed = set()
for i in range(N-1):
    if not Possible:
        break
    for j in range(i+1, N):
        if not Possible:
            break
        for k in range(N):
            if not Possible:
                break
            if A[i][j] <= A[i][k]+A[j][k]:
                if k != i and k !=j:
                    if A[i][j] == A[i][k]+A[j][k]:
                        NoNeed |= {(i, j)}
            else:
                Possible = False        

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [[int(i) for i in input().split()] for j in range(N)]

Possible = True
NoNeed = set()
for i in range(N-2):
    for j in range(i+1, N-1):
        for k in range(j+1, N):
            a, b, c = A[i][j], A[j][k], A[i][k]
            if a+b>=c and b+c>=a and c+a>=b:
                if a+b==c:
                    NoNeed |= {(i, k)}
                elif b+c==a:
                    NoNeed |= {(i, j)}
                elif c+a == b:
                    NoNeed |= {(j, k)}
            else:
                Possible = False
                break 

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [[int(i) for i in input().split()] for j in range(N)]

Possible = True
NoNeed = set()
for i in range(N-2):
    for j in range(i+1, N-1):
        for k in range(j+1, N):
            a, b, c = A[i][j], A[j][k], A[i][k]
            if a+b>=c and b+c>=a and c+a>=b:
                if a+b==c:
                    NoNeed |= {(i, k)}
                elif b+c==a:
                    NoNeed |= {(i, j)}
                elif c+a == b:
                    NoNeed |= {(j, k)}
            else:
                Possible = False
                break 

if Possible:
    Total = 0
    for i in range(N-1):
        for j in range(i+1, N):
            if (i, j) in NoNeed:
                continue
            else:
                Total += A[i][j]
    print(Total)
else:
    print(-1)

Submission status: Time Limit Exceeded

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

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

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

for k in range(n):
    for i in range(n):
        for j in range(n):
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

for i in range(n):
    for j in range(n):
        if graph[i][j] < a[i][j]:
            print(-1)
            exit()

ans = 0

for i in range(n):
    for j in range(i+1, n):
        v = INF
        for k in range(n):
            if k == i or k == j:
                continue
            v = min(v, graph[i][k] + graph[k][j])
        if v != graph[i][j]:
            ans += graph[i][j]

print(ans)

Submission status: Time Limit Exceeded

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] > key:
        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-1):
    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: Time Limit Exceeded

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
for i in range(N):
    if ans == -1:
        break
    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]:
            min_=0
        else:
            min_=dist[N*i+j]
        ans+=min_
print(ans)

Submission status: Time Limit Exceeded

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

from scipy.sparse.csgraph import floyd_warshall
a_opt = floyd_warshall(a)
# for i in range(n): print(a[i], a_opt[i])

def solve():
    ans = 0
    for i in range(n):
        for j in range(i+1, n):
            if a_opt[i][j] < a[i][j]:
                print(-1)
                return
            else:
                d = a[i][j]
                for k in range(n):
                    if k in [i, j]:
                        continue
                    elif a[i][k]+a[k][j] == d:
                        d = 0
                ans += d
    print(ans)
    return

solve()

Submission status: Time Limit Exceeded

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

def chk():
  v=0
  for j in range(n):
    for i in range(n):
      f=True
      for k in range(n):
        if l[i][j]>l[i][k]+l[k][j]:
          return -1
        if l[i][j]==l[i][k]+l[k][j] and i!=k and k!=j:
          f=False
      if f:v+=l[i][j]
  return v//2
print(chk())

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=[[int(i) for i in input().split()] for i in range(N)]
ans=0
for i in range(N):
    for j in range(i+1,N):
        flag=True
        for k in range(N):
            if j==k or i==k:
                continue
            if A[i][j]>A[i][k]+A[k][j]:
                print(-1)
                exit()
            if A[i][j]==A[i][k]+A[k][j]:
                flag=False
        if flag:
            ans+=A[i][j]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
AtoZ = [chr(i) for i in range(65,65+26)]
atoz = [chr(i) for i in range(97,97+26)]

def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())


N = int(input())
lines = []

for i in range(N):
	lines.append(inpl())

ans = 0
for s in range(N):
	for t in range(s+1,N):
		c = lines[s][t]
		ans += c
		for mid in range(N):
			if mid == s or mid == t:
				continue
			a = lines[s][mid]
			b = lines[mid][t]
			if a+b < c:
				print(-1)
				sys.exit()
			elif a+b == c:
				ans -= c
				break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def warshall_floyd(g):
    d = defaultdict(dict)
    V = list(g.keys())
    for v in g.values():
        V.extend(list(v))
    V = set(V)
    for i in V:
        for j in V:
            if i in g and j in g[i]:
                d[i][j] = g[i][j]
            else:
                d[i][j] = sys.maxsize
    for k in g:
        for i in g:
            for j in g:
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]

    return d


@mt
def slv(N, A):
    g = defaultdict(dict)
    for i, r in enumerate(A):
        for j, c in enumerate(r):
            g[i][j] = c
            g[j][i] = c

    d = warshall_floyd(g)

    for i in range(N):
        for j in range(N):
            if A[i][j] != d[i][j]:
                return -1
    ans = 0
    for i in range(N):
        for j in range(i, N):
            for k in range(N):
                if A[i][k] == 0:
                    continue
                if j != k and A[i][k] + A[k][j] == A[i][j]:
                    break
            else:
                ans += A[i][j]
    return ans


def main():
    N = read_int()
    A = [read_int_n() for _ in range(N)]
    # N = 200
    # A = [[random.randint(1, 10000) for _ in range(N)] for __ in range(N)]
    # for i in range(N):
    #     A[i][i] = 0
    print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):
    EC = []
    for i, r in enumerate(A):
        for j, c in enumerate(r):
            if c == 0:
                break
            EC.append((c, i, j))

    EC.sort()
    ans = 0
    for c, i, j in EC:
        q = [(0, i)]
        min_path = c
        f = True
        while q:
            c2, k = q.pop()
            if k != i and c2 + A[k][j] <= min_path:
                min_path = c2 + A[k][j]
                f = False
            else:
                for l, c3 in enumerate(A[k]):
                    if l != i and c3 != 0 and c2 + c3 < c:
                        q.append((c2 + c3, l))

        if min_path != c:
            return -1
        elif f:
            ans += c
    return ans


def main():
    N = read_int()
    A = [read_int_n() for _ in range(N)]

    print(slv(N, A))


if __name__ == '__main__':
    main()