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 _ in range(n)]

exist = True
ans = 0
ls = []
for i in range(n - 1):
    for j in range(i + 1, n):
        ls.append((a[i][j], i, j))
ls = list(reversed(sorted(ls)))
for (d, u, v) in ls:
    use = True
    for w in range(n):
        if u == w or v == w:
            continue
        if a[u][v] == a[u][w] + a[w][v]:
            use = False
        elif a[u][w] + a[w][v] < a[u][v]:
            exist = False
    if use:
        ans += d
if not exist:
    print(-1)
else:
    print(ans)

Submission status: Accepted

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

res = A.sum() // 2

A_ = A.copy()

# forbid self loop
for i in range(N):
    A_[i, i] = 1000000001


A3 = np.zeros((N, N, N), dtype=int)
for i in range(N):
    A3[i, :, :] += A_
for j in range(N):
    A3[:, :, j] += A_
    
A3_min = A3.min(axis=1)

for i in range(N-1):
    for j in range(i+1, N):
        if A3_min[i, j] < A[i, j]:
            res = -1
        elif A3_min[i, j] == A[i, j]:
            res -= A[i, j]
        
        
if res < 0:
    print(-1)
else:
    print(res)

Submission status: Accepted

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

for k in range(n):
    for i in range(n):
        for j in range(n):
            B[i][j] = min(B[i][k] + B[k][j], B[i][j])
ok = 1
for i in range(n):
    for j in range(n):
        if A[i][j] != B[i][j]:
            ok = 0
if not ok:
    print(-1)
    exit(0)

ans = 0
for i in range(n):
    for j in range(i+1, n):
        need = 1
        for k in range(n):
            if i == k or j == k:
                continue
            if A[i][k] + A[k][j] == A[i][j]:
                need = 0
        if need:
            ans += A[i][j]
print(ans)

Submission status: Accepted

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

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

class UnionFind:
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]

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

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False

    def subsetall(self):
        a = []
        for i in range(len(self.table)):
            if self.table[i] < 0:
                a.append((i, -self.table[i]))
        return a

def main():
    n = I()
    a = [LI() for _ in range(n)]
    for i in range(n):
        ai = a[i]
        for j in range(i+1,n):
            aij = ai[j]
            aj = a[j]
            for k in range(n):
                if ai[k] + aj[k] < aij:
                    return -1

    r = 0
    ij = sorted(list(itertools.chain.from_iterable([[[a[i][j], i, j] for j in range(i+1,n)] for i in range(n)])))
    uf = UnionFind(n)
    aa = [[inf] * n for _ in range(n)]
    for i in range(n):
        aa[i][i] = 0
    for k,i,j in ij:
        if uf.union(i,j):
            aa[i][j] = aa[j][i] = k
            r += k
        elif aa[i][j] > k:
            f = True
            for l in range(n):
                if f and aa[l][i] + aa[l][j] <= k:
                    aa[i][j] = aa[j][i] = aa[l][i] + aa[l][j]
                    f = False
                elif aa[l][i] + aa[l][j] < aa[i][j]:
                    aa[i][j] = aa[j][i] = aa[l][i] + aa[l][j]

            if f:
                aa[i][j] = aa[j][i] = k
                r += k

    for i in range(n):
        ai = a[i]
        aai = aa[i]
        for j in range(i+1,n):
            if ai[j] != aai[j]:
                return -1

    return r


print(main())

Submission status: Runtime Error

Solution code:
import itertools
N = int(input())
A = [[int(_) for _ in input().split()] for _ in range(N)]
ans = sum(sum(a) for a in A)
seen = set()
for k, i, j in itertools.product(range(N), repeat=3):
    if (i, j) in seen or k == i or i == j or j == k:
        continue
    elif A[i][j] > A[i][k] + A[j][k]:
        print(-1)
        exit()
    elif A[i][j] == A[i][k] + A[j][k]:
        ans -= A[i][j]
        seen.add((i, k))
        seen.add((k, i))
        seen.add((j, k))
        seen.add((k, j))
    seen.add(i, j)
    seen.add(j, i)
print(ans // 2)

Submission status: Runtime Error

Solution code:
import collections
N = int(input())
A = [[int(_) for _ in input().split()] for _ in range(N)]
B = [_.copy() for _ in A]
d_ij = collections.defaultdict(set)
for i in range(N - 1):
    for j in range(i + 1, N):
        d_ij[A[i][j]].add((i, j))
connected = collections.defaultdict(set)
ans = 0
for k in sorted(d_ij.keys()):
    for i, j in d_ij[k]:
        if i not in connected[j]:
            for p in connected[j]:
                if A[p][i] > A[p][j] + A[j][i]:
                    print(-1)
                    exit()
                elif A[p][i] == A[p][j] + A[j][i]:
                    B[p][i] = B[i][p] = 0
                    connected[p].add(i)
                    connected[i].add(p)
            for q in connected[i]:
                if A[q][j] > A[q][i] + A[i][j]:
                    print(-1)
                    exit()
                elif A[q][j] == A[q][i] + A[i][j]:
                    B[q][j] = B[j][q] = 0
                    connected[q].add(j)
                    connected[j].add(q)
            connected[i].add(j)
            connected[j].add(i)
print(sum(sum(_) for _ in B) // 2)

Submission status: Runtime Error

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

if A == warshall_floyd(A):
    ans = 0
    for i in range(1, N):
        for j in range(0, i):
            if min([A[i][k] + A[k][j] - A[i][j] for k in range(N) if k != i and k != j]) > 0:
                ans += A[i][j]
    print(ans)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
import sys
N=int(input())
len = [list(map(int,input().split())) for t in range (N)]
a=0
n=0
while n < N:
    m=n+1
    while m < N:
        while i < N:
            if i!=n and i!=m:
                if len[n][i]+len[i][m]==len[n][m]:
                    a+=len[n][m] 
                    break
                elif len[n][i]+len[i][m]<len[n][m]:  
                    print(-1)
                    sys.exit()
            i+=1
        m+=1
    n+=1

sum=0
n=0
while n < N:
    m=n+1
    while m < N:
        sum+=len[n][m]
        m+=1
    n+=1

print(sum-a)

Submission status: Runtime Error

Solution code:
import sys
import copy

N = int(input())
table = []
for i in range(N):
    A = [int(j) for j in input().split()]
    table.append(A)
tas = copy.deepcopy(table)
for k in range(N):
    for i in range(N):
        for j in range(N):
            tas[j][i] = min(tas[j][i], tas[j][k] + tas[k][i])

for y in range(N):
    for x in range(y+1, N):
        if A[y][x] != tas[y][x]:
            print(-1)
            sys.exit()
ans = 0
for i in range(N):
    for j in range(i + 1, N):
        flag = True
        for k in range(N):
            if i == k or j == k:
                continue
            if table[j][i] >= table[j][k] + table[k][i]:
                flag = False
        if flag:
            ans += table[j][i]
print(ans)

Submission status: Runtime Error

Solution code:
import sys
import copy
N=int(input())
table=[]
for i in range(N):
    A=[int(j) for j in input().split() ]
    table.append(A)
tas=copy.deepcopy(table)
for k in range(N):
    for i in range(N):
        for j in range(N):
            tas[j][i]=min(tas[j][i],tas[j][k]+tas[k][i])
            
for y in range(N):
    for x in range(N):
        if A[y][x]!=tas[y][x]:
            print(-1)
            sys.exit()
ans=0
for i in range(N):
    for j in range(i+1,N):
        flag =True
        for k in range(N):
            if i==k or j==k:
                continue
            if table[j][i]==table[j][k] +table[k][i]:
                flag = False
        if flag:        
            ans+=table[j][i]
print(ans)

Submission status: Runtime Error

Solution code:
def solve(n, tbl):
    ans = 0
    for i, row_i in enumerate(tbl):
        for j in range(i + 1, n):
            row_j = tbl[j]
            ij = row_i[j]
            mind = min(ik + kj for ik, kj in zip(row_i, row_j) if ik and kj)
            if ij > mind:
                return -1
            if ij < mind:
                ans += ij
    return ans


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

Submission status: Runtime Error

Solution code:
def shortcutable(v, n, x, y):
    a = v[x][y]
    can_prunning = False
    for z in range(n):
        if not z in (x,y):
            b = v[(x,z)]
            c = v[(z,y)]
            #print(x,y,z,a,b,c)
            if (b + c) < a:
                return -1
            if (b + c) == a:
                can_prunning = True
    if can_prunning:
        #print(x,y,a)
        return 0
    else:
        return a

def solve(n, v):
    shortcuts = []
    total = 0
    for x in range(n):
        for y in range(x+1,n):
            result = shortcutable(v, n, x, y)
            if result < 0:
                return -1
            else:
                total += result
            #print(x,y,total)
    
    return total

n = int(input())
v = {}
for i in range(n):
    for j, distance in map(int, input().split(" "))):
        v[(i,j)] = distance

print(solve(n, v))

Submission status: Runtime Error

Solution code:
def shortcutable(v, n, x, y):
    a = v[x][y]
    can_prunning = False
    for z in range(n):
        if not z in (x,y):
            b = v[x][z]
            c = v[z][y]
            #print(x,y,z,a,b,c)
            if (b + c) < a:
                return -1
            if (b + c) == a:
                can_prunning = True
    if can_prunning:
        #print(x,y,a)
        return 0
    else:
        return a

def solve(n, v):
    shortcuts = []
    total = 0
    for x in range(n):
        for y in range(x+1,n):
            result = shortcutable(v, n, x, y)
            if result < 0:
                return -1
            else:
                total += result
            #print(x,y,total)
    
    return total

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

print(solve(v, n))

Submission status: Runtime Error

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

    ans = sum([sum(_A) for _A in A])
    for k in range(n) :
        for i in range(n) :
            for j in range(n) :
                if i == k :
                    break
                elif j == k :
                    continue
                
                d = A[i][k] + A[k][j]
                if d == A[i][j] :
                    ans -= d
                elif d < A[i][j] :
                    print(-1)
                    exit()

    print(ans//2)

main()

Submission status: Runtime Error

Solution code:

N = int(input())

import numpy as np

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

import scipy.sparse.csgraph as csg

G2 = csg.floyd_warshall(G,directed=False)

if np.any(G != G2):
  print(-1)
else:
  G = G2
  T = csg.minimum_spanning_tree(G)
  total = np.sum(T)
  T = csg.floyd_warshall(T,directed=False,overwrite=True)

  import heapq as hq

  remaining = []
  counter = [0]*N

  indices = set()
  for i,j in zip(*np.nonzero(T!=G)):
    indices.add(i)
    counter[i] += 1
    counter[j] += 1
    if i > j:
      remaining.append((G[i,j],i,j))
  
  hq.heapify(remaining)
  while remaining:
    d,i,j = hq.heappop(remaining)
    counter[i] -= 1
    counter[j] -= 1
    if d != T[i,j]:
      T[i,j] = d
      T[j,i] = d
      total += d
      T2 = csg.dijkstra(T,directed=False,indices=list(indices))
      for i,j in enumerate(indices):
        T[j] = T2[i]
    if counter[i] == 0:
      indices.discard(i)
    if counter[j] == 0:
      indices.discard(j)
    

  print(int(total))

Submission status: Runtime Error

Solution code:
N = int(input())
 
import numpy as np
 
G = np.array([list(map(int,input().split())) for i in range(N)])
 
import scipy.sparse.csgraph as csg
 
G2 = csg.floyd_warshall(G,directed=False)
 
if np.any(G != G2):
  print(-1)
else:
  G = G2
  T = csg.minimum_spanning_tree(G)
  total = np.sum(T)
  T = csg.floyd_warshall(T,directed=False,overwrite=True)
 
  import heapq as hq
 
  remaining = []
  delta = T!=G
 
  indices = set()
  for i,j in zip(*np.nonzero(delta)):
    indices.add(i)
    if i > j:
      remaining.append((G[i,j],i,j))
  
  hq.heapify(remaining)
  while remaining:
    d,i,j = hq.heappop(remaining)
    delta[i,j] = True
    delta[j,i] = True
    if d != T[i,j]:
      T[i,j] = d
      T[j,i] = d
      total += d
      T2 = csg.dijkstra(T,directed=False,indices=list(indices))
      for i,j in enumerate(indices):
        T[j] = T2[i]
    
    if np.all(delta[i]):
      indices.discard(i)
    if np.all(delta[j]):
      indices.discard(j)
 
  print(int(total))

Submission status: Runtime Error

Solution code:
# coding: utf-8
import itertools
import heapq


def II(): return int(input())
def ILI(): return list(map(int, input().split()))


def read():
    N = II()
    matrix = [ILI() for __ in range(N)]
    return N, matrix


def check_first(matrix):
    t_matrix = list(map(list, zip(*matrix)))
    for i, (row, t_row) in enumerate(zip(matrix, t_matrix)):
        if row[i] != 0:
            return False
        for ele, t_ele in zip(row, t_row):
            if ele != t_ele:
                return False
    return True


def solve(N, matrix):
    if check_first(matrix) is False:
        return -1
    ano_matrix = [[10 ** 9] * N for __ in range(N)]
    for a, b, c in itertools.product(range(N), repeat=3):
        new_length = matrix[a][b] + matrix[b][c]
        ano_matrix[a][c] = min(ano_matrix[a][c], new_length)
    for row, ano_row in zip(matrix, ano_matrix):
        for ele, ano_ele in zip(row, ano_row):
            if ele != ano_ele:
                return -1

    # Prim 法で最小全域木を求める
    ans = 0
    s_nodes = set()
    s_nodes.add(0)
    while len(s_nodes) < N:
        other_nodes = set(range(N)) - s_nodes
        len_edge = 10 * 9
        f_node = None
        t_node = None
        for from_node in s_nodes:
            for to_node in other_nodes:
                if matrix[from_node][to_node] < len_edge:
                    f_node = from_node
                    t_node = to_node
        s_nodes.add(t_node)
        ans += matrix[f_node][t_node]
    return ans


def main():
    params = read()
    print(solve(*params))


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:

N = int(input())

import numpy as np

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

import scipy.sparse.csgraph as csg

G2 = csg.floyd_warshall(G,directed=False)

if np.any(G != G2):
  print(-1)
else:
  G = G2
  T = csg.minimum_spanning_tree(G)
  total = np.sum(T)
  T = csg.floyd_warshall(T,directed=False,overwrite=True)

  import heapq as hq

  remaining = []
  delta = T!=G

  indices = set()
  for i,j in zip(*np.nonzero(delta)):
    indices.add(i)
    if i > j:
      remaining.append((G[i,j],i,j))
  
  hq.heapify(remaining)
  while remaining:
    d,i,j = hq.heappop(remaining)
    delta[i,j] = True
    delta[j,i] = True
    if d != T[i,j]:
      T[i,j] = d
      T[j,i] = d
      total += d
      T2 = csg.dijkstra(T,directed=False,indices=list(indices))
      for i,j in enumerate(indices):
        T[j] = T2[i]
    
    if np.all(delta[i]):
      indices.remove(i)
    if np.all(delta[j]):
      indices.remove(j)

  print(int(total))

Submission status: Runtime Error

Solution code:
# coding: utf-8
import itertools
import array
import collections
import heapq


def II(): return int(input())
def ILI(): return list(map(int, input().split()))


def read():
    N = II()
    matrix = [ILI() for __ in range(N)]
    return N, matrix


def check_first(matrix):
    t_matrix = list(map(list, zip(*matrix)))
    for i, (row, t_row) in enumerate(zip(matrix, t_matrix)):
        if row[i] != 0:
            return False
        for ele, t_ele in zip(row, t_row):
            if ele != t_ele:
                return False
    return True


def solve(N, matrix):
    if check_first(matrix) is False:
        return -1
    ano_matrix = [[10 ** 9] * N for __ in range(N)]
    for a, b, c in itertools.product(range(N), repeat=3):
        new_length = matrix[a][b] + matrix[b][c]
        ano_matrix[a][c] = min(ano_matrix[a][c], new_length)
    for row, ano_row in zip(matrix, ano_matrix):
        for ele, ano_ele in zip(row, ano_row):
            if ele != ano_ele:
                return -1

    # Prim 法で最小全域木を求める
    ans = 0
    s_nodes = set()
    s_nodes.add(0)
    while len(s_nodes) < N:
        other_nodes = set(range(N)) - s_nodes
        len_edge = 10 * 9
        f_node = None
        t_node = None
        for from_node in s_nodes:
            for to_node in other_nodes:
                if matrix[from_node][to_node] < len_edge:
                    f_node = from_node
                    t_node = to_node
        s_nodes.add(t_node)
        ans += matrix[f_node][t_node]
    return ans


def main():
    params = read()
    print(solve(*params))


if __name__ == "__main__":
    main()