Submission #1691853

---

Source Code Expand

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)]
            if b >= a:
                continue
            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 enumerate(map(int, input().split(" "))):
        v[(i,j)] = distance

print(solve(n, v))

Submission Info

Judge Result