Buggy python submission (verdict: Runtime Error):
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))


Fixed submission:
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), default=float('inf'))
            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))

Buggy python submission (verdict: Time Limit Exceeded):
def solve(n, tbl):
    for k, tbl_k in enumerate(tbl):
        for i, tbl_i in enumerate(tbl):
            ik = tbl_i[k]
            if ik == 0:
                continue
            for j in range(i + 1, n):
                ij, kj = tbl_i[j], tbl_k[j]
                if ij == 0 or kj == 0:
                    continue
                if ij > ik + kj:
                    return -1
                if ij == ik + kj:
                    tbl_i[j] = 0
    return sum(sum(row[i + 1:]) for i, row in enumerate(tbl))


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


Fixed submission:
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), default=float('inf'))
            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))

Buggy python submission (verdict: Time Limit Exceeded):
import copy


def solve(n, tbl):
    for k, tbl_k in enumerate(tbl):
        for i, tbl_i in enumerate(tbl):
            ik = tbl_i[k]
            if ik == 0:
                continue
            for j in range(i + 1, n):
                ij, kj = tbl_i[j], tbl_k[j]
                if ij == 0 or kj == 0:
                    continue
                if ij > ik + kj:
                    return -1
                if ij == ik + kj:
                    tbl[i][j] = 0
    return sum(sum(row[i + 1:]) for i, row in enumerate(tbl))


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


Fixed submission:
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), default=float('inf'))
            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))

Buggy python submission (verdict: Time Limit Exceeded):
import copy


def solve(n, tbl):
    use = copy.deepcopy(tbl)
    for k in range(n):
        for i in range(n):
            if i == k:
                continue
            for j in range(i + 1, n):
                if j == k:
                    continue
                ij, ik, kj = tbl[i][j], tbl[i][k], tbl[k][j]
                if ij > ik + kj:
                    return -1
                if ij == ik + kj:
                    use[i][j] = 0
    ans = 0
    for i, row in enumerate(use):
        ans += sum(row[i + 1:])

    return sum(sum(row[i + 1:]) for i, row in enumerate(use))


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


Fixed submission:
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), default=float('inf'))
            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))

Buggy python submission (verdict: Time Limit Exceeded):
from scipy.sparse.csgraph import dijkstra

n = int(input())
dists = []
for i in range(n):
    ds = map(int, input().split())
    for j, c in enumerate(ds):
        if i >= j:
            continue
        dists.append((c, i, j))
dists.sort()

links = [[0] * n for _ in range(n)]
ans = 0

for c, i, j in dists:
    graph = dijkstra(links, directed=False, indices=i)
    if graph[j] < c:
        break
    elif graph[j] > c:
        links[i][j] = c
        links[j][i] = c
        ans += c

graph = dijkstra(links, directed=False)
for c, i, j in dists:
    if graph[i][j] != c:
        print(-1)
        break
else:
    print(ans)


Fixed submission:
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), default=float('inf'))
            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))

Buggy python submission (verdict: Time Limit Exceeded):
from scipy.sparse.csgraph import shortest_path, dijkstra


class UnionFind:
    def __init__(self, n):
        self.table = [-1] * n

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

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

    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2


n = int(input())
dists = []
for i in range(n):
    ds = map(int, input().split())
    for j, c in enumerate(ds):
        if i >= j:
            continue
        dists.append((c, i, j))
dists.sort()

uf = UnionFind(n)
links = [[0] * n for _ in range(n)]
ans = 0

for c, i, j in dists:
    if not uf.find(i, j):
        links[i][j] = c
        links[j][i] = c
        ans += c
        uf.union(i, j)
        continue
    graph = dijkstra(links, directed=False, indices=i)
    if graph[j] < c:
        break
    elif graph[j] > c:
        links[i][j] = c
        links[j][i] = c
        ans += c

graph = dijkstra(links, directed=False)
for c, i, j in dists:
    if graph[i][j] != c:
        print(-1)
        break
else:
    print(ans)


Fixed submission:
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), default=float('inf'))
            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))

Buggy python submission (verdict: Time Limit Exceeded):
from scipy.sparse.csgraph import dijkstra


class UnionFind:
    def __init__(self, n):
        self.table = [-1] * n

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

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

    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2


n = int(input())
dists = []
for i in range(n):
    ds = map(int, input().split())
    for j, c in enumerate(ds):
        if i >= j:
            continue
        dists.append((c, i, j))
dists.sort()

uf = UnionFind(n)
links = [[0] * n for _ in range(n)]

for c, i, j in dists:
    if not uf.find(i, j):
        links[i][j] = c
        links[j][i] = c
        uf.union(i, j)
        continue
    graph = dijkstra(links, directed=False, indices=[i, j])
    if graph[0][j] < c:
        break
    elif graph[0][j] > c:
        links[i][j] = c
        links[j][i] = c

graph = dijkstra(links, directed=False)
for c, i, j in dists:
    if graph[i][j] != c:
        print(-1)
        break
else:
    print(sum(sum(l) for l in links) // 2)


Fixed submission:
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), default=float('inf'))
            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))