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)]

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()

ans = 0
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]:
                break
        else:
            ans += A[i][j]
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
import copy
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

def nck(n, k, kaijyo):
    return (npk(n, k, kaijyo) * divide(kaijyo[k])) % MOD

def npk(n, k, kaijyo):
    if k == 0 or k == n:
        return n % MOD
    return (kaijyo[n] * divide(kaijyo[n-k])) % MOD

def fact_and_inv(SIZE):
    inv = [0] * SIZE  # inv[j] = j^{-1} mod MOD
    fac = [0] * SIZE  # fac[j] = j! mod MOD
    finv = [0] * SIZE  # finv[j] = (j!)^{-1} mod MOD
    inv[1] = 1
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    for i in range(2, SIZE):
        inv[i] = MOD - (MOD // i) * inv[MOD % i] % MOD
        fac[i] = fac[i - 1] * i % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD

    return fac, finv

def renritsu(A, Y):
    # example 2x + y = 3, x + 3y = 4
    # A = [[2,1], [1,3]])
    # Y = [[3],[4]] または [3,4]
    A = np.matrix(A)
    Y = np.matrix(Y)
    Y = np.reshape(Y, (-1, 1))
    X = np.linalg.solve(A, Y)

    # [1.0, 1.0]
    return X.flatten().tolist()[0]

class TwoDimGrid:
    # 2次元座標 -> 1次元
    def __init__(self, h, w, wall="#"):
        self.h = h
        self.w = w
        self.size = (h+2) * (w+2)
        self.wall = wall
        self.get_grid()
        # self.init_cost()

    def get_grid(self):
        grid = [self.wall * (self.w + 2)]
        for i in range(self.h):
            grid.append(self.wall + getS() + self.wall)

        grid.append(self.wall * (self.w + 2))
        self.grid = grid
    def init_cost(self):
        self.cost = [INF] * self.size

    def pos(self, x, y):
        # 壁も含めて0-indexed 元々の座標だけ考えると1-indexed
        return y * (self.w + 2) + x
    def getgrid(self, x, y):
        return self.grid[y][x]
    def get(self, x, y):
        return self.cost[self.pos(x, y)]
    def set(self, x, y, v):
        self.cost[self.pos(x, y)] = v
        return
    def show(self):
        for i in range(self.h+2):
            print(self.cost[(self.w + 2) * i:(self.w + 2) * (i+1)])
    def showsome(self, tgt):
        for t in tgt:
            print(t)
        return
    def showsomejoin(self, tgt):
        for t in tgt:
            print("".join(t))
        return

    def search(self):
        grid = self.grid
        move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        move_eight = [(0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]
        # for i in range(1, self.h+1):
        #     for j in range(1, self.w+1):
        #         cx, cy = j, i
        #         for dx, dy in move_eight:
        #             nx, ny = dx + cx, dy + cy

def solve():
    n = getN()
    g = []
    for i in range(n):
        g.append(getList())

    ans = 0
    for i in range(n):
        for j in range(i+1, n):
            cc = g[i][j]
            fl = True
            for k in range(n):
                if k == i or k == j:
                    continue
                if g[i][k] + g[j][k] < cc:
                    print(-1)
                    return
                elif g[i][k] + g[j][k] == cc:
                    fl = False

            if fl:
                ans += cc

    print(ans)

def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    # main()
    solve()

Submission status: Accepted

Solution code:
import copy

n=int(input())
a=[]
ans=0
for _ in range(n):
  b=list(map(int,input().split()))
  ans+=sum(b)
  a.append(b)
  
c=copy.deepcopy(a)
  
for i in range(n):
  for j in range(n):
    ch=0
    for k in range(n):
      if c[i][j]==c[i][k]+c[k][j] and ch==0 and i!=k and j!=k:
        ans-=c[i][j]
        ch+=1
      c[i][j]=min(c[i][j],c[i][k]+c[k][j])
      
if a==c:
  
  print(ans//2)
  
else:
  print(-1)

Submission status: Accepted

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

total = 0
for i in range(n-1):
    for j in range(i+1,n):
        flg = True
        for x in range(n):
            if x == i or x == j:
                continue
            if a[i][j] > a[i][x] + a[j][x]:
                print(-1)
                exit()
            elif a[i][j] == a[i][x] + a[j][x]:
                flg = False
                break
        if flg:
            total += a[i][j]
            
print(total)

Submission status: Accepted

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=[[] for i in range(n)]
for i in range(n):
    miti[i]=A[i][:]
    
for k in range(n):
    for j in range(k):
        for i in range(j):
            q=A[i][j]
            w=A[j][k]
            e=A[k][i]
            #print(i,j,k,"\t",q,w,e)
            # q,w,e=sorted([[q,i,j],[w,j,k],[e,k,i]])
            # if max(q,w,e)==inf: continue
            if q+w==e and q!=inf and w!=inf: miti[k][i]=inf;miti[i][k]=inf;continue
            if q+w<A[k][i] and q!=inf and w!=inf: print(-1);exit()
            if w+e==q and e!=inf and w!=inf: miti[i][j]=inf;miti[j][i]=inf;continue
            if w+e<A[i][j]  and e!=inf and w!=inf : print(-1);exit()
            if e+q==A[j][k] and q!=inf and e!=inf: miti[j][k]=inf;miti[k][j]=inf;continue
            if e+q<A[j][k] and q!=inf and e!=inf: 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: Accepted

Solution code:
import copy
N=int(input())



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


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

H=copy.deepcopy(G)

#print(H, G)
H=warshall_floyd(H)



for i in range(N):
    for j in range(N):
        if G[i][j]!=H[i][j]:
            print(-1)
            exit()
T=copy.deepcopy(H)
for k in range(N):
    for i in range(N):
        for j in range(N):
            if H[i][j]==H[i][k] + H[k][j] and i!=k and j!=k:
                T[i][j]=0
ans=0
for i in range(N):
    ans+=sum(T[i])
print(ans//2)

Submission status: Accepted

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


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

B = deepcopy(A)
#d = warshall_floyd(A)
#if B != d:
#  print(-1)
#  exit()

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 A[i][k] + A[k][j] < A[i][j]:
        print(-1)
        exit()
      elif A[i][k] + A[k][j] == A[i][j]: 
        B[i][j] = 0

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

print(ans)

Submission status: Accepted

Solution code:
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"

def main():
    n = int(ipt())
    a = [[int(i) for i in ipt().split()] for _ in range(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]:
                    print(-1)
                    exit()
    for i in range(n):
        for j in range(n):
            for k in range(n):
                if a[j][i] != 0 and a[i][k] != 0 and a[j][k] == a[j][i]+a[i][k]:
                    a[j][k] = 0

    ans = 0
    for i in range(n):
        for j in range(i,n):
            ans += a[i][j]

    print(ans)

    return None

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N=int(input())
import copy
def warshall_floyd(N):
  d=[list(map(int,input().split())) for i in range(N)]
  D=copy.deepcopy(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])
  if d==D:
    return d
  else:
    return -1
  
E=warshall_floyd(N)
if E==-1:
  print(-1)
  exit()
  
for k in range(N):
  for i in range(N):
    for j in range(N):
      if E[i][j]!=0 and E[i][k]!=0 and E[k][j]!=0:
        if E[i][j]==E[i][k]+E[k][j]:
          E[i][j]=0       
ans=0
for i in range(N):
  ans+=sum(E[i]) 
print(ans//2)

Submission status: Accepted

Solution code:
# 63


n = int(input())
dp = [[int(x) for x in input().split()] for y in range(n)]
del_l = []
ans = 0

for i in range(n-1):
    for j in range(i+1,n):
        for k in range(n):
            if k in (i,j):
                continue
            if dp[i][j] > dp[i][k] + dp[k][j]:
                print("-1")
                exit()
            elif dp[i][j] == dp[i][k] + dp[k][j]:
                break
        else:
            ans += dp[i][j]

print(ans)

Submission status: Accepted

Solution code:
# 63


n = int(input())
dp = [[int(x) for x in input().split()] for y in range(n)]
del_l = []
ans = 0

for i in range(n):
    for j in range(i+1,n):
        ans += dp[i][j]

for i in range(n-1):
    for j in range(i+1,n):
        for k in range(n):
            if k in (i,j):
                continue
            if dp[i][j] > dp[i][k] + dp[k][j]:
                print("-1")
                exit()
            elif dp[i][j] == dp[i][k] + dp[k][j]:
                ans -= dp[i][j]
                break

print(ans)

Submission status: Accepted

Solution code:
# 63


n = int(input())
dp = [[int(x) for x in input().split()] for y in range(n)]
del_l = []
ans = 0

# for i in range(n):
#     for j in range(i+1,n):
#         ans += dp[i][j]

for i in range(n-1):
    for j in range(i+1,n):
        for k in range(n):
            if k in (i,j):
                continue
            if dp[i][j] > dp[i][k] + dp[k][j]:
                print("-1")
                exit()
            elif dp[i][j] == dp[i][k] + dp[k][j]:
                break
        else:
            ans += dp[i][j]

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, A: "List[List[int]]"):
    import numpy as np
    from scipy.sparse.csgraph import floyd_warshall
    A = np.array(A, dtype=np.float64)
    B = floyd_warshall(A, directed=True)
    if not np.array_equal(A, B):
        return -1
    delta = 1e-1
    _, pre = floyd_warshall(A-delta, return_predecessors=True)
    return int(A[pre == [[i]*N for i in range(N)]].sum()) // 2

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [[int(next(tokens)) for _ in range(N)] for _ in range(N)]  # type: "List[List[int]]"
    print(solve(N, A))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, A: "List[List[int]]"):
    import numpy as np
    from scipy.sparse.csgraph import floyd_warshall
    A = np.array(A, dtype=np.float64)
    B = floyd_warshall(A, directed=True)
    if not np.array_equal(A, B):
        return -1
    delta = 1e-1
    _, pre = floyd_warshall(A-delta+np.identity(N)*delta, return_predecessors=True)
    return int(A[pre == [[i]*N for i in range(N)]].sum()) // 2

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [[int(next(tokens)) for _ in range(N)] for _ in range(N)]  # type: "List[List[int]]"
    print(solve(N, A))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, A: "List[List[int]]"):
    import numpy as np
    from scipy.sparse.csgraph import floyd_warshall
    A = np.array(A, dtype=np.float64)
    B = floyd_warshall(A, directed=True)
    if not np.array_equal(A, B):
        return -1
    delta = 1e-3
    _, pre = floyd_warshall(A-delta+np.identity(N)*delta, return_predecessors=True)
    return int(A[pre == [[i]*N for i in range(N)]].sum()) // 2

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [[int(next(tokens)) for _ in range(N)] for _ in range(N)]  # type: "List[List[int]]"
    print(solve(N, A))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, A: "List[List[int]]"):
    import numpy as np
    from scipy.sparse.csgraph import floyd_warshall
    A = np.array(A, dtype=np.float64)
    B = floyd_warshall(A, directed=True)
    if not np.array_equal(A, B):
        return -1
    delta = 1e-7
    _, pre = floyd_warshall(A-delta+np.identity(N)*delta, return_predecessors=True)
    return int(A[pre == [[i]*N for i in range(N)]].sum()) // 2

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [[int(next(tokens)) for _ in range(N)] for _ in range(N)]  # type: "List[List[int]]"
    print(solve(N, A))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Accepted

Solution code:
import copy

N = int(input())
graph = []
road = []
for _ in range(N):
  A = list(map(int, input().split()))
  graph.append(A)
  road.append(copy.deepcopy(A))

exist = 1
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]:
        exist = 0
        break
      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]:
          road[i][j] = 0
    if exist == 0:
      break
  if exist == 0:
    break

if exist == 0:
  print(-1)
else:
  ans = 0
  for row in road:
    ans += sum(row)
  print(ans//2)

Submission status: Accepted

Solution code:
n = int(input())
a = [list(map(int, input().split())) 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(0)

ans = 0
for i in range(n):
    for j in range(i+1, n):
        ok = True
        for k in range(n):
            if i == k or j == k:
                continue
            if a[i][j] == a[i][k]+a[k][j]:
                ok = False
                break
        if ok:
            ans += a[i][j]
print(ans)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()

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

    """
    まず三角不等式が任意の３頂点に対して成り立つことを確認する。
    なりたってなければグラフは存在しない。

    なりたっている場合は与えられた最短距離と同じ長さの辺を各頂点のペアごとに張れば
    一応条件を満たすグラフは構成できている。

    あとはここから余分な辺をどう削除するかだが、これは三角不等式で統合が成り立っているもの
    として判別できる。
    """

    # 三角不等式チェック
    triangle = True
    used_path = [[0] * N for _ in range(N)]
    for i in range(N):
        for j in range(i + 1, N):
            minimal_dist = 10**18
            for k in range(N):
                if k == i or k == j: continue
                if A[i][k] + A[k][j] < A[i][j]:
                    triangle = False
                    break
                else:
                    minimal_dist = min(minimal_dist, A[i][k] + A[k][j])
            if A[i][j] < minimal_dist: used_path[i][j] = 1
    if not triangle:
        print(-1)
        return
    
    # 辺の削除
    ans = 0
    for i in range(N):
        for j in range(i + 1, N):
            ans += A[i][j] * used_path[i][j]
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    N = int(readline())
    A = list(list(map(int, readline().split())) for _ in range(N))
    A = np.array(A)
    D = dijkstra(A)
    if (A!=D).any():
        print(-1)
    else:
        ans = 0
        D += np.identity(N, int) * (10**10)
        for i in range(N):
            for j in range(i + 1, N):
                a = np.min(D[i] + D[j])
                if a > D[i, j]:
                    ans += D[i, j]
        print(int(ans))



if __name__ == '__main__':
    main()

Submission status: Accepted

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

ans = 0

for i in range(N):
    for j in range(N):
        used = True
        for k in range(N):
            if i == k or j == k:
                continue
            tmp = A[i][k] + A[k][j]
            if A[i][j] > tmp:
                print(-1)
                exit()
            if A[i][j] == tmp:
                used = False
        if used:
            ans += A[i][j]
print(ans//2)

Submission status: Accepted

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

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

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

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

total = 0
for n in range(N):
    for m in range(n + 1, N):
        total += A[n][m]

flag = False
for n in range(N):
    for m in range(n + 1, N):
        for k in range(N):
            if k != n and k != m:
                if A[n][m] > A[n][k] + A[k][m]:
                    flag = True
                    break
                elif A[n][m] == A[n][k] + A[k][m]:
                    # この辺はいらない
                    total -= A[n][m]
                    break
        if total < 0 or flag:
            break
    if total < 0 or flag:
        break

if flag:
    print(-1)
else:
    print(total)

Submission status: Accepted

Solution code:
def print_dp(dp):
    i_len = len(dp)
    j_len = len(dp[0])
    tmp_dp = [[0]*i_len for _ in range(j_len)]
    for i in range(i_len):
        for j in range(j_len):
            tmp_dp[j][i] = dp[i][j]
    for i in range(j_len):
        print(tmp_dp[i])

import copy
n = int(input())
grid = [[float('inf')]*n for _ in range(n)]
for i in range(n):
    lis = list(map(int, input().split()))
    for j in range(n):
        if i == j:
            grid[i][j] = 0
        else:
            grid[i][j] = lis[j]
grid_m = copy.deepcopy(grid)

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

ok = True
for i in range(n):
    for j in range(n):
        if not grid[i][j] == grid_m[i][j]:
            ok = False
if not ok:
    print(-1)
else:
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if i == k or j == k:
                    continue
                if grid[i][j] == grid[i][k] + grid[k][j] and grid[i][k] != 0 and grid[k][j] != 0:
                    grid[i][j] = 0
    res = 0
    for i in range(n):
        res += sum(grid[i])
    print(res//2)

Submission status: Accepted

Solution code:
N = int(input())
A = [[0 for _ in range(N+1)]]
for _ in range(N):
    a = list(map(int,input().split()))
    a.insert(0,0)
    A.append(a)
tot = 0
for i in range(1,N):
    for j in range(i,N+1):
        tot += A[i][j]
for i in range(1,N):
    for j in range(i+1,N+1):
        for k in range(1,N+1):
            if k!=i and k!=j:
                if A[i][j]>A[i][k]+A[k][j]:
                    tot = -1
                    break
                elif A[i][j]==A[i][k]+A[k][j]:
                    tot -= A[i][j]
                    break
        if tot<0:break
    if tot<0:break
print(tot)

Submission status: Accepted

Solution code:
from copy import deepcopy
def solve():
  ans = 0
  N = int(input())
  A = [list(map(int, input().split())) for _ in range(N)]
  d = deepcopy(A)
  D = deepcopy(A)
  #三重ループ
  for k in range(N):
    for i in range(N):
      if i==k:
        continue
      for j in range(N):
        if j==k:
          continue
        if d[i][k]+d[k][j]<=d[i][j]:
          d[i][j] = d[i][k]+d[k][j]
          D[i][j] = float('inf')
  for i in range(N): #ひとまず枝があるペアは枝の長さをセット
    for j in range(N):
      if D[i][j]<float('inf') and i>j:
        ans += A[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])
  for i in range(N):
    for j in range(N):
      if D[i][j] != A[i][j]:
        return -1
  return ans
print(solve())

Submission status: Accepted

Solution code:
import numpy as np
 
N = int(input())
A = np.array([input().split() for _ in range(N)], dtype=np.int64).reshape(N,N)

np.fill_diagonal(A, 10**9+1)

ans = 0
for i in range(N-1):
  for j in range(i+1,N):
    d = np.min(A[i]+A[j])
    if d > A[i][j]:
      ans+=A[i][j]
    elif d < A[i][j]:
      print(-1)
      exit()

print(ans)

Submission status: Accepted

Solution code:
import sys
from copy import deepcopy

N = int(input())
A = [[int(x) for x in input().split()] for _ in range(N)]
B = deepcopy(A)
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][k] + A[k][j] < A[i][j]:
                print(-1)
                sys.exit()
            elif A[i][k] + A[k][j] == A[i][j]:
                B[i][j] = 0

ans = sum(sum(B[i][j] for j in range(N)) for i in range(N)) // 2
print(ans)

Submission status: Accepted

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

A = []
for _ in range(N):
  A.append(list(map(int, input().split())))
  
D = copy.deepcopy(A)
for i in range(N):
  D[i][i] = 0
  
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])
      
#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: Accepted

Solution code:
import sys

N = int(sys.stdin.readline())

d = []
for _ in range(N):
    d.append(list(map(int, sys.stdin.readline().split())))

grid_min_path = [[True for _ in range(N)] for _ in range(N)]

def warshall_floyd(d, n, grid_min_path):
    changed = False
    path_length = 0
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if d[i][j] > d[i][k] + d[k][j]:
                    changed = True
                if d[i][j] == d[i][k] + d[k][j] and i != k and k != j:
                    # print(i, j, k)
                    grid_min_path[i][j] = False
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d, changed, grid_min_path

d, changed, grid_min_path = warshall_floyd(d, N, grid_min_path)
# print(grid_min_path)
if changed:
    print(-1)
else:
    length = 0
    for i in range(N):
        for j in range(i+1, N):
            if grid_min_path[i][j]:
                length += d[i][j]
    print(length)

Submission status: Accepted

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

import copy

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

A2 = copy.deepcopy(A)
for k in range(N):
    for i in range(N):
        for j in range(N):
            A2[i][j] = min(A2[i][j], A2[i][k] + A2[k][j])

for i in range(N):
    for j in range(N):
        if A[i][j] != A2[i][j]:
            print(-1)
            exit()

result = 0
for i in range(N):
    for j in range(N):
        flag = True
        if i == j:
            continue
        for k in range(N):
            if i == k or j == k:
                continue
            if A2[i][j] == A[i][k]+A[k][j]:
                flag = False
                break
        if flag:
            result += A[i][j]

print(result//2)

Submission status: Accepted

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

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

flag = True

for i in range(n):
    if root[i][i] != 0:
        flag = False
        break

search_distance = copy.deepcopy(root)

search_distance = warshall_floyd(search_distance)

ans = 0

for i in range(n):
    for j in range(n):
        if search_distance[i][j] != root[i][j]:
            flag = False
            break
        else:
            judge = 1
            for h in range(n):
                if h != i and h != j and root[i][h]+root[h][j] == root[i][j]:
                    judge = -1
            if judge == 1:
                ans += root[i][j]
if flag:
    print(ans//2)
else:
    print(-1)

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
import numpy as np
N = int(input())
A = np.array([list(map(int, input().split())) for _ in [0]*N], dtype=np.int)
D = csgraph_from_dense(A)
D = floyd_warshall(D, directed=False)

if (A == D).all():
    ans = 0
    D += np.identity(N, int) * (1 << 60)
    for i in range(N):
        for j in range(i+1, N):
            a = np.min(D[i]+D[j])
            if a > D[i, j]:
                ans += D[i, j]
    print(int(ans))
else:
    print(-1)