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: Wrong Answer

Solution code:
"""from collections import *
from itertools import *
from bisect import *
from heapq import *

import math
from fractions import gcd"""
from heapq import*
N=int(input())
A=[list(map(int,input().split())) for i in range(N)]
data=[[] for i in range(N)]

for i in range(N):
    for m in range(N):
        if i==m:
            continue
        data[i].append([m,A[i][m],i*300+m])

"""

visited={0}
stack=[]
dic={}
for p,c,i in data[0]:
    if c in dic:
        dic[c].append([p,i])
    else:
        dic[c]=[[p,i]]
    stack.append(c)
heapify(stack)
value=0
usedpath=set()
while stack:
    m=heappop(stack)
    a,i=dic[m].pop()
    if not a in visited:
        visited.add(a)
        usedpath.add(i)
        value+=m
        for p,c,i in data[a]:
            if not p in visited:
                if c in dic:
                    dic[c].append([p,i])
                else:
                    dic[c]=[[p,i]]
                heappush(stack,c)
"""
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

Alst=[[A[i][m],i,m] for i in range(N) for m in range(N)]
Alst=sorted(Alst,key=lambda x:x[0])
uf=UnionFind(N)
usedpath=set()
value=0

for B,i,m in Alst:
    if not uf.same(i,m):
        uf.union(i,m)
        usedpath.add(i*300+m)
        value+=B
        if uf.group_count()==1:
            break




idle_max=10**18
d=[[idle_max for i in range(N)] for m in range(N)]
for i in range(N):
    d[i][i]=0
for i in usedpath:
    i,m=i//300,i%300
    d[i][m]=A[i][m]
    d[m][i]=A[m][i]

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 B,i,m in Alst:
    if d[i][m]<A[i][m]:
        print(-1)
        exit()
    if d[i][m]>A[i][m]:
        d[i][m]=A[i][m]
        d[m][i]=A[m][i]
        value+=A[i][m]

        for i1 in range(N):
            for j in range(N):
                 d[i1][j] = min(d[i1][j], d[i1][i] + d[i][j])
                 d[i1][j] = min(d[i1][j], d[i1][m] + d[m][j])


print(value)

Submission status: Wrong Answer

Solution code:
"""from collections import *
from itertools import *
from bisect import *
from heapq import *

import math
from fractions import gcd"""
from heapq import*
N=int(input())
A=[list(map(int,input().split())) for i in range(N)]
data=[[] for i in range(N)]

for i in range(N):
    for m in range(N):
        if i==m:
            continue
        data[i].append([m,A[i][m],i*300+m])



visited={0}
stack=[]
dic={}
for p,c,i in data[0]:
    if c in dic:
        dic[c].append([p,i])
    else:
        dic[c]=[[p,i]]
    stack.append(c)
heapify(stack)
value=0
usedpath=set()
while stack:
    m=heappop(stack)
    a,i=dic[m].pop()
    if not a in visited:
        visited.add(a)
        usedpath.add(i)
        value+=m
        for p,c,i in data[a]:
            if not p in visited:
                if c in dic:
                    dic[c].append([p,i])
                else:
                    dic[c]=[[p,i]]
                heappush(stack,c)

idle_max=10**18
d=[[idle_max for i in range(N)] for m in range(N)]
for i in range(N):
    d[i][i]=0
for i in usedpath:
    i,m=i//300,i%300
    d[i][m]=A[i][m]
    d[m][i]=A[m][i]

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])
Alst=[[A[i][m],i,m] for i in range(N) for m in range(N)]
Alst=sorted(Alst,key=lambda x:x[0])
for B,i,m in Alst:
    if d[i][m]<A[i][m]:
        print(-1)
        exit()
    if d[i][m]>A[i][m]:
        d[i][m]=A[i][m]
        d[m][i]=A[m][i]
        value+=A[i][m]

        for i1 in range(N):
            for j in range(N):
                 d[i1][j] = min(d[i1][j], d[i1][i] + d[i][j])
                 d[i1][j] = min(d[i1][j], d[i1][m] + d[m][j])


print(value)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 1000000007

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



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

# 最短性の確認
for i in range(n):
    for j in range(n):
        for k in range(n):
            if dist[j][k] > dist[j][i] + dist[i][k]:
                print(-1)
                exit()
            if (i - j) * (j - k) * (k - i) and dist[j][k] == dist[j][i] + dist[i][k]:
                ans -= dist[j][k]

print(ans//2)

Submission status: Wrong Answer

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
n=int(input())
table=[]
for i in range(n):
  table.append([int(i) for i in input().split()])

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
table2=warshall_floyd(table)

Chk=True
for i in range(n):
  for j in range(n):
    if table[i][j]==table2[i][j]:
      continue
    else:
      Chk=False
ans=0
for i in range(n):
  for j in range(i+1,n):
    C=True
    for k in range(n):
      if k==i or k==j:
        continue
      else:
        if table[i][k]+table[k][j]==table[i][j]:
          C=False
    if C:
      ans+=table[i][j]
print(ans if Chk else -1)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [list(map(int,input().split())) for _ in range(N)]
cnt = 0
for i in range(N):
    for j in range(N):
        cnt += A[i][j]
flg = 0
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]:
                flg = -1
                break
            elif A[i][j]==A[i][k]+A[k][j] and A[i][k]*A[k][j]>0:
                cnt -= A[i][j]
        if flg==-1:break
    if flg==-1:break
if flg==-1:
    print(-1)
else:
    print(cnt//2)

Submission status: Wrong Answer

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

def solve(N: int, A: "List[List[int]]"):
    for i in range(N-1):
        for j in range(i+1,N):
            for k in range(N):
                if i == k or j == k or A[i][k] == 0 or A[j][k] == 0:
                    continue
                
                if A[i][j] == A[i][k]+A[j][k]:
                    A[i][j] = 0
                    A[j][i] = 0
                    break
                elif A[i][j] > A[i][k]+A[j][k]:
                    print(-1)
                    return
    
    answer = 0
    for i in range(N-1):
        for j in range(i+1,N):
            answer += A[i][j]
    print(answer)
    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: Wrong Answer

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

def solve(N: int, A: "List[List[int]]"):
    for i in range(N-1):
        for j in range(i+1,N):
            for k in range(N):
                if i == k or j == k or A[i][k] == 0 or A[j][k] == 0:
                    continue
                
                if A[i][j] == A[i][k]+A[j][k]:
                    A[i][j] = 0
                    A[j][i] = 0
                    break
                elif A[i][j] > A[i][k]+A[j][k]:
                    print(-1)
                    return
    
    answer = 0
    for i in range(N):
        answer += sum(A[i])
    print(answer//2)

    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: Wrong Answer

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

def solve(N: int, A: "List[List[int]]"):
    for i in range(N-1):
        for j in range(i+1,N):
            for k in range(N):
                if i == k or j == k or A[i][k] == 0 or A[j][k] == 0:
                    continue
                
                if A[i][j] == A[i][k]+A[j][k]:
                    A[i][j] = 0
                    A[j][i] = 0
                elif A[i][j] > A[i][k]+A[j][k]:
                    print(-1)
                    return
    
    answer = 0
    for i in range(N):
        answer += sum(A[i])
    print(answer//2)

    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: Wrong Answer

Solution code:
import sys
import math
import fractions
import itertools
from collections import deque
import copy
import heapq
import bisect


def warshall_floyd(d):
    """
    d[i][l]がi→lへのコストを示す隣接行列
    結果としてd[i][l]はi→lへの最短コストになる。
    """
    for i in range(len(d)):
        for l in range(len(d)):
            for k in range(len(d)):
                d[l][k] = min(d[l][k], d[l][i] + d[i][k])
    return d


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

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

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

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

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque
 
sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7
 
DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]
 
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N = I()
    G = []
    for _ in range(N):
        a = LI()
        G.append(a)
    dp = copy.deepcopy(G)
    for i in range(N):
        for j in range(N):
            for k in range(N):
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
 
    if dp != G:
        print(-1)
        return
 
    for i in range(N):
        for j in range(N):
            for k in range(N):
                if i == j:
                    continue
                if j == k:
                    continue
                if i == k:
                    continue
                if dp[i][k] == 0 or dp[i][j] == 0 or dp[j][k] == 0:
                    continue
                if dp[i][j] == dp[i][k] + dp[k][j]:
                    dp[i][j] = 0
                    dp[j][i] = 0
    cnt = 0
    for i in range(N):
        for j in range(N):
            cnt += dp[i][j]
    print(cnt // 2)
main()

Submission status: Wrong Answer

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

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

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

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

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

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

Submission status: Wrong Answer

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

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

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

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

                # 真の最短距離
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])

    for i in range(N):
        for j in range(N):
            if dp[i][j] < G[i][j]:
                return

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

Submission status: Wrong Answer

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

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

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

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

                # 真の最短距離
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
    for i in range(N):
        for j in range(N):
            if dp[i][j] < G[i][j]:
                return

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

Submission status: Wrong Answer

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

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

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

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N = I()
    G = []
    for _ in range(N):
        a = LI()
        G.append(a)
    dp = copy.deepcopy(G)
    for i in range(N):
        for j in range(N):
            for k in range(N):
                # 真の最短距離
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
    print(dp)
    for i in range(N):
        for j in range(N):
            if dp[i][j] < G[i][j]:
                print(-1)
                return

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

Submission status: Wrong Answer

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

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

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

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N = I()
    G = []
    for _ in range(N):
        a = LI()
        G.append(a)
    dp = copy.deepcopy(G)
    for i in range(N):
        for j in range(N):
            for k in range(N):
                # 真の最短距離
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
    for i in range(N):
        for j in range(N):
            if dp[i][j] < G[i][j]:
                print(-1)
                return

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

Submission status: Wrong Answer

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

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

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

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N = I()
    G = []
    for _ in range(N):
        a = LI()
        G.append(a)
    dp = copy.deepcopy(G)
    for i in range(N):
        for j in range(N):
            for k in range(N):
                # 真の最短距離
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
    for i in range(N):
        for j in range(N):
            if G[i][j] < dp[i][j]:
                print(-1)
                return

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

Submission status: Wrong Answer

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

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

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

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N = I()
    G = []
    for _ in range(N):
        a = LI()
        G.append(a)
    dp = copy.deepcopy(G)
    for i in range(N):
        for j in range(N):
            for k in range(N):
                # 真の最短距離
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])

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

Submission status: Wrong Answer

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

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

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

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N = I()
    G = []
    for _ in range(N):
        a = LI()
        G.append(a)
    dp = copy.deepcopy(G)
    for i in range(N):
        for j in range(N):
            for k in range(N):
                # 真の最短距離
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])

    for i in range(N):
        for j in range(N):
            for k in range(N):
                if i == j or j == k or k == j:
                    continue
                if dp[i][k] == 0 or dp[i][j] == 0 or dp[j][k] == 0:
                    continue
                if G[i][j] > dp[i][k] + dp[k][j]:
                    # 入力がおかしい
                    print(-1)
                    return
                if G[i][j] == dp[i][k] + dp[k][j]:
                    # i->jは要らない
                    dp[i][j] = 0
                    dp[j][i] = 0
    cnt = 0
    for i in range(N):
        for j in range(N):
            cnt += dp[i][j]
    print(cnt // 2)
main()

Submission status: Wrong Answer

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

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

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

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

    for i in range(N):
        for j in range(N):
            for k in range(N):
                if i == j or j == k or k == j:
                    continue
                if dp[i][k] == 0 or dp[i][j] == 0 or dp[j][k] == 0:
                    continue
                if G[i][j] > dp[i][k] + dp[k][j]:
                    print(-1)
                    return
                if G[i][j] == dp[i][k] + dp[k][j]:
                    dp[i][j] = 0
                    dp[j][i] = 0
    cnt = 0
    for i in range(N):
        for j in range(N):
            cnt += dp[i][j]
    print(cnt // 2)
main()

Submission status: Wrong Answer

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

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

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

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

    for i in range(N):
        for j in range(N):
            for k in range(N):
                if i == j or j == k or k == j:
                    continue
                if dp[i][k] == 0 or dp[i][j] == 0 or dp[j][k] == 0:
                    continue
                if dp[i][j] > dp[i][k] + dp[k][j]:
                    print(-1)
                    return
                if dp[i][j] == dp[i][k] + dp[k][j]:
                    dp[i][j] = 0
                    dp[j][i] = 0
    cnt = 0
    for i in range(N):
        for j in range(N):
            cnt += dp[i][j]
    print(cnt // 2)
main()