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: Accepted

Solution code:
N=int(input())
A=[list(map(int,input().split())) for i in range(N)]
res=0
flag=[[False]*N for i in range(N)]
for k in range(N):
    for i in range(N):
        for j in range(N):
            if A[i][j]>A[i][k]+A[k][j]:
                print(-1)
                exit()
            elif k!=i and k!=j and A[i][j]==A[i][k]+A[k][j] and not flag[i][j] and not flag[j][i]:
                flag[i][j]=True
                flag[j][i]=True
                res-=A[i][j]
ans=sum(sum(A[i]) for i in range(N))//2+res

print(ans)

Submission status: Accepted

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

# dは隣接頂点間のコスト、Nは頂点の個数
def warshall_floyd(d):
    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)
                    sys.exit()
                elif d[i][j] == d[i][k] + d[k][j] and k != i and k != j:
                    delete[i][j] = True
                    delete[j][i] = True                 
    return d

N = int(input())
inf = float("inf")
delete = [[False]*N for _ in range(N)]
# input

# d[i][v]:辺(i, v)間のコスト、存在しなければinf
d = [[int(x) for x in input().split()] for _ in range(N)]
d = warshall_floyd(d)

ans = 0

for i in range(N):
    for j in range(i + 1, N):
        if delete[i][j]:
            continue
        ans += d[i][j]
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
n = int(input())
a = [list(map(int,input().split())) for i in range(n)]
dic = defaultdict(lambda :0)
cut = 0
for k in range(n):
    for i in range(n):
        for j in range(n):
            if i == j:continue
            temp = a[i][k] + a[k][j]

            if a[i][j] > temp:
                print(-1)
                exit()

            if temp == a[i][j] and i < j and k != i and k != j:
                if not dic[(i, j)]:
                    cut += a[i][j]
                    dic[(i, j)] = 1
rec = 0
for i in range(n):
    for j in range(n):
        if i < j :rec += a[i][j]

print(rec - cut)

Submission status: Accepted

Solution code:
import numpy as np
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    N = int(readline())
    A = np.array(read().split(), dtype=np.int64).reshape(N,N)

    INF = 10**15
    ans = 0
    for i in range(N):
        B = A[i,:] + A
        np.fill_diagonal(B, INF)
        B[:,i] = INF
        C = B.min(axis=1)
        C[i] = 0

        if (C < A[i,:]).sum() > 0:
            print(-1)
            exit()
        else:
            index = C > A[i,:]
            ans += A[i, index].sum()

    print(ans // 2)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

def main():
    N = int(readline())
    A = [[int(i) for i in readline().split()] for _ in range(N)]

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


if __name__ == "__main__":
    main()

Submission status: Accepted

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

for i in range(N):
    for j in range(N):
        for k in range(N):
            dp[j][k] = min(dp[j][k], dp[j][i]+dp[i][k])
        

judge = origin_dp == dp

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

                if dp[j][k] == dp[j][i] + dp[i][k]:
                    dp[j][k] = 0
        
    for i in range(N):
        for j in range(i+1,N):
            ans += dp[i][j]

    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
n = int(input())

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

# d[i][j]は2頂点間i, j間の移動コストを格納, Vは頂点数
def warshall_floyd(d, V):
    for k in range(V):
        for i in range(V):
            for j in range(V):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])

    return d  # d[i][j]に頂点i, j間の最短距離を格納
from copy import deepcopy
d = warshall_floyd(deepcopy(dl), n)

if d != dl:
    print(-1)
    exit()

ans = 0
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        flag = True
        for k in range(n):
            if i == k or k == j:
                continue
            if d[i][j] == d[i][k] + d[k][j]:
                flag = False
        if flag:
            ans += d[i][j]
print(ans//2)

Submission status: Accepted

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):
    for j in range(i,n):
        ans +=Graph[i][j]
print(ans)

Submission status: Accepted

Solution code:
import sys
import copy
import heapq
from collections import deque

# sys.setrecursionlimit(100001)
INF = sys.maxsize


# ===CODE===
def main():
    n = int(input())
    dist_mat = []
    for i in range(n):
        l = list(map(int, input().split()))
        dist_mat.append(l)

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

    ans = 0
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if i == j:
                    continue
                dist_mat_calc[i][j] = min(dist_mat_calc[i][j], dist_mat[i][k] + dist_mat[k][j])

    tmp = [[dist_mat_calc[j][i] if dist_mat_calc[j][i] != INF else 0 for i in range(n)] for j in range(n)]
    if tmp != dist_mat:
        print(-1)
        exit(0)

    ans = 0

    for i in range(n):
        for j in range(i, n):
            if i == j:
                continue
            tmp = min([x+y for (x,y) in zip(dist_mat_calc[i], dist_mat_calc[j])])
            if dist_mat_calc[i][j] < tmp:
                ans+=dist_mat_calc[i][j]

    print(ans)





if __name__ == '__main__':
    main()

Submission status: Accepted

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

for i in range(N):
    if A[i][i] != 0:
        print(-1)
        exit()
import copy
ca = copy.deepcopy(A)

for k in range(N):
    for i in range(N):
        for j in range(N):
            ca[i][j] = min(ca[i][j],ca[i][k] + ca[k][j])


## 各頂点間に最短距離通りの辺を引いた時に最短距離が更新されていたらそれはどうやったって構築できない
for i in range(N):
    for j in range(N):
        if A[i][j] != ca[i][j]:
            print(-1)
            exit()

ans = 0
for i in range(N):
    for j in range(N):
        need = True
        for k in range(N):
            if i != k and j != k and ca[i][k] + ca[k][j] == ca[i][j]: # ijのパスが無くても制約を満たせるならijのパスは消して良い
                need = False
        if need:
            ans += ca[i][j]
ans = ans//2 # 各パスを2回ずつ数えている
print(ans)

Submission status: Accepted

Solution code:
import copy
n = int(input())
inf = 10**18
g = [[]]
for i in range(n):
    g.append([0]+list(map(int, input().split())))

g2 = copy.deepcopy(g)
for k in range(1, n+1):
    for i in range(1, n+1):
        for j in range(1, n+1):
            if g[i][k] == 0 or g[k][j] == 0:
                continue
            if g[i][j] == g[i][k] + g[k][j]:
                g[i][j] = 0

ans = 0
for i in range(1, n+1):
    ans += sum(g[i])

for i in range(1, n+1):
    for j in range(1, n+1):
        if g[i][j] == 0:
            g[i][j] = inf
    g[i][i] = 0

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

if g != g2:
    ans = -1

print(ans//2)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    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][j]>A[i][k]+A[k][j]:
                    print(-1)
                    exit()
                elif i!=k and j!=k and A[i][j]==A[i][k]+A[k][j]:
                    f[i][j]=False
    ans=0
    for i in range(N):
        for j in range(N):
            ans+=A[i][j]*f[i][j]
    print(ans//2)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read
inp = sys.stdin.buffer.readline
def inpS(): return inp().rstrip().decode()
readlines = sys.stdin.buffer.readlines
MOD = 10**9+7
INF = 1<<60
# A：想定する最短距離と計算(WF)で算出した最短距離が合っているか判定
# A[i][j] > A[i][k] + A[k][j] : -1
# AとWFが合っていたら最短距離の和を出力
import numpy as np
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix

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

    csr = csr_matrix(np.array(A))
    wf =  floyd_warshall(csr, directed=False)
    for i in range(N):
        wf[i][i] = INF
        A[i][i] = INF
    ans = 0
    for i in range(N):
        for j in range(N):
            if A[i][j] != wf[i][j]:
                print(-1)
                return
            if wf[i][j] < np.min(wf[i] + wf[j]):
                ans += wf[i][j]
    print(int(ans//2))

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
MOD = 10**9 + 7

N = int(input())
INF = 10**10
cost = [[INF]*N for _ in range(N)]

for u in range(N):
    C = list(map(int, input().split()))
    for v in range(N):
        if u==v: # INFのままにする
            continue
        cost[u][v] = C[v]
 
ans = 0
for u in range(N):
    for v in range(u+1,N):
        mn = INF # u-w-vのような経路の中で最小の距離を求める
        for w in range(N):
            mn = min(mn, cost[u][w]+cost[w][v])    
        if (cost[u][v] > mn): # 与えられた行列が最短経路ではない
            print (-1)
            exit()
        elif (cost[u][v] < mn): # 等しくない場合はu-vを直接結ぶ橋が必要 
            ans += cost[u][v]                      
print (ans)

Submission status: Accepted

Solution code:
# solution

import io
import math
import scipy.sparse as s,numpy as n

f=n.loadtxt(open(0),skiprows=1)

g=s.csgraph.dijkstra(f)

h=n.where(g,g,1)

print(int(sum(t[j]*(t[j]<t+h[j]).all()for i,t in enumerate(h)for j in range(i)))*(f==g).all()or-1)

Submission status: Accepted

Solution code:
from copy import deepcopy
n = int(input())
INF = 10**12

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

B = [[1]*n for _ in range(n)]
G = deepcopy(A)

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])
      if not (i==j or j==k or k==i):
        if G[i][j] == G[i][k]+G[k][j]:
          B[i][j] = 0
      
if A==G:
  ans = 0
  for i in range(n):
    for j in range(i+1,n):      
      ans += G[i][j] * B[i][j]
  print(ans)
else:
  print(-1)

Submission status: Accepted

Solution code:
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):
        ok = True
        for k in range(N):
            if A[i][j] > A[i][k] + A[k][j]:
                print(-1)
                exit()
            if i != k and j != k:
                if A[i][j] == A[i][k] + A[k][j]:
                    ok = False
        if ok:
            ans += A[i][j]

print(ans//2)

Submission status: Accepted

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

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

class WarshallFloyd:
    def __init__(self,n):
        self.v = n
        self.d = [[1e100]*n for _ in range(n)]
        for i in range(n):
            self.d[i][i] = 0

    def path(self,x,y,c):
        if x == y:
            return False
        self.d[x][y] = c
        self.d[y][x] = c
        return True

    def build(self):
        for k in range(self.v):
            for i in range(self.v):
                for j in range(self.v):
                    self.d[i][j] = min(self.d[i][j], self.d[i][k] + self.d[k][j])

wf = WarshallFloyd(n)

for i in range(1,n):
    for j in range(i):
        wf.path(i,j,A[i][j])

wf.build()
ans = 0
for i in range(n-1):
    for j in range(i+1,n):
        if A[i][j] > wf.d[i][j]:
            print(-1)
            exit(0)
        flag = 1
        for k in range(n):
            if i != k != j:
                if wf.d[i][j] == wf.d[i][k] + wf.d[k][j]:
                    flag = 0
                    break
        if flag:
            ans += A[i][j]
print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc074/tasks/arc083_b

# 考えること
# 1, どうやったらu→vの最短経路を復元できるか？
# 2, そのような道路が存在しない場合とはどういうときか？

# 重要な考察
# 1, iを固定したとき、j=arg_j min D[i][j] はiと必ず隣接する
# 2, d(u,v)=d(u,i)+d(i,v) を満たすiは最短経路の中にある。


# minimum sppaning treeからスタートする発想は悪くなかったねぇ

# 解説見ました...

# 道路が存在しない場合の判別方法→隣接行列Aに対してワーシャルフロイドをして、隣接行列Bを作成
# B(u,v)<A(u,v)となるとき、理想の最短距離よりも短い最短距離が存在して矛盾が生じるので-1

# Aを全点間グラフとして、辺の削除を考える。
# あらゆる二点に関するminimumな経路は？u,i,vについて、d(u,v)<d(u,i)+d(i,v)ならば、辺を残さないと最小距離にならない.
# 逆にd(u,v)=d(u,i)+d(i,v)ならば、d(u,v)の方は取り除いても構わない  (d(u,v)>d(u,i)+d(i,v)の状況はワーシャルフロイドで取り除かれている)


import sys
read = sys.stdin.readline
ra = range
enu = enumerate


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


N = read_a_int()
A = read_matrix(N)
from itertools import combinations
edge_rm = set()
for u, v in combinations(range(N), 2):
    for i in range(N):
        if i == u or i == v:
            continue
        a = A[u][i]
        b = A[i][v]
        c = A[u][v]
        # print(a, b, c)
        if c == a + b:
            # print(u, i, v, a, b, c)
            edge_rm.add((u, v) if u < v else(v, u))
        elif c > a + b:
            print(-1)
            exit()
# print(edge_rm)
ans_sum = 0
for a in A:
    for aa in a:
        ans_sum += aa
ans_sum //= 2
for u, v in edge_rm:
    ans_sum -= A[u][v]
print(ans_sum)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

import numpy as np

n = int(readline())
graph = np.array([list(map(int, readline().split())) for _ in range(n)])
inf = 10 ** 10
ans = 0
for i in range(n):
    graph[i][i] = inf
for i in range(n):
    for j in range(i + 1, n):
        v = np.min(graph[i] + graph[j])
        if graph[i][j] > v:
            print(-1)
            exit()
        elif graph[i][j] < v:
            ans += graph[i][j]
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
import copy
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]

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

def warshall_floyd(d,d2):
    #d[i][j]: iからjへの最短距離

    for k in range(n):
        for i in range(n):
            for j in range(n):
                if i==k or j==k:
                    continue
                if d[i][j]>d[i][k] + d[k][j]:
                    print(-1)
                    quit()
                if d[i][j]==d[i][k] + d[k][j]:
                    d2[i][j]=1
                # d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d


d = [[float("inf") for i in range(n)] for i in range(n)] 
#d[u][v] : 辺uvのコスト(存在しないときはinf)
cnt=0
for i in range(n):
    for j in range(n):
        d[i][j]=a[i][j]
        cnt+=a[i][j]
for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０
# print(d)

d2 = [[0 for i in range(n)] for i in range(n)]
warshall_floyd(d,d2)
# print(d2)
cnt=0
for i in range(n):
    for j in range(n):
        if d2[i][j]==0:
            cnt+=d[i][j]
print(cnt//2)

Submission status: Accepted

Solution code:
def warshall_floyd(G, n):
    global c
    for i in range(n):
        for j in range(n):
            b = 1
            for k in range(n):
                if j == k or i == k:
                    continue
                if G[i][j] == G[i][k] + G[k][j]:
                    b = 0
                elif G[i][j] > G[i][k] + G[k][j]:
                    print(-1)
                    exit()
            if b == 1:
                c += G[i][j]

n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
c = 0
warshall_floyd(a, n)
print(c // 2)

Submission status: Accepted

Solution code:
N = int(input())
A = [list(map(int, input().split())) for i in range(N)]
flag = True
Sum = 0 
for i in range(N-1):
    for j in range(i+1, N):
        f = True
        for k in range(N):
            if k == i or k == j:
                continue
            if A[i][k] + A[k][j] < A[i][j]:
                flag = False
            elif A[i][k] + A[k][j] == A[i][j]:
                f = False
        if f:
            Sum += A[i][j]
if flag:
    print(Sum)
else:
    print(-1)

Submission status: Accepted

Solution code:
# ワーシャルフロイド　全点最短経路、負の距離あっても可　o(n**3)
def warshall_floyd(d,ans):
    #d[i][j]: iからjへの最短距離
    flag=True
    for i in range(n):
        for j in range(n):
            x=d[i][j]
            y=float('inf')
            for k in range(n):
                if k!=i and k!=j:
                    y = min(d[i][k] + d[k][j],y)
            if x==y:
                ans-=y
            elif x<y:
                continue
            else:
                flag=False
                break

    return flag,ans

##############################
n=int(input())

d = [list(map(int, input().split())) for i in range(n)]
ans=0
for i in range(n):
    ans+=sum(d[i])


a1,a2=warshall_floyd(d,ans)

if a1:
    print(a2//2)
else:
    print(-1)

Submission status: Accepted

Solution code:
def warshall_floyd(e, n):
    d = [[e[j][i] for i in range(n)] for j in range(n)]
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if d[i][k] + d[k][j] < d[i][j]:
                    d[i][j] = d[i][k] + d[k][j]
    # [print(i) for i in d]
    return d

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

ans = [[0 for i in range(n)] for j in range(n)]
for i in range(n):
    for j in range(n):
        if grid[i][j] != dgrid[i][j]:
            print(-1)
            exit()

ans = 0
for i in range(n):
    for j in range(n):
        for k in range(n):
            if i == j or j == k or k == i:
              continue
            if grid[i][k] + grid[k][j] == grid[i][j]:
                dgrid[i][j] = 0

ans = 0
for i in range(n):
    for j in range(i+1, n):
        ans += dgrid[i][j]
print(int(ans))

Submission status: Accepted

Solution code:
from copy import deepcopy

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

graph = deepcopy(A)
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])

ans = 0
for u in range(N):
    if ans < 0:
        break
    for v in range(N):
        if graph[u][v] < A[u][v]:
            ans = -1
            break
            
        flg = True
        for w in range(N):
            if w == u or w == v:
                continue
            flg &= graph[u][v] < graph[u][w] + graph[w][v]
        
        if flg:
            ans += graph[u][v]

print(ans // 2)

Submission status: Accepted

Solution code:
import copy
n=int(input())
a=[list(map(int,input().split())) for i in range(n)]
b=copy.deepcopy(a)
for k in range(n):
  for i in range(n):
    for j in range(n):
      b[i][j]=min(b[i][j],b[i][k]+b[k][j])
for i in range(n):
  for j in range(n):
    if b[i][j]!=a[i][j]:
      print(-1)
      exit()
ans=0
for i in range(n):
  for j in range(i+1,n):
    m=10**18
    for k in range(n):
      if i==j or j==k or k==i:
        continue
      m=min(m,b[i][k]+b[k][j])
    if m>b[i][j]:
      ans+=b[i][j]
print(ans)

Submission status: Accepted

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

dp = A
cnt = 0
for i in range(N - 1):
    for j in range(i + 1, N):
        if all(dp[i][j] < dp[i][k] + dp[k][j] for k in range(N) if k != i and k != j):
            cnt += dp[i][j]
        if any(dp[i][j] > dp[i][k] + dp[k][j] for k in range(N)):
            print(-1)
            exit()

print(cnt)

Submission status: Accepted

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

dp = A
cnt = 0
for i in range(N):
    for j in range(N):
        if all(dp[i][j] < dp[i][k] + dp[k][j] for k in range(N) if k != i and k != j):
            cnt += dp[i][j]
        if any(dp[i][j] > dp[i][k] + dp[k][j] for k in range(N)):
            print(-1)
            exit()

print(cnt // 2)

Submission status: Accepted

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

ans = 0
cannot = 0
for i in range(n-1):
  for j in range(i+1,n):
    detour = min([A[i][k] + A[k][j] for k in range(n) if k!=i and k!=j]+[10**18])
    if detour<A[i][j]:
      cannot = 1
    elif detour>A[i][j]:
      ans += A[i][j]
if cannot:
  print(-1)
else:
  print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc074/tasks/arc083_b
# DP
import copy
import sys
input = sys.stdin.readline
n = int(input()) # 入力が1つ
# map(int, input().split()) # 入力が複数
graph = []
for _ in range(n):
    row = [int(i) for i in input().split()]
    graph.append(row)

ans = 0
for i in range(n):
    for j in range(n):
        for k in range(n):
            if graph[i][j] > graph[i][k] + graph[k][j]:
                # iからjに行く間に、kを挟む方が早いパターンが存在するなら、最短ではない。
                print(-1)
                exit()
            elif graph[i][j] == graph[i][k] + graph[k][j] and k != i and k != j:
                # 自分の点以外で、iからjに行く間に、kを挟んでも同じパターンが存在するなら、それは不要。
                break
        else:
            ans += graph[i][j]

print(ans // 2)

Submission status: Accepted

Solution code:
import heapq
import math
class Graph:
    def __init__(self,v,adj,w_v = None):
        super().__init__()
        self.v = v
        self.w_e = [{} for _ in [0]*self.v]
        self.neighbor = [[] for _ in [0]*self.v]
        
        self.w_v = w_v

        for i, adj_i in enumerate(adj):
            for j, w in enumerate(adj_i):
                self.w_e[i][j] = w #weight of edge
                self.neighbor[i].append(j)

    def dijkstra(self,v_n):
        d = [10**18]*self.v
        d[v_n] = 0
        prev = [-1]*self.v

        queue = []
        for i,d_i in enumerate(d): heapq.heappush(queue,(d_i,i))
        
        while len(queue)>0:
            d_u,u = queue.pop()
            if d[u]<d_u :continue
            for v in self.neighbor[u]:
                alt = d[u]+self.w_e[u][v]
                if d[v]>alt:
                    d[v] = alt
                    prev[v] = u
                    heapq.heappush(queue,(alt,v))

        return d,prev
    
    def WarshallFloyd(self):
        d = [[10**18]*self.v for _ in [0]*self.v]
        for i in range(self.v):
            for j in self.neighbor[i]:
                d[i][j] = self.w_e[i][j]
                
        for i in range(self.v):
            for j in range(self.v):
                for k in range(self.v):
                    check = d[i][k] + d[k][j]
                    if d[i][j] > check:
                        d[i][j] = check
        return d

def main():
    n = int(input())

    a = [[int(t)for t in input().split()]for _ in [0]*n]

    g = Graph(n,a)
    a_check = g.WarshallFloyd()

    s = 0
    for i in range(n):
        for j in range(n):
            a_ij = a[i][j]
            if a_ij != a_check[i][j]:
                print(-1)
                return
            if sum([a_ij == a[i][k] + a[k][j] for k in range(n) if k != i and k != j]) == 0:
                s+=a_ij
    print(s//2)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def warshall_floyd(G):
    import copy
    ret = copy.deepcopy(G)
    for k in range(N):
        for i in range(N):
            for j in range(N):
                ret[i][j] = min(ret[i][j], ret[i][k] + ret[k][j])
    return ret


N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
W, ans = warshall_floyd(A), 0
if A == W:
    for i in range(N):
        for j in range(N):
            if sum([A[i][j] == A[i][k] + A[k][j] for k in range(N) if k != i and k != j]) == 0:
                ans += A[i][j]
    print(ans // 2)
else:
    print(-1)

Submission status: Accepted

Solution code:
def solve(V, G):
    ans = 0
    for i in range(V - 1):
        for j in range(i + 1, V):
            direct = G[i][j]
            for k in range(V):
                if k == i or k == j:
                    continue
                ind = G[i][k] + G[k][j]
                if direct > ind:
                    return -1
                elif direct == ind:
                    break
            else:
                ans += direct
    return ans


def main():
    V = int(input())
    G = [[int(i) for i in input().split()] for i in range(V)]
    print(solve(V, G))


if __name__ == "__main__":
    main()

Submission status: Accepted

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

count=0
for i in range(0,N):
    for j in range(0,N):
        for k in range(0,N):
            if A[i][j]>A[i][k]+A[k][j]:
                print(-1)
                exit()
            elif A[i][j]==A[i][k]+A[k][j] and k!=i and k!=j:
                break
        else:
            count+=A[i][j]

print(count//2)

Submission status: Accepted

Solution code:
n=int(input())
a=[list(map(int,input().split())) for _ in range(n)]
flag=[[True]*n for _ in range(n)]
for k in range(n):
  for i in range(n):
    for j in range(n):
      if i==j or j==k or k==i:
        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[i][j]=False
        flag[j][i]=False
ans=0
for i in range(n-1):
  for j in range(i+1,n):
    if flag[i][j]:
      ans+=a[i][j]
print(ans)

Submission status: Accepted

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

def sol():
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d = A[i][k] + A[k][j]
                if d < A[i][j]:
                    return - 1

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

    return ret

print(sol())

Submission status: Accepted

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

def sol():
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d = A[i][k] + A[k][j]
                if d < A[i][j]:
                    return - 1

    INF = 10**18

    for k in range(N):
        for i in range(N):
            for j in range(N):
                if k == i or k == j:
                    continue

                if A[i][k] + A[k][j] == A[i][j]:
                    A[i][j] = INF

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

    return ans

print(sol())

Submission status: Accepted

Solution code:
from collections import deque
import sys
input = lambda: sys.stdin.readline().rstrip()

N = int(input())

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

for k in range(N):
    for i in range(N):
        for j in range(N):
            if A[i][j] > A[i][k] + A[k][j]:
                print(-1)
                exit()
            if A[i][j] == A[i][k] + A[k][j] and i != k and k != j:
                flg[i][j] = False
                flg[j][i] = False

ans = 0
for i in range(N):
    for j in range(N):
        if flg[i][j]:
            ans += A[i][j]
print(ans//2)