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:
import sys
from itertools import combinations
from heapq import heappush, heappop, heapify
from numba import njit
import numpy as np


def dijkstra(s, t, links):
    heap = list(links[s])
    heapify(heap)
    visited = set()
    while heap:
        cost, node = heappop(heap)
        if node == t:
            return cost
        if node in visited:
            continue
        visited.add(node)
        for cost2, node2 in links[node]:
            if node2 not in visited:
                heappush(heap, (cost + cost2, node2))
    return float("inf")


@njit("b1(i8[:,:],i8)", cache=True)
def existed(a, n):
    for i in range(n):
        for j in range(n):
            for k in range(n):
                if a[j][k] > a[j][i] + a[i][k]:
                    return False
    return True


def main():
    input = sys.stdin.buffer.readline
    n = int(input())
    a = [list(map(int, input().split())) for _ in range(n)]
    flag = existed(np.array(a, dtype="i8"), n)
    if flag:
        ans = 0
        g = [set() for _ in range(n)]
        hq = []
        for i, j in combinations(range(n), 2):
            heappush(hq, (a[i][j], i, j))
        while hq:
            d, i, j = heappop(hq)
            if dijkstra(i, j, g) > d:
                g[i].add((d, j))
                g[j].add((d, i))
                ans += a[i][j]
        print(ans)
    else:
        print(-1)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import combinations
from heapq import heappush, heappop, heapify
from numba import njit
import numpy as np


def dijkstra(s, t, links):
    heap = list(links[s])
    heapify(heap)
    visited = set()
    while heap:
        cost, node = heappop(heap)
        if node == t:
            return cost
        if node in visited:
            continue
        visited.add(node)
        for cost2, node2 in links[node]:
            if node2 not in visited:
                heappush(heap, (cost + cost2, node2))
    return float("inf")


@njit("b1(i8[:,:],i8)", cache=True)
def existed(a, n):
    for i in range(n):
        for j in range(n):
            for k in range(n):
                if a[j][k] > a[j][i] + a[i][k]:
                    return False
    return True


def main():
    input = sys.stdin.buffer.readline
    n = int(input())
    a = [list(map(int, input().split())) for _ in range(n)]
    flag = existed(np.array(a, dtype="i8"), n)
    if flag:
        ans = 0
        g = [set() for _ in range(n)]
        hq = []
        for i, j in combinations(range(n), 2):
            heappush(hq, (a[i][j], i, j))
        while hq:
            _, i, j = heappop(hq)
            if dijkstra(i, j, g) > a[i][j]:
                g[i].add((a[i][j], j))
                g[j].add((a[i][j], i))
                ans += a[i][j]
        print(ans)
    else:
        print(-1)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import combinations
from heapq import heappush, heappop, heapify
from numba import jit
import numpy as np


def dijkstra(s, t, links):
    heap = list(links[s])
    heapify(heap)
    visited = set()
    while heap:
        cost, node = heappop(heap)
        if node == t:
            return cost
        if node in visited:
            continue
        visited.add(node)
        for cost2, node2 in links[node]:
            if node2 not in visited:
                heappush(heap, (cost + cost2, node2))
    return float("inf")


@jit("b1(i8[:,:],i8)")
def existed(a, n):
    for i in range(n):
        for j in range(n):
            for k in range(n):
                if a[j][k] > a[j][i] + a[i][k]:
                    return False
    return True


def main():
    input = sys.stdin.buffer.readline
    n = int(input())
    a = [list(map(int, input().split())) for _ in range(n)]
    flag = existed(np.array(a, dtype="i8"), n)
    if flag:
        ans = 0
        g = [set() for _ in range(n)]
        hq = []
        for i, j in combinations(range(n), 2):
            heappush(hq, (a[i][j], i, j))
        while hq:
            _, i, j = heappop(hq)
            if dijkstra(i, j, g) > a[i][j]:
                g[i].add((a[i][j], j))
                g[j].add((a[i][j], i))
                ans += a[i][j]
        print(ans)
    else:
        print(-1)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import product, combinations
from heapq import heappush, heappop, heapify


def dijkstra(s, t, links):
    heap = list(links[s])
    heapify(heap)
    visited = set()
    while heap:
        cost, node = heappop(heap)
        if node == t:
            return cost
        if node in visited:
            continue
        visited.add(node)
        for cost2, node2 in links[node]:
            if node2 not in visited:
                heappush(heap, (cost + cost2, node2))
    return float("inf")


def main():
    input = sys.stdin.buffer.readline
    n = int(input())
    a = [list(map(int, input().split())) for _ in range(n)]
    flag = True
    for i, j, k in product(range(n), repeat=3):
        if a[j][k] > a[j][i] + a[i][k]:
            flag = False
    if flag:
        ans = 0
        g = [set() for _ in range(n)]
        hq = []
        for i, j in combinations(range(n), 2):
            heappush(hq, (a[i][j], i, j))
        while hq:
            _, i, j = heappop(hq)
            if dijkstra(i, j, g) > a[i][j]:
                g[i].add((a[i][j], j))
                g[j].add((a[i][j], i))
                ans += a[i][j]
            a[i][j] = 10 ** 12
        print(ans)
    else:
        print(-1)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import product, combinations
import numpy as np
from heapq import heappush, heappop, heapify


def dijkstra(s, t, links):
    heap = list(links[s])
    heapify(heap)
    visited = set()
    while heap:
        cost, node = heappop(heap)
        if node == t:
            return cost
        if node in visited:
            continue
        visited.add(node)
        for cost2, node2 in links[node]:
            if node2 not in visited:
                heappush(heap, (cost + cost2, node2))
    return float("inf")


def main():
    input = sys.stdin.buffer.readline
    n = int(input())
    a = [list(map(int, input().split())) for _ in range(n)]
    flag = True
    for i, j, k in product(range(n), repeat=3):
        if a[j][k] > a[j][i] + a[i][k]:
            flag = False
    if flag:
        ans = 0
        a = np.array(a, dtype="i8")
        g = [set() for _ in range(n)]
        hq = []
        for i, j in combinations(range(n), 2):
            heappush(hq, (a[i, j], i, j))
        while hq:
            _, i, j = heappop(hq)
            if dijkstra(i, j, g) > a[i, j]:
                g[i].add((a[i, j], j))
                g[j].add((a[i, j], i))
                ans += a[i, j]
            a[i, j] = 10 ** 12
        print(ans)
    else:
        print(-1)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = [list(map(int, input().split())) for _ in range(n)]
# 小さい順に調べていく
roads = []
for i in range(n-1):
    for j in range(i+1, n):
        roads.append((A[i][j], i, j))
roads = sorted(roads)

INF = 10**9*1
AD = [[INF]*n for _ in range(n)]
G = [[] for _ in range(n)]
edges = set()
from collections import deque
ok = True
ans = 0
for a, s, e in roads:
    # s to e
    q = deque([[s, 0]])
    visited = [INF] * n
    visited[s] = 0
    while q:
        node, dist = q.popleft()
        if node == e:
            # sからeにたどり着いて
            if dist == a:
                # あたえられた距離と同じならばOK
                break
            elif dist < a:
                # あたえられた距離より小さいならばaは最短距離じゃないNG
                ok = False
                break
        
        for nn, cost in G[node]:
            if dist+cost < visited[nn]:
                visited[nn] = dist+cost
                q.append([nn, dist+cost])
    else:
        # sからeにたどり着けなかったら最短距離確定
        AD[s][e] = a
        G[s].append((e, a))
        G[e].append((s, a))
        ans += a
    if not ok:
        break

print(ans if ok else -1)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = [list(map(int, input().split())) for _ in range(n)]
# 小さい順に調べていく
roads = []
for i in range(n-1):
    for j in range(i+1, n):
        roads.append((A[i][j], i, j))
roads = sorted(roads)

INF = 10**9*1
AD = [[INF]*n for _ in range(n)]
G = [[] for _ in range(n)]
edges = set()
from collections import deque
ans = 0
for a, s, e in roads:
    # s to e
    q = deque([[s, 0]])
    visited = [INF] * n
    visited[s] = 0
    while q:
        node, dist = q.popleft()
        if node == e:
            # sからeにたどり着いて
            if dist == a:
                # あたえられた距離と同じならばOK
                break
            elif dist < a:
                # あたえられた距離より小さいならばaは最短距離じゃないNG
                ans = -1
                break
        
        for nn, cost in G[node]:
            if dist+cost < visited[nn]:
                visited[nn] = dist+cost
                q.append([nn, dist+cost])
    else:
        # sからeにたどり着けなかったら最短距離確定
        AD[s][e] = a
        G[s].append((e, a))
        G[e].append((s, a))
        edges.add((a, s, e))
    if ans == - 1:
        break

if ans == -1:
    print(ans)
else:
    for a, s, e in edges:
        ans += a
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = [list(map(int, input().split())) for _ in range(n)]
# 小さい順に調べていく
from heapq import heappop, heappush
heap = []
for i in range(n-1):
    for j in range(i+1, n):
        a = A[i][j]
        heappush(heap, (a, i, j))

G = [[] for _ in range(n)]
edges = set()
from collections import deque
ans = 0
while heap:
    # s to e
    a, s, e = heappop(heap)
    q = deque([[s, 0]])
    visited = [10**9+1] * n
    visited[s] = 0
    while q:
        node, dist = q.popleft()

        if node == e:
            if dist == a:
                # ok
                break
            elif dist < a:
                ans = -1
                break
        
        for nn, cost in G[node]:
            if dist+cost < visited[nn]:
                visited[nn] = dist+cost
                q.append([nn, dist+cost])
    else:
        # sからeにたどり着けなかったら枝を足す
        G[s].append((e, a))
        G[e].append((s, a))
        edges.add((a, s, e))
    if ans == - 1:
        break

if ans == -1:
    print(ans)
else:
    for a, s, e in edges:
        ans += a
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import product
import numpy as np
from heapq import heappush, heappop, heapify


def dijkstra(s, t, links):
    heap = list(links[s])
    heapify(heap)
    visited = set()
    while heap:
        cost, node = heappop(heap)
        if node == t:
            return cost
        if node in visited:
            continue
        visited.add(node)
        for cost2, node2 in links[node]:
            if node2 not in visited:
                heappush(heap, (cost + cost2, node2))
    return float("inf")


def main():
    input = sys.stdin.buffer.readline
    n = int(input())
    a = [list(map(int, input().split())) for _ in range(n)]
    flag = True
    for i, j, k in product(range(n), repeat=3):
        if a[j][k] > a[j][i] + a[i][k]:
            flag = False
    if flag:
        ans = 0
        a = np.array(a, dtype="i8")
        g = [set() for _ in range(n)]
        for _ in range(n * n):
            i, j = np.unravel_index(np.argmin(a), a.shape)
            if dijkstra(i, j, g) > a[i, j]:
                g[i].add((a[i, j], j))
                g[j].add((a[i, j], i))
                ans += a[i, j]
            a[i, j] = 10 ** 12
        print(ans)
    else:
        print(-1)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
if __name__ == "__main__":
    N = int(input())
    V = N
    dp = []
    for i in range(N):
        dp.append(list(map(int,input().split())))
    edge = [[True]*N for _ in range(N)]
    for k in range(V):
        for i in range(V):
            for j in range(V):
                a = dp[i][j]
                b = dp[i][k]+dp[k][j]
                if a > b:
                    print(-1)
                    exit(0)
                elif a == b and k != i and k != j:
                    edge[i][j] = False
                    edge[j][i] = False
    ans = 0
    for i in range(N):
        for j in range(i+1, N):
            if edge[i][j]:
                ans += dp[i][j]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys 
from heapq import heappop,heappush
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())
data = []
for i in range(N):
    A = list(map(int,readline().split()))
    for j in range(i):
        data.append((A[j],j+1,i+1))
        
def dijkstra(q,edges,dist):
    while q:
        cost, v_from = heappop(q)
        if dist[v_from] < cost:
            continue
        for _cost,v_to in edges[v_from]:
            newcost = cost+_cost
            if newcost < dist[v_to]:
                dist[v_to] = newcost
                heappush(q,(newcost,v_to))             
    return 

data = sorted(data)
edges = [[] for _ in range(N+1)]
INF = 10**31
ans = 0
for c,i,j in data:
    dist = [INF]*(N+1)
    dist[i] = 0
    q = [(0,i)]
    dijkstra(q,edges,dist)
    if c < dist[j]:
        edges[i].append((c,j))
        edges[j].append((c,i))
        ans += c
    elif c > dist[j]:
        print(-1)
        sys.exit()

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy

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

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

data = warshall_floyd(dis)
flag = True
for i in range(n):
    for j in range(i + 1, n):
        if data[i][j] < a[i][j]:
            flag = False
            break
    if flag == False:
        break
if flag == False:
    print(-1)
else:
    count = 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 data[i][k] + data[k][j] == data[i][j]:
                    break
            else:
                count += data[i][j]
    print(count)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [[int(x) for x in input().split()] for _ in range(N)]
Need = [True] *(N*N)
ans = 0
for k in range(N):
    for i in range(N):
        if i == k: continue
        for j in range(i+1,N):
            if j == k: continue
            Aikj = A[i][k] + A[k][j]
            if A[i][j] > Aikj:
                ans = -1
            if A[i][j] == Aikj:
                Need[i*N+j] = False

if ans != -1:
    for i in range(N):
        for j in range(i+1,N):
            if Need[i*N+j]:
                ans += A[i][j]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [[int(x) for x in input().split()] for _ in range(N)]
Need = [[True]*N for _ in range(N)]
ans = 0
for k in range(N):
    for i in range(N):
        if i == k: continue
        for j in range(i+1,N):
            if j == k: continue
            Aikj = A[i][k] + A[k][j]
            if A[i][j] > Aikj:
                ans = -1
            if A[i][j] == Aikj:
                Need[i][j] = False

if ans != -1:
    for i in range(N):
        for j in range(i+1,N):
            if Need[i][j]:
                ans += A[i][j]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
N = int(input())
A = [[int(x) for x in input().split()] for _ in range(N)]
road_length = sum(sum(a) for a in A) //2

for k in range(N):
    for i in range(N):
        for j in range(i+1,N):
            if A[i][j] > A[i][k] + A[k][j]:
                print(-1)
                sys.exit()
            if A[i][j] == A[i][k] + A[k][j] and i != k and j != k:
                road_length -= A[i][j]
ans = road_length
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    A = [list(map(int, input().split())) for _ in range(n)]
    flg = [[True] * n for _ in range(n)]

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

    res = 0
    for i in range(n):
        for j in range(n):
            if flg[i][j]:
                res += A[i][j]

    print(res // 2)


if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

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

arr = np.array(a)
csr = csr_matrix(arr)
f = floyd_warshall(csr)

if np.sum(arr == f) != n**2:
    print(-1)
    exit()
total = np.sum(arr) // 2
for i in range(n-1):
    for j in range(i+1,n):
        for x in range(n):
            if x == i or x == j:
                continue
            if a[i][j] == a[i][x] + a[j][x]:
                total -= a[i][j]
print(total)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import heapq
mod=10**9+7
inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict, OrderedDict
#すべてのkeyが用意されてる defaultdict(int)で初期化
#順序を保ったdict
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  #変換後の末尾桁を0や0.01で指定
  #Decimal((str(0.5)).quantize(Decimal('0'), rounding=ROUND_HALF_UP))
from functools import lru_cache
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########
n=int(input())
A=[]
# ans=0
for i in range(n):
    a=list(map(int,input().split()))
    A.append(a)
    # ans+=sum(a)

#ans//=2
miti=A[:]
for k in range(n):
    for i in range(k):
        for j in range(i):
            q=miti[i][j]
            w=miti[j][k]
            e=miti[k][i]
            q,w,e=sorted([[q,i,j],[w,j,k],[e,k,i]])
            if e[0]==inf:
                continue
            if sum([q[0],w[0],e[0]])==e[0]*2:
                miti[e[1]][e[2]]=inf
                miti[e[2]][e[1]]=inf
            elif q[0]+w[0]<e[0]:
                print(-1);exit()
ans=0
for i in range(n):
    for j in range(n):
        if miti[i][j]!=inf:
            ans+=miti[i][j]

print(ans//2)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
import copy
def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j]=min(d[i][j],d[i][k]+d[k][j])
    return d

  
cost=[list(map(int,input().split())) for i in range(N)]
D=copy.deepcopy(cost)
E=warshall_floyd(cost)
      
if D!=E: 
  print(-1)
  exit()
D=cost
for k in range(N):
  for i in range(N):
    for j in range(N):
      a,b,c=D[i][j],D[j][k],D[i][k]
      if a!=0 and b!=0 and c!=0:
        if D[i][j]==D[i][k]+D[k][j]:
          D[i][j]=0       
ans=0
for i in range(N):
  ans+=sum(D[i]) 
print(ans//2)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
import copy
def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j]=min(d[i][j],d[i][k]+d[k][j])
    return d

  
cost=[list(map(int,input().split())) for i in range(N)]
D=copy.deepcopy(cost)
E=warshall_floyd(cost)
      
if D!=E: 
  print(-1)
  exit()
D=cost
for i in range(N):
  for j in range(N):
    for k in range(N):
      a,b,c=cost[i][j],cost[j][k],cost[i][k]
      if a+b==c and a!=0 and b!=0 and c!=0:
        D[i][k]=0       
ans=0
for i in range(N):
  ans+=sum(D[i]) 
print(ans//2)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())

def dijkstra(s,n,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
               
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d
  
cost=[list(map(int, input().split())) for i in range(N)]
ans=0
for i in range(N):
  for j in range(N):
    if i<j:
      d=dijkstra(i,N,cost)
      if d[j]!=cost[i][j]:
        print(-1)
        exit()
D=cost
for i in range(N):
  for j in range(N):
    for k in range(N):
      a,b,c=cost[i][j],cost[j][k],cost[i][k]
      if a+b==c and a!=0 and b!=0 and c!=0:
        D[i][k]=0       
ans=0
for i in range(N):
  ans+=sum(D[i]) 
print(ans//2)

Submission status: Time Limit Exceeded

Solution code:
import copy


def warshalFloyd(n):
    G=[list(map(int,input().split())) for _ in range(n)]
    D=copy.deepcopy(G)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                G[i][j]=min(G[i][j],G[i][k]+G[k][j])

    return G if G==D else -1


n=int(input())
Graph=warshalFloyd(n)
if Graph==-1:print(-1);exit()

for k in range(n):
    for i in range(n):
        for j in range(n):
            if Graph[i][j]!=0 and Graph[i][k]!=0 and Graph[k][j]!=0:
                if Graph[i][j]==Graph[i][k]+Graph[k][j]:
                    Graph[i][j]=0

ans=0
for i in range(n):
    ans +=sum(Graph[i])
print(ans//2)

Submission status: Time Limit Exceeded

Solution code:

N=int(input())

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


check=[[0]*N for i in range(N)]

ans=0   
for i in range(N):
    for j in range(N):
        for k in range(N):
            if ans==-1:
                break
            if arr[j][k]>arr[j][i]+arr[i][k]:
                ans=-1
            elif arr[j][k]==arr[j][i]+arr[i][k] and arr[j][i]>0 and arr[i][k]>0:
                check[j][k]=1
if ans!=-1:
    for i in range(N):
        for j in range(i):
            if check[i][j]==0:
                ans+=arr[i][j]


print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    grid = [list(map(int, input().split())) for _ in range(n)]
    flg = [[True] * n for _ in range(n)]

    for k in range(n):
        for i in range(n):
            for j in range(n):
                if grid[i][k] + grid[k][j] < grid[i][j]:
                    print(-1)
                    exit()
                elif grid[i][k] + grid[k][j] == grid[i][j] and i != k and j != k:
                    flg[i][j] = False

    res = 0
    for i in range(n):
        for j in range(n):
            if flg[i][j]:
                res += grid[i][j]
    print(res // 2)


if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys

icase=0
if icase==0:
    n=int(input())
    a=[[0]*n for i in range(n)]
    for i in range(n):
        a[i]=list(map(int,input().split()))
elif icase==1:
    n=3
    a=[[0, 1, 3], [1, 0, 2], [3, 2, 0]]
#    a=[[0, 1, 3], [1, 0, 1], [3, 1, 0]]

dp=[[0]*n for i in range(n)]
for i in range(n):
    dp[i]=a[i].copy()
    
c=[[0]*n for i in range(n)]

for k in range(n):
    for i in range(n):
        for j in range(n):
            if dp[i][j]>dp[i][k]+dp[k][j]:
                dp[i][j]=dp[i][k]+dp[k][j]
            if dp[i][j]==dp[i][k]+dp[k][j] and i!=k and j!=k:
                c[i][j]=1                
                

icnt=0
for i in range(0,n-1):
    for j in range(i+1,n):
        if a[i][j]!=dp[i][j]:
            print(-1)
            sys.exit()
        elif c[i][j]==0:
            icnt+=dp[i][j]
print(icnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
from copy import deepcopy
import numpy as np
readline=sys.stdin.readline
read=sys.stdin.read

def main():
    n=int(readline())
    a=np.array([list(map(int,l.split())) for l in read().splitlines()])
    cost=deepcopy(a)
    for k in range(n):
        arr=np.stack([cost,[cost[k]]+np.transpose([cost[k]])])
        cost=np.amin(arr,axis=0)
    cost2=deepcopy(a)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                cost2[i][j]=min(cost2[i][j],cost2[i][k]+cost2[k][j])
    f=np.sum(cost<a)
    if f:
        print(-1)
        return
    filt=np.sum([([cost[k]]+np.transpose([cost[k]]))==cost for k in range(n)],axis=0)==2
    print(np.sum(a[filt])//2)

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

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

    ans = 0
    for i in range(n):
        for j in range(n):
            if i == j:
                continue
            flag = True
            for k in range(n):
                if k == i or k == j:
                    continue
                if d[i][j] > d[i][k]+d[k][j]:
                    print(-1)
                    exit()
                elif d[i][j] == d[i][k]+d[k][j]:
                    flag = False
                else:
                    pass
            if flag:
                ans += d[i][j]
    #print(ans)
    print(ans//2)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import heapq

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

ans = 0
for i in range(N):
    for j in range(N):
        via_k = float('inf')
        for k in range(N):
            if A[i][j] > A[i][k] + A[k][j]:
                print(-1)
                exit()
            if k == i or k == j:
                continue
            via_k = min(via_k, A[i][k] + A[k][j])
        if i <= j:
            continue
        if A[i][j] < via_k:
            ans += A[i][j]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
N = int(input())

A = []
for _ in range(N):
  A.append(list(map(int, input().split())))
  
G = csgraph_from_dense(A)
D = floyd_warshall(G)

ans = 0
for i in range(N):
  for j in range(i+1,N):
    if D[i][j] < A[i][j]:
      print(-1)
      exit(0)
      
for i in range(N):
  for j in range(i+1,N):
    flg = True
    for k in range(N):
      if i == k or j == k:
        continue
      if D[i][j] == D[i][k] + D[k][j]:
        flg = False
        break
    if flg:
      ans += D[i][j]
      
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
N = int(input())

A = []
for _ in range(N):
  A.append(list(map(int, input().split())))
  
G = csgraph_from_dense(A)
D = floyd_warshall(G)

ans = 0
for i in range(N):
  for j in range(i+1,N):
    if D[i][j] < A[i][j]:
      print(-1)
      exit(0)
      
for i in range(N):
  for j in range(i+1,N):
    flg = True
    for k in range(N):
      if i == k or j == k:
        continue
      if D[i][j] == D[i][k] + D[k][j]:
        flg = False
    if flg:
      ans += D[i][j]
      
print(int(ans))

Submission status: Time Limit Exceeded

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

import copy
d = copy.deepcopy(As)
for i in range(n):
    for k in range(n):
        for j in range(n):
            d[i][j] = min(d[i][j], d[i][k]+d[k][j])
cnt = 0
routes = set()
for i in range(n):
    for j in range(i+1,n):
        routes.add(i*n+j)


for i in range(n):
    for k in range(n):
        for j in range(n):
            x = (i-j)*(j-k)*(k-i)
            # かぶりを消す
            if d[i][j] == d[i][k]+d[k][j] and x != 0:
                try:
                    routes.remove(i*n+j)
                except:
                    pass
cnt = 0
for r in routes:
    i,j = divmod(r,n)
    cnt += d[i][j]

if As != d:
    print(-1)
else:
    print(cnt)