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:
#!/usr/bin/env python3
#ABC74 D

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

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

for i in range(n):
    for j in range(i+1,n):
        for k in range(n):
            if i == k or j == k:
                continue
            if a[i][j] > a[i][k] + a[k][j]:
                print(-1)
                quit()
            if a[i][j] == a[i][k] + a[k][j]:
                ans -= a[i][j]
                break
print(ans)

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

ans = 0

for i in range(N):
    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)]

flag = [[0] * N for _ in range(N)]
dist = [line[:] for line in 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 dist[i][j] > dist[i][k] + dist[k][j]:
                dist[i][j] = dist[i][k] + dist[k][j]
            elif dist[i][j] < dist[i][k] + dist[k][j]:
                flag[i][j] += 1

if A != dist:
    print(-1)
    exit()

ans = 0
for i in range(N):
    for j in range(N):
        if flag[i][j] == N-2:
            ans += A[i][j]

ans //= 2
print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    N = int(input())
    A = [list(map(int,input().split())) for i in range(N)]
    
    import copy
    D = [[[0,1] for i in range(N)] for j in range(N)]
    for i in range(N):
        for j in range(N):
            D[i][j][0] = A[i][j]
    flag = 0
    
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if k != i and k != j:
                    if D[i][j][0] > D[i][k][0] + D[k][j][0]:
                        flag = 1
                    elif D[i][j][0] == D[i][k][0] + D[k][j][0]:
                        D[i][j][1] += 1
    ans = 0
    for i in range(N):
        for j in range(i+1,N):
            if D[i][j][1] == 1:
                ans += D[i][j][0]
    if flag == 1:
        print(-1)
    else:
        print(ans)
    
main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=sys.stdin.readline
def resolve():
    n=int(input())
    A=[0]*n
    ans=0
    for i in range(n):
        A[i]=list(map(int,input().split()))
        ans+=sum(A[i])
    from copy import deepcopy
    B=deepcopy(A)
    # Warshall-Floyd
    from itertools import product
    for k,i,j in product(range(n),repeat=3):
        B[i][j]=min(B[i][j],B[i][k]+B[k][j])
    # calculate
    if A!=B:
        print(-1)
        return
    for i,j in product(range(n),repeat=2):
        if i==j: continue
        flag=False
        for r in range(n):
            if i==r or j==r: continue
            flag=(flag or B[i][j]==B[i][r]+B[r][j])
        if flag: ans-=B[i][j]
    print(ans//2)

resolve()

Submission status: Accepted

Solution code:
n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
b = [[1]*n for i 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!=j:
                b[i][j] = 0

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

Submission status: Accepted

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

for i in range(n):
    for j in range(n):
        for k 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!=j:
                b[i][j] = 0

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

Submission status: Accepted

Solution code:
import sys,bisect as bs,collections as cl
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
n = onem()

ans = 0
a = []

for i in range(n):
    a.append(l())

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()
for i in range(n-1):
    for j in range(i,n):
        for k in range(n):
            if i == k 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:
N = int(input())

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

#ワーシャルフロイド法で条件を満たすものがあるか確認
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,N):
        for k in range(N):
            if i == k or j == k:
                continue
            if A[i][j] == A[i][k] + A[k][j]: # A[i][j]はiとjのノードを直接結ぶものではない
                break
        else:
            ans += A[i][j]

print(ans)

Submission status: Accepted

Solution code:
n = int(input())

field = [ [ int(v) for v in input().split() ] for i in range(n) ]
field_2 = [ [ 1 for i in range(n) ] for i in range(n) ]

err = 0
for k in range(n):
    for i in range(n):
        for j in range(n):
            if i != j and j != k and k != i:
                if field[i][k] + field[k][j] == field[i][j]:
                    field_2[i][j] = 0
                if field[i][k] + field[k][j] < field[i][j]:
                    err = 1

if err == 0:
    ans = 0
    for i in range(n):
        for j in range(n):
            ans += field[i][j] * field_2[i][j]
    print(ans//2)
else:
    print(-1)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
import copy
 
def WarshallFloyd(Map):
    Dist=copy.deepcopy(Map)
    l=len(Dist)
    for k in range(l):
        for i in range(l):
            for j in range(l):
                Dist[i][j]=min(Dist[i][j],Dist[i][k]+Dist[k][j])
    return Dist

def solve(n,A):
    B=WarshallFloyd(A)
    for i in range(n):
        for j in range(n):
            if A[i][j]>B[i][j]:
                return -1
    for k in range(n):
        for i in range(n):
            if i==k:
                continue
            for j in range(n):
                if j==k:
                    continue
                if A[i][j]==A[i][k]+A[k][j]:
                    B[i][j]=0; B[j][i]=0
    ret=0
    for i in range(n):
        ret+=sum(B[i])
    ret//=2
    return ret

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

class UnionFind():
    def __init__(self,n):
        self.par = [i for i in range(n)]
        self.rank = [0] * n

    def root(self,x):
        if x == self.par[x]:
            return x
        r = self.root(self.par[x])
        self.par[x] = r
        return r

    def unit(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y: return False
        if self.rank[x] < self.rank[y]: x, y= y, x,
        if self.rank[x] == self.rank[y]: self.rank[x] += 1
        self.par[y] = x
        return True
#A
def A():
    n, a = II(), II()
    print(n * n - a)
    return

#B
def B():
    _ = II()
    k = II()
    x = LI()
    ans = 0
    for xi in x:
        ans += min(xi, k - xi)
    print(ans * 2)
    return

#C
def C():
    a, b, c, d, e, F = LI()
    ans = [min(a,b)*100, 0]
    for ai in range(F // (100 * a) + 1):
        for bi in range((F - 100 * ai * a) // (100 * b) + 1):
            if ai == bi == 0:
                continue
            ab = ai * 100 * a + bi * 100 * b
            for ci in range((F - ab) // c + 1):
                for di in range((F - ab - ci * c) // d + 1):
                    if (ai * a + bi * b) * e < ci * c + di * d:
                        continue
                    if ans[1] / ans[0] < (ci * c + di * d) / (ab + ci * c + di * d):
                        ans = [ab + ci * c + di * d, ci * c + di * d]
    print(*ans)
    return

#D
def D():
    n = II()
    edg = LIR(n)

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

    for x in range(n):
        for y in range(x + 1, n):
            for k in range(n):
                if x == k or y == k:
                    continue
                if edg[x][y] > edg[x][k] + edg[k][y]:
                    print(-1)
                    return
                if edg[x][y] == edg[x][k] + edg[k][y]:
                    ans -= edg[x][y]
                    break

    print(ans)

    return

#Solve
if __name__ == '__main__':

    D()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def main():
    INF = float('inf')
    N = int(input())
    d = [[int(x) for x in input().split()]for _ in range(N)]
    ans = 0
    flag = True
    for i in d:
        ans += sum(i)
    ans //= 2
    max_d = 0
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if(i==j or j==k or i==k or d[i][j]==INF):continue
                max_d = max(max_d,d[i][j])
                if(d[i][j]==d[i][k] + d[k][j]):
                    ans -= d[i][j]
                    d[i][j] = INF
                    d[j][i] = INF
                elif(d[i][j]>d[i][k] + d[k][j]):
                    flag = False
    print(ans if (ans >= max_d)and flag else -1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
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 II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

import copy

def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    arr = copy.deepcopy(d)
    n = len(arr)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                arr[i][j] = min(arr[i][j], arr[i][k] + arr[k][j])
    return arr

def main(): 
    N = II()
    tizu = []
    for _ in range(N):
        tizu.append(LI())

    min_road = warshall_floyd(tizu)
    for i in range(N):
        for j in range(N):
            if tizu[i][j] > min_road[i][j]:  # 回り道をしたほうが速い。
                print(-1)
                return

    # 残っているのは、回り道をしても早くならないもののみ。
    # → 2点間距離と、別の町に行ってから目的地に行く距離とは、同じかそれより大きいかしかない。
    # → 経由地は1つだけ考えれば良い。

    for keiyu in range(N):
        for i in range(N):
            if i == keiyu: continue
            for j in range(N):
                if j == keiyu: continue
                if tizu[i][j] == tizu[i][keiyu] + tizu[keiyu][j]:
                    min_road[i][j] = 0
                    min_road[j][i] = 0
    
    ans = 0
    for i in range(N):
        ans += sum(min_road[i])

    print(ans//2)


main()

Submission status: Accepted

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

def judge() :
    s = 0
    for i in range(N) :
        for j in range(i + 1, N) :
            for k in range(N) :
                if i == k or j == k :
                    continue
                if A[i][k] + A[k][j] < A[i][j] :
                    return -1
                elif A[i][k] + A[k][j] == A[i][j] :
                    s += A[i][j]
                    break
    tot = 0
    for i in range(N) :
        for j in range(i + 1, N) :
            tot += A[i][j]
    return tot - s
    
print(judge())

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline

#n,x = [int(i) for i in readline().split()]
n = int(input())
d = [[int(i) for i in readline().split()] for i in range(n)]
e = []
for i in range(n):
    for j in range(i+1,n):
        e.append((d[i][j],i,j))

e.sort()

ans = 0
for c,i,j in e:
    eq = 0
    for k in range(n):
        dk = d[k][i] + d[k][j]
        if dk < c:
            print(-1)
            exit()
        elif dk == c and k != i and k != j:
            eq = 1
    if eq: continue
    else: ans += c

            
print(ans)

Submission status: Accepted

Solution code:
inf = float("inf")
N = int(input())
A = []
for _ in range(N):
    a = [int(s) for s in input().split()]
    A.append(a)
d = [a[:] for a in A]
ans = 0
for i in range(N - 1):
    for j in range(i + 1, N):
        dmin = min([inf] + [d[i][k] + d[k][j]
                            for k in range(N) if k not in (i, j)])
        if d[i][j] > dmin:
            print(-1)
            exit()
        if d[i][j] != dmin:
            ans += d[i][j]
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
INF=float("inf")
g=[[INF]*n for _ in range(n)]
ans=0
for i in range(n):
	for j,c in enumerate(map(int,input().split())):
		if i!=j:
			g[i][j]=c
for i in range(n):
	for j in range(i):
		m=min(a+b for a,b in zip(g[i],g[j]))
		if g[i][j]>m:
			print(-1)
			exit()
		if g[i][j]<m:
			ans+=g[i][j]
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")


class Graph(object):
    def __init__(self, N):
        self.N = N
        self.V = list(range(N))
        self.E = [[] for _ in range(N)]

    def add_edge(self, edge):
        """辺を加える。edgeは(始点, 終点、重み)からなるリスト
        重みがなければ、重み1とする。
        """
        if len(edge) == 2:
            edge.append(1)
        elif len(edge) != 3:
            print("error in add_edge")
            pass

        s, t, w = edge
        self.E[s].append([t, w])
        self.E[t].append([s, w])  # 無向グラフを仮定。逆向きにも辺を張る

        pass

    def remove_edge(self, edge):
        if len(edge) == 2:
            edge.append(1)
        elif len(edge) != 3:
            print("error in add_edge")
            pass

        s, t, w = edge
        for tt, ww in self.E[s]:
            if tt == t:
                break
        if tt == t:
            self.E[s].remove([t, ww])
            self.E[t].remove([s, ww])
        pass


def Warshall_Floyd(g: Graph):
    """ワーシャルフロイド法により、全節点対の最短距離を求める。O(V^3)
    https://ja.wikipedia.org/wiki/%E3%83%AF%E3%83%BC%E3%82%B7%E3%83%A3%E3%83%AB%E2%80%93%E3%83%95%E3%83%AD%E3%82%A4%E3%83%89%E6%B3%95
    """
    N = g.N
    dist = [[INF]*N for _ in range(N)]
    for from_, toweights in enumerate(g.E):
        for to_, w in toweights:
            dist[from_][to_] = w

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


def solve(N: int, A: "List[List[int]]"):

    g = Graph(N)
    for i in range(N):
        for j in range(i+1, N):
            g.add_edge([i, j, A[i][j]])

    B = Warshall_Floyd(g)

    counter = 0
    for i in range(N):
        for j in range(i+1, N):
            if B[i][j] < A[i][j]:
                print(-1)
                return

            flag = True
            for k in range(N):
                if B[i][j] == B[i][k]+B[k][j]:
                    flag = False
            if flag == True:
                counter += B[i][j]
    print(counter)

    return


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

    solve(N, A)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
INF = float('inf')
N = int(input())
a = [list(map(int, input().split())) for i in range(N)]
b = [[INF] * N for i in range(N)]
for k in range(N):
    for i in range(N):
        for j in range(N):
            b[i][j] = min(b[i][j], a[i][k] + a[k][j])
for i in range(N):
    for j in range(N):
        if b[i][j] < a[i][j]:
            print(-1)
            quit()
ans = 0
for i in range(N-1):
    for j in range(i+1, N):
        flag = 1
        for k in range(N):
            if a[i][j] == a[i][k] + a[k][j] and k != i and k != j:
                flag = 0
                break
        if flag: ans += a[i][j]
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [[float('inf')]*(N+1)] + [[float('inf')]+list(map(int,input().split())) for _ in range(N)]
test = [[float('inf')]*(N+1) for _ in range(N+1)]
def main():
    for i in range(1,N+1):
        for j in range(1,N+1):
            for k in range(1,N+1):
                test[i][j] = min(test[i][j],A[i][j],A[i][k] + A[k][j])
    ans = 0
    if test == A:
        for i in range(1,N+1):
            for j in range(i+1,N+1):
                flag = True
                for k in range(1,N+1):
                    if A[i][j] == A[i][k] + A[j][k] and k != i and k != j:
                        flag = False
                        break
                if flag:
                    ans += A[i][j]    
        print(ans)                
    else:
        print(-1)
main()

Submission status: Accepted

Solution code:
N = int(input())
G = [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 G[i][k] + G[k][j] < G[i][j]:
                print(-1)
                exit()

Need = [[True] * N for i in range(N)]
for k in range(N):
    for i in range(N):
        for j in range(N):
            if (i == k) or (j == k):
                continue
            if G[i][k] + G[k][j] == G[i][j]:
                Need[i][j] = False

ans = 0
for i in range(N):
    for j in range(N):
        if Need[i][j]:
            ans += G[i][j]

print(ans // 2)

Submission status: Accepted

Solution code:
import sys
import numpy as np
input = sys.stdin.readline
n = int(input())
G = np.array([list(map(int, input().split())) for _ in range(n)], dtype=float)
G2 = G
for i in range(n):
    G2[i,i] = np.inf
use = np.ones((n,n),dtype=bool)
impossible = np.zeros((n,n),dtype=bool)
for w in range(n):
    D = sum(np.meshgrid(G2[w], G2[w]))
    use &= ~(G == D)
    impossible |= G > D
if impossible.sum() > n:
    print(-1)
else:
    print(int(np.sum(G[use]) / 2))

Submission status: Accepted

Solution code:
import sys
import numpy as np
input = sys.stdin.readline
n = int(input())
G = np.array([list(map(int, input().split())) for _ in range(n)], dtype=float)
use = np.ones((n,n),dtype=bool)
impossible = np.zeros((n,n),dtype=bool)
for w in range(n):
    D = sum(np.meshgrid(G[w], G[w]))
    D[w] = np.inf
    D[:,w] = np.inf
    use &= ~(G == D)
    impossible |= G > D
if impossible.any():
    print(-1)
else:
    print(int(np.sum(G[use]) / 2))

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = [list(map(int, input().split())) for _ in range(N)]
    ans = 0
    for i in range(N):
        A[i][i] = float('INF')
    for i in range(N):
        for j in range(i):
            if i == j:
                A[i][j] = float('INF')
                continue
            b = min(map(sum, zip(A[i], A[j])))
            if A[i][j] > b:
                print(-1)
                return
            if b > A[i][j]:
                ans += A[i][j]
    print(ans)


main()

Submission status: Accepted

Solution code:
from subprocess import*
call(('python3','-c',"""
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]*all(t[j]<t+h[j])for i,t in enumerate(h)for j in range(i)))*(f==g).all()or-1)
"""))

Submission status: Accepted

Solution code:
import sys
from itertools import permutations, combinations

N=input()
d=[ [ float("inf") for j in range(N+1) ] for i in range(N+1) ] 

KOUHO=[]
for i in range(N):
	L=map(int, sys.stdin.readline().split())
	d[i][i]=0
	for j in range(i+1,N):
		length=L[j]
		d[i+1][j+1]=length
		d[j+1][i+1]=length
		KOUHO.append( (length,i+1,j+1))


ans=0
for c,i,j in KOUHO:
	for k in range(1,N+1):
		if k==i or k==j: continue
		a=d[i][k]
		b=d[j][k]
		if a+b==c:
			break
		elif a+b<c:
			print -1
			quit()
	else:
		ans+=c

print ans

Submission status: Accepted

Solution code:
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]*all(t[j]<t+h[j])for i,t in enumerate(h)for j in range(i)))*(f==g).all()or-1)

Submission status: Accepted

Solution code:
N=int(input())
MP=[list(map(int,input().split())) for i in range(N)]
MP2=[]
for li in MP:
    MP2.append([i for i in li])

MP3=[[-1]*N for _ in range(N)]

# ワーシャルフロイド
for k in range(N):
    for i in range(N):
        for j in range(N):
            cand = MP2[i][k] + MP2[k][j]
            if cand <= MP2[i][j]:
                MP2[i][j] = cand
                if (i != k and j != k):
                    MP3[i][j] = k

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

checked=set()

res = set()
def dfs(i,j):
    k = MP3[i][j]
    if k == -1:
        k = i
    if (i,j) in checked:
        return
    checked.add((i,j))
    if (i == k or j == k):
        if i < j:
            res.add((i,j))
    else:
        dfs(i,k)
        dfs(k,j)

for i in range(N):
    for j in range(N):
        dfs(i,j)

ressum = 0
for i,j in res:
    ressum += MP[i][j]

# for li in MP3:
#     print(li)
# print(res)
print(ressum)

Submission status: Accepted

Solution code:
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:
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)
a=0
for i,t in enumerate(h):
  for j in range(i):
    a+=t[j]*(t[j]<t+h[j]).all()
print(int(a)*(f==g).all()or-1)

Submission status: Accepted

Solution code:
import numpy as np
#from numpy import*
#from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph)
#from scipy.sparse.csgraph import dijkstra
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix

from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul,itemgetter
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
input=sys.stdin.readline  #危険！基本オフにしろ！
sys.setrecursionlimit(10**8)

def main():
    n=int(input())
    grid=[list(map(int,input().split()))for i in range(n)]
    p=floyd_warshall(csgraph=csr_matrix(grid))
    q=[list(i) for i in p]
    
    if q!=grid:
        print(-1)
    else:
        for i in range(n):
            p[i][i]=float("inf")
        ans=0
        for i in range(n):
            for j in range(i):
                if p[i][j]<min(np.array(p[i])+np.array(p[j])):
                    
                    ans+=p[i][j]
        print(int(ans))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
#from numpy import*
#from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph)
#from scipy.sparse.csgraph import dijkstra
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix

from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul,itemgetter
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
#input=sys.stdin.readline  #危険！基本オフにしろ！
sys.setrecursionlimit(10**8)

def main():
    n=int(input())
    grid=[list(map(int,input().split()))for i in range(n)]
    p=floyd_warshall(csgraph=csr_matrix(grid))
    q=[list(i) for i in p]
    
    if q!=grid:
        print(-1)
    else:
        for i in range(n):
            p[i][i]=float("inf")
        ans=0
        for i in range(n):
            for j in range(i):
                if i==j:
                    continue
                if p[i][j]<min(np.array(p[i])+np.array(p[j])):
                    
                    ans+=p[i][j]
        print(int(ans))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N=int(input())
A=[]
for i in range(N):
    a=list(map(int,input().split()))
    A.append(a)
ans=0
for i in range(N):
    for j in range(N):
        ans+=A[i][j]
        for k in range(i+1,N):
            if A[i][j]+A[j][k]<A[i][k]:
                print(-1)
                quit()
ans//=2
for i in range(N):
    for k in range(i+1,N):
        for j in range(N):
            if i==j or j==k:
                continue
            if A[i][j]+A[j][k]==A[i][k]:
                ans-=A[i][k]
                break

print(ans)

Submission status: Accepted

Solution code:
import sys

import numpy as np

sys.setrecursionlimit(10000)
INF = float('inf')

N = int(sys.stdin.readline())
A = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
A = np.array(A, dtype=float) + np.diag([np.inf] * N)

useless = np.zeros((N, N), dtype=bool)
impossible = np.zeros((N, N), dtype=bool)
for via in range(N):
    # R[i][j]: i -> via -> j の距離
    R = sum(np.meshgrid(A[via], A[via]))
    useless |= R == A
    impossible |= R < A

if (impossible ^ np.eye(N, dtype=bool)).sum():
    print(-1)
else:
    print(int(A[~useless].sum() // 2))

Submission status: Accepted

Solution code:
import itertools
import sys

sys.setrecursionlimit(10000)
INF = float('inf')

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


def solve():
    # 消していいやつ
    useless = [[0] * N for _ in range(N)]

    # 1 つ経由するのだけ考えれば OK
    for st, en in itertools.combinations(range(N), r=2):
        for via in range(N):
            if via in [st, en]:
                continue
            if A[st][via] + A[via][en] < A[st][en]:
                return -1
            if A[st][via] + A[via][en] == A[st][en]:
                useless[st][en] = True
                useless[en][st] = True
    return sum([A[s][e] for s, e in itertools.product(range(N), repeat=2) if not useless[s][e]]) // 2


print(solve())