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
import math
import fractions
import itertools
from collections import deque
import copy
import heapq
import bisect
from scipy.sparse.csgraph import shortest_path
import numpy as np

MOD = float('inf')
INF = 10 ** 18 + 7
input = lambda: sys.stdin.readline().strip()

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

result = shortest_path(np.array(A))
ans = 0
for i in range(N):
    for l in range(N):
        if result[i][l] != A[i][l]:
            print(-1)
            sys.exit()
        ans += A[i][l]
        if A[i][l] == 0:
            A[i][l] = INF

ans /= 2
for i in range(N - 1):
    for l in range(i + 1, N):
        for k in range(N):
            if A[i][l] == A[i][k] + A[k][l]:
                ans -= A[i][l]
                break
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import fractions
import itertools
from collections import deque
import copy
import heapq
import bisect
from scipy.sparse.csgraph import shortest_path
import numpy as np

MOD = float('inf')
INF = 10 ** 18 + 7
input = lambda: sys.stdin.readline().strip()

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

result, path = shortest_path(np.array(A), return_predecessors=True)
ans = 0
for i in range(N):
    for l in range(N):
        if result[i][l] != A[i][l]:
            print(-1)
            sys.exit()
        ans += A[i][l]
        if A[i][l] == 0:
            A[i][l] = INF

ans /= 2
for i in range(N - 1):
    for l in range(i + 1, N):
        for k in range(N):
            if A[i][l] == A[i][k] + A[k][l]:
                ans -= A[i][l]
                break
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall


def solve():
    N = int(input())
    A = np.array([input().split() for _ in range(N)], dtype=np.int64).reshape(N, N)
    
    B = floyd_warshall(csr_matrix(A), directed=False)
    
    if np.any(B < A):
        print(-1)
        exit()
    
    np.fill_diagonal(B, np.inf)
    for i in range(N - 1):
        for j in range(i + 1, N):
            for k in range(N):
                if B[i][j] == B[i][k] + B[k][j]:
                    A[i][j] = A[j][i] = 0
    print(np.sum(A) // 2)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall


def solve():
    N = int(input())
    A = np.array([input().split() for _ in range(N)], dtype=np.int64).reshape(N, N)
    
    B = floyd_warshall(csr_matrix(A))
    
    if np.any(B < A):
        print(-1)
        exit()
    
    np.fill_diagonal(B, np.inf)
    for i in range(N - 1):
        for j in range(i + 1, N):
            for k in range(N):
                if B[i][j] == B[i][k] + B[k][j]:
                    A[i][j] = A[j][i] = 0
    print(np.sum(A) // 2)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N = I()
    G = []
    dp = []
    for _ in range(N):
        a = LI()
        G.append(a)
        dp.append(a)

    for i in range(N):
        for j in range(N):
            for k in range(N):
                if G[i][j] > G[i][k] + G[k][j]:
                    print(-1)
                    return 

    for k in range(N):
        for i in range(N):
            for j in range(N):
                if j == k or k == i:
                    continue
                if dp[i][k] == inf or dp[i][j] == inf or dp[j][k] == inf:
                    continue
                if G[i][j] == G[i][k] + G[k][j]:
                    # i->jは要らない
                    dp[i][j] = inf
    cnt = 0
    for i in range(N):
        for j in range(N):
            if dp[i][j] < inf:
                cnt += dp[i][j]
    print(cnt // 2)
main()

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N = I()
    G = []
    for _ in range(N):
        a = LI()
        G.append(a)
    dp = copy.deepcopy(G)

    for i in range(N):
        for j in range(N):
            for k in range(N):
                if G[i][j] > G[i][k] + G[k][j]:
                    print(-1)
                    return 

    for k in range(N):
        for i in range(N):
            for j in range(N):
                if j == k or k == i:
                    continue
                if dp[i][k] == inf or dp[i][j] == inf or dp[j][k] == inf:
                    continue
                if G[i][j] == G[i][k] + G[k][j]:
                    # i->jは要らない
                    dp[i][j] = inf
    cnt = 0
    for i in range(N):
        for j in range(N):
            if dp[i][j] < inf:
                cnt += dp[i][j]
    print(cnt // 2)
main()

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix

import numpy as np

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

a = np.array(a)

g = csr_matrix(a)
dist = floyd_warshall(g)

bl = dist == a

if bl.all():
    sm = a.sum()
    for u in range(n):
        for v in range(n):
            if v == u:
                continue
            for w in range(n):
                if w == u or w == v:
                    continue
                if dist[u][v] == dist[u][w] + dist[w][v]:
                    sm -= dist[u][v]

    ans = int(sm) // 2
    print(ans)

else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline


N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
dist = [[float('inf')] * N for _ in range(N)]
for i in range(N):
    dist[i][i] = 0
edges = []
for i in range(N-1):
    for j in range(i+1, N):
        edges.append((A[i][j], i, j))
edges.sort()
edges = deque(edges)
ans = 0
while edges:
    d, u, v = edges.popleft()
    if d > dist[u][v]:
        ans = -1
        break
    if d < dist[u][v]:
        ans += d
        for i in range(N-1):
            for j in range(i+1, N):
                ndist = min(dist[i][j], dist[i][u] + d + dist[v][j], dist[i][v] + d + dist[u][j])
                dist[i][j] = dist[j][i] = ndist
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline


N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
dist = [[float('inf')] * N for _ in range(N)]
for i in range(N):
    dist[i][i] = 0
edges = []
for i in range(N-1):
    for j in range(i+1, N):
        edges.append((A[i][j], i, j))
edges.sort(reverse=True)
ans = 0
while edges:
    d, u, v = edges.pop()
    if d > dist[u][v]:
        ans = -1
        break
    if d < dist[u][v]:
        ans += d
        for i in range(N-1):
            for j in range(i+1, N):
                ndist = min(dist[i][j], dist[i][u] + d + dist[v][j], dist[i][v] + d + dist[u][j])
                dist[i][j] = dist[j][i] = ndist
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
import sys
input = sys.stdin.readline


def dijkstra(edges, size, source):
    distance = [float('inf')] * size
    distance[source] = 0
    visited = [False] * size
    pq = []
    heappush(pq, (0, source))
    while pq:
        dist_v, v = heappop(pq)
        visited[v] = True
        for u, weight in edges[v]:
            if not visited[u]:
                new_dist = dist_v + weight
                if distance[u] > new_dist:
                    distance[u] = new_dist
                    heappush(pq, (new_dist, u))
    return distance


N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
G = [[] for _ in range(N)]
edges = []
for i in range(N-1):
    for j in range(i+1, N):
        edges.append((A[i][j], i, j))
edges.sort(reverse=True)
ans = 0
while edges:
    d, u, v = edges.pop()
    dist = dijkstra(G, N, u)
    if d > dist[v]:
        ans = -1
        break
    if d < dist[v]:
        ans += d
        G[u].append((v, d))
        G[v].append((u, d))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy

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

Check = copy.deepcopy(A)

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

Graph_exist = True
for i in range(n):
    for j in range(n):
        if A[i][j] != Check[i][j]:
            Graph_exist = False

Road_exist = [[True for _ in range(n)] for _ in range(n)]
for i in range(n):
    Road_exist[i][i] = False

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 A[i][j] == (A[i][k] + A[k][j]):
                Road_exist[i][j] = False

ans = 0
for i in range(n):
    for j in range(i+1,n):
        if Road_exist[i][j] == True:
            ans += A[i][j]

if Graph_exist == False:
    ans = -1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
# 辺の必要性
f = [[True] * n for _ in range(n)]
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]:
                print(-1)
                exit()
            elif a[i][k] + a[k][j] == a[i][j] and i != k and k != j:
                f[i][j] = False

ans = 0
for i in range(n):
    for j in range(n):
        if f[i][j]:
            ans += a[i][j]
ans //= 2
print(ans)

Submission status: Time Limit Exceeded

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

def warshal_floyd(d):
  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 copy
B = copy.deepcopy(A)
B = warshal_floyd(B)

ans = 0
for i in range(n):
    for j in range(n):
        if B[i][j] < A[i][j]:
            print(-1)
            exit()
        else:
            for k in range(n):
                if k == i or k == j:
                    continue
                if B[i][j] == B[i][k] + B[k][j]:
                    break
            else:
                ans += A[i][j]
ans //=2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from copy import deepcopy

def warshall_floyd(n,a):
    d = deepcopy(a)
    is_via = np.full((n,n), False)
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if i == j:
                    continue
                # 経由する場合
                if (d[i][k] != 0 and d[k][j] != 0) and (d[i][j] == d[i][k] + d[k][j]):
                    is_via[i][j] = True
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    flag = np.all(a == d)
    return flag, is_via

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

flag, is_via = warshall_floyd(N,A)

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env pypy3
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
import copy

################
class UnionFind():
    """
    parents : 親要素(findしない場合は根ではないことの注意)，根の場合は"-(要素数）"
    find(x):要素xの属するグループの根を返す
    size(x):要素xの属するグループの要素数を返す
    same(x,y):x,yが同じグループに属しているか返す
    members(x):要素xが属するグループに属する要素をリストで返す
    roots:全ての根の要素を返す
    group_count():グループの数を返す
    all_group_members():{根要素：[そのグループに含まれる要素のリスト]}の辞書を返す
    """
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
    
################
##########################################
import heapq
class Dijkstra():
    """
    ・有向 / 無向は問わない(無向の場合は，逆向きの辺もたす)
    ・負のコストがない場合のみ
    ・計算量はO(E log|V|)　
    ・heapを使うことで頂点を走査する必要がなくなる（代わりに，距離更新したものは確定でなくともqueに入れておく）
    """
    
    #最短のpathをたす
    
    
    class Edge():
        #重み付き有向辺
        
        def __init__(self, _to, _cost):
            self.to =_to
            self.cost = _cost
    
    def __init__(self, V):
        #引数Vは頂点数
        self.G = [[] for _ in range(V)] #隣接リストG[u][i]が頂点uのi番目の辺
        self. _E = 0 #辺の数
        self._V = V #頂点数
    
    #proparty - 辺の数
    def E(self):
        return self._E
    
    #proparty - 頂点数
    def V(self):
        return self._V
    
    def add(self, _from, _to, _cost):
        #2頂点と辺のコストを追加
        self.G[_from].append(self.Edge(_to,_cost))
        self._E +=1
        
    def add2(self, _from, _to, _cost):
        #2頂点と辺のコスト（無向）を追加
        self.G[_from].append(self.Edge(_to, _cost))
        self.G[_to].append(self.Edge(_from, _cost))
        self._E +=1
        
    def shortest_path(self,s,g):
        #始点sから頂点iまでの最短経路長のリストを返す
        
        que = [] #priority queue
        d = [float("inf")] * self.V()
        prev = [None]*self.V() #prev[j]は，sからjへ最短経路で行くときのjの一つ前の場所
        d[s] = 0
        heapq.heappush(que,(0,s)) #始点の距離と頂点番号をヒープに追加
        
        while len(que)!=0:
            #キューに格納されてある中で一番コストが小さい頂点を取り出す
            cost,v = heapq.heappop(que)
            
            #キューに格納された最短経路長候補がdの距離よりも大きい場合に処理をスキップ
            if d[v] < cost:
                continue
                
            #頂点vに隣接する各頂点iに対して，vを経由した場合の距離を計算して，これがd[i]よりも小さい場合に更新
            for i in range(len(self.G[v])):
                e = self.G[v][i] #vのi個目の隣接辺
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost #更新
                    prev[e.to] = v
                    heapq.heappush(que,(d[e.to],e.to)) #queに新たな最短経路長候補を追加
        
        #sからgまでの最短経路
        path = []
        pos = g #今いる場所，ゴールで初期化
        for _ in range(self.V()+1):
            path.append(pos)
            if pos == s:
                break
            #print("pos:",format(pos))
            pos = prev[pos]
        path.reverse()
        #print(path)
                    
        return d[g]#,path
########################

def main():
    mod=10**9+7
    N=I()
    adj=[[] for _ in range(N)]
    A=[[]for _ in range(N)]
    for i in range(N):
        A[i]=LI()
        
        
    def warshall_floyd(D):
        d=copy.deepcopy(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
    
    mA=[]
    for i in range(N):
        for j in range(i+1,N):
            a=[A[i][j],i,j]
            mA.append(a)
            
    mA.sort()
    g_cnt=N
    ans=0
    
    if A==warshall_floyd(A):
        uf=UnionFind(N)
        djk = Dijkstra(N)
        for i in range(len(mA)):
            if g_cnt==1:#とりあえず連結になるまでは新しい辺を足す
                d_ij= djk.shortest_path(mA[i][1],mA[i][2])
                if d_ij==A[mA[i][1]][mA[i][2]]:#最小を更新できるなら辺をたす
                    continue
                else:
                     djk.add2(mA[i][1],mA[i][2],mA[i][0])
                     ans+=mA[i][0]
            else:
                uf.union(mA[i][1],mA[i][2])
                g_cnt = uf.group_count()
                djk.add2(mA[i][1],mA[i][2],mA[i][0])
                ans+=mA[i][0]
                    
                
        
        
        
    else:
        ans=-1





    print(ans)
        
    

main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from heapq import heappush, heappop
    from operator import itemgetter

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

    for i in range(n):
        for j in range(n):
            if a[i][j] != min(a[i][k] + a[k][j] for k in range(n)):
                print(-1)
                return

    h = []
    for r, row in enumerate(a):
        for c, cell in enumerate(row):
            if r == c: break
            bit = (1 << r) | (1 << c)
            heappush(h, (cell, bit))  # dist,bit

    pathes = set()
    while h:
        dist, bit = heappop(h)

        is_path = True
        for d1, p1 in pathes:
            for d2, p2 in pathes:
                xor = p1 ^ p2
                if (xor == bit) and (dist >= d1 + d2):
                    is_path = False
                    break
            if not is_path:
                break

        if is_path:
            pathes.add((dist, bit))

    print(sum(map(itemgetter(0), pathes)))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = [list(map(int, input().split())) for _ in range(n)]
ans = 0
for s in range(n):
  for g in range(n):
    b = 0
    for via in range(n):
      if A[s][g] > A[s][via] + A[via][g]:
        print(-1)
        exit()
      if A[s][g] == A[s][via] + A[via][g]:
        b += 1
    if b == 2:
      ans += A[s][g]
print(ans//2)

Submission status: Time Limit Exceeded

Solution code:
#14:05
n = int(input())
krus = []
raw = []
for i in range(n):
  tmp = list(map(int,input().split()))
  raw.append(tmp)
  for j in range(n):
    krus.append([tmp[j],i,j])
krus.sort()
#print(krus)
ans = 0
inf = 10 ** 18
wf = [[inf for _ in range(n)] for _ in range(n)]
for x in krus:
  d,i,j = x
  if wf[i][j] < d:
    print(-1)
    exit()
  elif wf[i][j] == d:
    continue
  wf[i][j] = d
  ans += d
  for a in range(n):
    for b in range(n):
      wf[a][b] = min(wf[a][b], wf[a][i] + d + wf[j][b])
      wf[b][a] = min(wf[b][a], wf[b][i] + d + wf[j][a])
  #print(wf)
  #print(x)
print(ans//2)

Submission status: Time Limit Exceeded

Solution code:
#14:05
n = int(input())
krus = []
wf = []
for i in range(n):
  tmp = list(map(int,input().split()))
  wf.append(tmp)
  for j in range(n):
    krus.append([tmp[j],i,j])
krus.sort()
#print(krus)
ans = 0
for k in range(n):
  for i in range(n):
    for j in range(n):
      if wf[i][j] > wf[i][k] + wf[k][j]:
        print(-1)
        exit()
inf = 10 ** 3
wf = [[inf for _ in range(n)] for _ in range(n)]
for x in krus:
  d,i,j = x
  if wf[i][j] == d:
    continue
  wf[i][j] = d
  ans += d
  for a in range(n):
    for b in range(n):
      wf[a][b] = min(wf[a][b], wf[a][i] + d + wf[j][b])
      wf[b][a] = min(wf[b][a], wf[b][i] + d + wf[j][a])
  #print(wf)
  #print(x)
print(ans//2)

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import floyd_warshall
N = int(input())
dic = [0]*N
for i in range(N):
  dic[i] = [int(c) for c in input().split()]

d = floyd_warshall(dic)
ans = 0
for i in range(N-1):
  for j in range(i+1,N):
    if d[i][j] < dic[i][j]:
      print(-1)
      import sys
      sys.exit()
    elif dic[i][j] == d[i][j]:
      flag = False
      for k in range(N):
        if k==i or k==j:
          continue
        if d[i][j] == d[i][k]+d[k][j]:
          flag = True
          break
      if flag:
        continue
    ans += dic[i][j]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

from scipy.sparse.csgraph import shortest_path,floyd_warshall
from scipy.sparse import csr_matrix
lc = csr_matrix(lst1)
st = shortest_path(lc,method="FW")
ans = 0
for i in range(n):
    for j in range(i+1,n):
        if lst1[i][j] > st[i][j]:
            print(-1)
            exit()
        elif lst1[i][j]==st[i][j]:
            #他に最短距離がある場合はcontinue
            res = [0]*n
            for k in range(n):
                res[k] += lst1[i][k] + lst1[j][k]
            res[i] = -1
            res[j] = -1
            if any([res[k]==lst1[i][j] for k in range(n)]):
                continue
            else:
                ans += lst1[i][j]
        else:
            ans += lst1[i][j]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def warshall(d, n):
    e = copy.deepcopy(d)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                # print(d[i][k], d[k][j], d[i][j])
                if i == k or k == j:
                    continue
                if d[i][k] + d[k][j] < d[i][j]:
                    return []
                if d[i][k] + d[k][j] == d[i][j]:
                    # print(d[i][k], d[k][j], d[i][j], i,j,k)
                    e[i][j] = 0
                    e[j][i] = 0
    return e
    
import copy
n = int(input())
edges = []

graph = [list(map(int, input().split())) for i in range(n)]
e = warshall(graph, n)
if e == []:
    print(-1)
    exit()
# print(e)
edge_list = [[] for _ in range(n)]
ans = 0
for i in range(n):
    for j in range(n):
        if e[i][j] > 0:
            edge_list[i].append((e[i][j], j))
        if j > i and e[i][j]:
            ans += e[i][j]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop

def prim_heap(edges, n):
    visited = [False] * n
    heap = []
    start = 0
    for e in edges[start]:
        heappush(heap, e)
    visited[start] = True

    res = 0
    while heap:
        cost, v = heappop(heap)
        if visited[v]:
            continue
        visited[v] = True
        res += cost
        for c,u in edges[v]:
            if visited[u]:
                continue
            heappush(heap, (c,u))
    # print(visited)
    return res if sum(visited) == n else -1

inf = float('INF')
def warshall(d, n):
    e = copy.deepcopy(d)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                # print(d[i][k], d[k][j], d[i][j])
                if i == k or k == j:
                    continue
                if d[i][k] + d[k][j] < d[i][j]:
                    e[i][k] = 0
                    e[k][j] = 0
                    e[k][i] = 0
                    e[j][k] = 0
                if d[i][k] + d[k][j] == d[i][j]:
                    # print(d[i][k], d[k][j], d[i][j], i,j,k)
                    e[i][j] = 0
                    e[j][i] = 0
    return e
    
import copy
n = int(input())
edges = []

graph = [list(map(int, input().split())) for i in range(n)]
e = warshall(graph, n)
# print(e)
edge_list = [[] for _ in range(n)]
ans = 0
for i in range(n):
    for j in range(n):
        if e[i][j] > 0:
            edge_list[i].append((e[i][j], j))
        if j > i and e[i][j]:
            ans += e[i][j]

print(ans if prim_heap(edge_list, n) != -1 else -1)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.buffer.readline
import numpy as np

def main():
    N = int(input())
    edge = np.array([list(map(int,input().split())) for _ in range(N)])
    use = np.array([[True for _ in range(N)] for _ in range(N)])
    count = 0
    for k in range(N):
        for i in range(N):
            if k == i:
                continue
            for j in range(N):
                if (k == j or i == j):
                    continue
                if edge[i][j] == edge[i][k] + edge[k][j]:
                    use[i][j] = False
                elif edge[i][j] > edge[i][k] + edge[k][j]:
                    print(-1)
                    exit()
    
    ans = 0
    for i in range(N):
        ans += sum(edge[i,i:]*use[i,i:])
        
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.buffer.readline


def main():
    N = int(input())
    edge = [list(map(int,input().split())) for _ in range(N)]
    use = [[True for _ in range(N)] for _ in range(N)]
    count = 0
    for k in range(N):
        for i in range(N):
            if k == i:
                continue
            for j in range(N):
                if (k == j or i == j):
                    continue
                if edge[i][j] == edge[i][k] + edge[k][j]:
                    use[i][j] = False
                elif edge[i][j] > edge[i][k] + edge[k][j]:
                    print(-1)
                    exit()
    
    ans = 0
    for i in range(N):
        for j in range(i,N):
            ans += (edge[i][j]*use[i][j])
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
ans = sum(A[i][j] for i in range(N) for j in range(i+1,N))
for i in range(N-1):
    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]:
                print(-1)
                exit()
            if A[i][j] == A[i][k]+A[k][j]:
                ans -= A[i][j]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
if all(A[i][j] <= A[i][k]+A[k][j] for k in range(N) for i in range(N) for j in range(N)):
    ans = sum(A[i][j] for i in range(N) for j in range(i+1,N))
    for i in range(N-1):
        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]:
                    ans -= A[i][j]
    print(ans)
else:
    print(-1)

Submission status: Time Limit Exceeded

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

length = 0
for i in range(n) :
    for j in range(n):
        route = 10000000000
        for k in range(n):
            if k == i or k == j : continue
            route = min(route, a[i][k] + a[k][j] ) #< a[i][j]
            if route < a[i][j]:
                print(-1)
                exit() 
        if route > a[i][j] :
            length +=  a[i][j]
print(int(length/2))

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import floyd_warshall
N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]

# for a in A:
#     print(a)
# 余分な辺を消去する問題
graph = floyd_warshall(A)
for i in range(N):
    for j in range(N):
        if A[i][j] != graph[i][j]:
            print(-1)
            exit()

# 最短経路であることは分かった
flag = [[True]*N for _ in range(N)]
for k in range(N):
    for i in range(N):
        for j in range(N):
            if graph[i][j] == graph[i][k] + graph[k][j] and i != k and k != j:
                flag[i][j] = False

ans = 0
for i in range(N):
    for j in range(i+1, N):
        if flag[i][j] == True:
            ans += graph[i][j]
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import permutations, combinations
  
def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [[int(a) for a in input().split()] for _ in range(N)]

    length = 0
    possible = True
    for a, b in combinations(range(N), 2):
        Lab = A[a][b]
        create_pass = True
        for k in range(N):
            if k != a and k != b:
                if Lab >  A[a][k] + A[k][b]:
                    possible = False
                    break
                elif Lab ==  A[a][k] + A[k][b]:
                    create_pass = False
                    break
        if create_pass: length += Lab
        if not possible:
            print(-1)
            break
    else: print(length)
    
    return 0
  
if __name__ == "__main__":
    solve()