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: Time Limit Exceeded

Solution code:
#D問題
import copy

N = int(input())
A = [list(map(int,input().split())) for i in range(N)]
G = copy.deepcopy(A)
whole = 0
for i in range(N):
    for j in range(N):
        whole+=A[i][j]


#print(A,G)
#warshall_floyd法
def warshall_floyd(dist):
    global N
    #dist[i][j]: iからjへの最短距離
    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])

warshall_floyd(G)
#print(A,G)

flag = 0
ans = 0
for i in range(N):
    for j in range(N):
        if A[i][j] != G[i][j]:
            flag = 1
        else:
            for k in range(N):
                if k != i and k != j:
                    #print(G[i][j],G[i][k]+G[k][j])
                    if G[i][j] == G[i][k] + G[k][j]:
                        ans+=A[i][j]
                        #print(A[i][j])
                        break
                
            
if flag == 1:
    print(-1)
else:
    print((whole-ans)//2)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = []
for i in range(N):
  As = list(map(int, input().split()))
  A.append(As)
r = 0
for i in range(N):
  for j in range(i+1, N):
    ok = False
    for k in range(N):
      if A[i][j] > A[i][k]+A[k][j]:
        print(-1)
        exit()
      if A[i][j] == A[i][k]+A[k][j] and k != i and k != j:
        ok = True
    if not(ok):
      r += A[i][j]
print(r)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = []
r = 0
for i in range(N):
  As = list(map(int, input().split()))
  A.append(As)
  r += sum(As)
#print(r)
G = [[-1]*N for i in range(N)]
for i in range(N):
  for j in range(N):
    ok = False
    for k in range(N):
      if A[i][j] > A[i][k]+A[k][j]:
        print(-1)
        exit()
      if A[i][j] == A[i][k]+A[k][j] and k != i and k != j:
        ok = True
    if ok:
      r -= A[i][j]
r = r//2
print(r)

Submission status: Time Limit Exceeded

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

flag = True
for k in range(N):
	for i in range(N):
		for j in range(i):
			if A[i][j] > A[i][k] + A[k][j]:
				flag = False
				break
		if not flag:
			break
	if not flag:
		break

ans = 0
if flag:
	for i in range(N):
		for j in range(i):
			flag = True
			for k in range(N):
				if k != i and k != j:
					if A[i][j] == A[i][k] + A[k][j]:
						flag = False
						break
			if flag:
				ans += A[i][j]
	print(ans)
else:
	print(-1)

Submission status: Time Limit Exceeded

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):
        is_edge = True
        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のノードを直接結ぶものではない
                is_edge = False
        if is_edge:
            ans += A[i][j]

print(ans)

Submission status: Time Limit Exceeded

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):
    for j in range(N):
        is_edge = True
        for k in range(N):
            if i == j or i == k or j == k:
                continue
            if A[i][j] == A[i][k] + A[k][j]: # A[i][j]はiとjのノードを直接結ぶものではない
                is_edge = False
        if is_edge:
            ans += A[i][j]

print(ans//2) # A[i][j]とA[j][i]が重複してたされているから２で割る

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n = int(input())
a = np.array([list(map(int, input().split(" "))) for i in range(n)])
ans = 0

edges = np.ones((n, n))

class BadBoard(Exception):
    pass

try:
    for i in range(n):
        for j in range(n):
            path = a[i][j]
            for k in range(n):
                if a[i][k] + a[k][j] < a[i][j]:
                    raise BadBoard
                elif a[i][k] + a[k][j] == a[i][j] and i != k and j != k:
                    edges[i][j] = 0

    print(int(np.sum(edges * a) // 2))

except BadBoard:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=[list(map(int,input().split())) for i in range(N)]
r=0
for i,aa in enumerate(A):
    for j,a in enumerate(aa[i+1:]):
        f=1
        j+=i+1
        for k in range(N):
            if k==i or k==j:
                continue
            if a>A[i][k]+A[k][j]:
                f=r=-1
                break
            if a==A[i][k]+A[k][j]:
                f=0
                break
        if f==1:
            r+=a
        elif f==-1:
            break
    if r<0:
        break
print(r)

Submission status: Time Limit Exceeded

Solution code:
import copy
ans=0
n=int(input())
l=[list(map(int,input().split())) for _ in range(n)]
o=copy.deepcopy(l)

for k in range(n):
  for i in range(n):
    for j in range(n):
      if l[i][j]>l[i][k]+l[k][j]:
        print(-1)
        exit()
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 o[i][j]==o[i][k]+o[k][j]:
            o[i][j]=float("inf")
for i in range(n):
    for j in range(n):
        if o[i][j] != float("inf") :
            ans+=o[i][j]
print(int(ans/2))

Submission status: Time Limit Exceeded

Solution code:
import copy
ans=0
n=int(input())
l=[list(map(int,input().split())) for _ in range(n)]
o=copy.deepcopy(l)

for k in range(n):
  for i in range(n):
    for j in range(n):
      if l[i][j]>l[i][k]+l[k][j]:
        print(-1)
        exit()
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 o[i][j]==o[i][k]+o[k][j]:
            o[i][j]=float("inf")
for i in range(n):
    for j in range(n):
        if o[i][j] != float("inf") :
            ans+=o[i][j]
print(int(ans/2))

Submission status: Time Limit Exceeded

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([d[i][k] + d[k][j]
                    for k in range(N) if k not in (i, j)], default=inf)
        if d[i][j] > dmin:
            print(-1)
            exit()
        if d[i][j] != dmin:
            ans += d[i][j]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import heapq
from bisect import bisect_left
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: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import heapq
from bisect import bisect_left
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 shortestPath(g: Graph, s: int):
    """ グラフgにおいて、始点sから各頂点への最短路を求める
    引数
    g: グラフ, s: 始点
    返り値
    dist: 始点からの距離が格納されたリスト
    prev: 始点から最短経路で移動する場合、各頂点に至る前の頂点のリスト
    """
    dist = [INF]*g.N
    dist[s] = 0

    prev = [None]*g.N
    Q = []
    heapq.heappush(Q, (dist[s], s))

    while len(Q) > 0:
        _, u = heapq.heappop(Q)
        for v, w in g.E[u]:
            if dist[v] > dist[u] + w:
                dist[v] = dist[u] + w
                prev[v] = u
                heapq.heappush(Q, (dist[v], v))
    return dist, prev


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):
            g.remove_edge([i, j])
            dist, prev = shortestPath(g, i)
            if dist[j] < A[i][j]:
                print(-1)
                return
            elif dist[j] == A[i][j]:
                continue
            else:
                counter += A[i][j]
            g.add_edge([i, j, A[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: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import heapq
from bisect import bisect_left
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 shortestPath(g: Graph, s: int):
    """ グラフgにおいて、始点sから各頂点への最短路を求める
    引数
    g: グラフ, s: 始点
    返り値
    dist: 始点からの距離が格納されたリスト
    prev: 始点から最短経路で移動する場合、各頂点に至る前の頂点のリスト
    """
    dist = [INF]*g.N
    dist[s] = 0

    prev = [None]*g.N
    Q = []
    heapq.heappush(Q, (dist[s], s))

    while len(Q) > 0:
        _, u = heapq.heappop(Q)
        for v, w in g.E[u]:
            if dist[v] > dist[u] + w:
                dist[v] = dist[u] + w
                prev[v] = u
                heapq.heappush(Q, (dist[v], v))
    return dist, prev


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

    # 最短路が小さい順に処理します。
    shortests = []
    for i in range(N):
        for j in range(i+1, N):
            shortests.append([A[i][j], i, j])
    shortests.sort()

    counter = 0
    # Graph
    g = Graph(N)
    for debug, (path, from_, to_) in enumerate(shortests):
        # print("START:", from_, to_, path)
        # print(g.E)
        dist, prev = shortestPath(g, from_)
        # print("dist:", dist)
        if dist[to_] < path:
            # すでにより短い路が存在しているケース
            print(-1)
            return
        elif dist[to_] == path:
            # 現状ですでに満たしているケース
            continue
        else:
            g.add_edge([from_, to_, path])
            counter += path

        # if dist[to_] == INF:    # 連結していない場合
        #     # 新たにつなげるべき枝は、貪欲に枝が小さくて済む場所
        #     mi, m = from_, 0
        #     for i, d in enumerate(dist):
        #         if m < d < path:
        #             m = d
        #             mi = i

        #     # ただし逆向きにも見てやる必要がある。
        #     rev_dist, rev_prev = shortestPath(g, to_)
        #     mmi, mm = to_, 0
        #     for i, d in enumerate(rev_dist):
        #         if mm < d < path:
        #             mm = d
        #             mmi = i
        #     if path-mm < path-m:
        #         w = path-mm
        #         f_ = mmi
        #         t_ = from_
        #     else:
        #         w = path-m
        #         f_ = mi
        #         t_ = to_
        #         print("EDGE:", f_, t_, w)
        #     g.add_edge([f_, t_, w])

        #     counter += path-m

        # else:                   # 連結している場合
        #     # 新たにつなげるべき枝は、貪欲に枝が小さくて済む場所
        #     mi, m = from_, 0
        #     for i, d in enumerate(dist):
        #         if m < d < path:
        #             m = d
        #             mi = i
        #     print("EDGE:", mi, to_, path-m)
        #     g.add_edge([mi, to_, path-m])
        #     counter += path-m
        # # print(g.E)
        # # if debug == 3:
        #     # break

    # print("FINAL:", g.E)
    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: Time Limit Exceeded

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

egde = []
for u in range(n):
    for v in range(u):
        egde.append([adjacency_list[u][v], u, v])
egde.sort()
ans = 0
INF = 10 ** 10
for d, u, v in egde:
    d2 = INF
    for w in range(n):
        if w == u or w == v:
            continue
        d2 = min(d2, adjacency_list[u][w] + adjacency_list[w][v])
    if d < d2:
        ans += d
    elif d > d2:
        print(-1)
        exit()

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
adjacency_list = [list(map(int, input().split())) for i in range(n)]
egde = []
for u in range(n):
    for v in range(u):
        egde.append([adjacency_list[u][v], u, v])
egde.sort()

ans = 0
for d, u, v in egde:
    for w in range(n):
        d2 = adjacency_list[u][w] + adjacency_list[w][v]
        if d == d2:
            if w == u or w == v:
                continue
            break
        elif d > d2:
            print(-1)
            exit()
    else:
        ans += d

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
adjacency_list = [list(map(int, input().split())) for i in range(n)]
egde = []
for u in range(n):
    for v in range(u):
        egde.append([adjacency_list[u][v], u, v])
egde.sort()

ans = 0
for d, u, v in egde:
    for w in range(n):
        d2 = adjacency_list[u][w] + adjacency_list[w][v]
        if d == d2:
            if w == u or w == v:
                continue
            break
        elif d > d2:
            print(-1)
            exit()
    else:
        ans += d

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
adjacency_list = [list(map(int, input().split())) for i in range(n)]
egde = []
for u in range(n):
    for v in range(u):
        egde.append([adjacency_list[u][v], u, v])
egde.sort()

ans = 0
for d, u, v in egde:
    for w in range(n):
        if w == u or w == v:
            continue
        d2 = adjacency_list[u][w] + adjacency_list[w][v]
        if d == d2:
            break
        elif d > d2:
            print(-1)
            exit()
    else:
        ans += d

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
adjacency_list = [list(map(int, input().split())) for i in range(n)]
egde = []
for u in range(n):
    for v in range(u):
        egde.append([adjacency_list[u][v], u, v])
egde.sort()

ans = 0
for d, u, v in egde:
    for w in range(n):
        if w == u or w == v:
            continue
        d2 = adjacency_list[u][w] + adjacency_list[w][v]
        if d > d2:
            print(-1)
            exit()
        elif d == d2:
            break
    else:
        ans += d

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
adjacency_list = [list(map(int, input().split())) for i in range(n)]
egde = []
for u in range(n):
    for v in range(u):
        egde.append([adjacency_list[u][v], u, v])
egde.sort()

ans = 0
for d, u, v in egde:
    for w in range(n):
        if w == u or w == v:
            continue
        if d > adjacency_list[u][w] + adjacency_list[w][v]:
            print(-1)
            exit()
        elif d == adjacency_list[u][w] + adjacency_list[w][v]:
            break
    else:
        ans += d

print(ans)

Submission status: Time Limit Exceeded

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

ans = sum([sum(line) for line in graph]) // 2
for a in range(n):
    for b in range(n):
        if a == b:
            break
        for c in range(n):
            if a == c or b == c:
                continue
            if graph[a][b] > graph[a][c] + graph[c][b]:
                print(-1)
                exit()
            elif graph[a][b] == graph[a][c] + graph[c][b]:
                ans -= graph[a][b]

print(ans)

Submission status: Time Limit Exceeded

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

ans = sum([sum(line) for line in graph])
for a in range(n):
    for b in range(n):
        if a == b:
            continue
        for c in range(n):
            if a == c or b == c:
                continue
            if graph[a][b] > graph[a][c] + graph[c][b]:
                print(-1)
                exit()
            elif graph[a][b] == graph[a][c] + graph[c][b]:
                ans -= graph[a][b]

print(ans // 2)

Submission status: Time Limit Exceeded

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

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

d[N][N]=0

P=list( permutations(range(1,N+1),3) )

for i,j,k in P:
	a=d[i][j]
	b=d[j][k]
	c=d[i][k]	
	if a+b<c:
		print -1
		quit()
	if a+b==c and hen[i][k]!=0:
		ans-=c
		hen[i][k]=0
		hen[k][i]=0

print ans

Submission status: Time Limit Exceeded

Solution code:
import sys
from heapq import heappush, heappop
from collections import defaultdict

N=input()
nl=[ [ ] for i in range(N+1) ] 

hq=[]
for i in range(N):
	L=map(int, sys.stdin.readline().split())
	for j in range(i+1,N):
		heappush( hq, (L[j],i+1,j+1) )


ans=0
for n in range(N-1):
	cost,x,y=heappop( hq )
	nl[x].append( (cost,y) )
	nl[y].append( (cost,x) )
	ans+=cost



def dij(start,end):
	#d=[ float("inf")  for i in range(N+1) ] 
	d=defaultdict(lambda: float("inf")) 
	d[start]=0
	q=[]
	heappush( q, start )	#u: chouten
	while q:
		fro=heappop(q)
		for cost, to in nl[fro]:
			alt=d[fro]+cost
			if d[to]>alt:
				d[to]=alt
				heappush(q,to)
	return d[end]

while hq:
	input_cost,x,y=heappop( hq )
	cost=dij(x,y)
	if cost < input_cost:
		print -1
		quit()
	elif input_cost<cost:
		nl[x].append( (input_cost,y) )
		nl[y].append( (input_cost,x) )
		ans+=input_cost

print ans

Submission status: Time Limit Exceeded

Solution code:
import sys
from heapq import heappush, heappop
from collections import defaultdict

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

hq=[]
for i in range(N):
	L=map(int, sys.stdin.readline().split())
	for j in range(i+1,N):
		heappush( hq, (L[j],i+1,j+1) )


ans=0
for n in range(N-1):
	cost,x,y,=heappop( hq )
	nl[x][y]=cost
	nl[y][x]=cost
	ans+=cost

def dij(start,end):
	d=defaultdict(lambda: float("inf")) 
	d[start]=0
	q=[]
	heappush( q, start )	#u: chouten

	while q:
		fro=heappop(q)
		for to in range(1,N+1):
			if nl[fro][to]==float("inf"): continue
			alt=d[fro]+nl[fro][to]
			if d[to]>alt:
				d[to]=alt
				heappush(q,to)
	return d[end]


while hq:
	cost,x,y=heappop( hq )
	d=dij(x,y)

	if d<cost:
		print -1
		quit()
	elif cost<d:
		ans+=cost
	nl[x][y]=cost
	nl[y][x]=cost


print ans

Submission status: Time Limit Exceeded

Solution code:
import sys
from heapq import heappush, heappop
from collections import defaultdict

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

hq=[]
for i in range(N):
	L=map(int, sys.stdin.readline().split())
	for j in range(i+1,N):
		heappush( hq, (L[j],i+1,j+1) )


ans=0
for n in range(N-1):
	cost,x,y,=heappop( hq )
	nl[x][y]=cost
	nl[y][x]=cost
	ans+=cost

def dij(start,end):
	d=defaultdict(lambda: float("inf")) 
	d[start]=0
	q=[]
	heappush( q, start )	#u: chouten

	while q:
		fro=heappop(q)
		for to in range(1,N+1):
			alt=d[fro]+nl[fro][to]
			if d[to]>alt:
				d[to]=alt
				heappush(q,to)
	return d[end]


while hq:
	cost,x,y,=heappop( hq )
	d=dij(x,y)

	if d<cost:
		print -1
		quit()
	elif cost<d:
		ans+=cost
	nl[x][y]=cost
	nl[y][x]=cost


print ans

Submission status: Time Limit Exceeded

Solution code:
import sys
from heapq import heappush, heappop

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

hq=[]
for i in range(N):
	L=map(int, sys.stdin.readline().split())
	for j in range(i+1,N):
		heappush( hq, (L[j],i+1,j+1) )


ans=0
for n in range(N-1):
	cost,x,y,=heappop( hq )
	nl[x][y]=cost
	nl[y][x]=cost
	ans+=cost

def dij(start,end):
	d=[ float("inf") for _ in range(N+1)]
	d[start]=0
	q=[]
	heappush( q, start )	#u: chouten

	while q:
		fro=heappop(q)
		for to in range(1,N+1):
			alt=d[fro]+nl[fro][to]
			if d[to]>alt:
				d[to]=alt
				heappush(q,to)
	return d[end]


while hq:
	cost,x,y,=heappop( hq )
	d=dij(x,y)

	if d<cost:
		print -1
		quit()
	elif cost<d:
		ans+=cost
	nl[x][y]=cost
	nl[y][x]=cost


print ans

Submission status: Time Limit Exceeded

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

L = []
for i in range(N):
  for j in range(i + 1, N):
    L.append([A[i][j], i, j])

ans = 0
for i in range(N - 1):
  for j in range(i + 1, N):
    for k in range(N):
      if i == k: continue
      if j == k: continue
      if A[i][j] > A[i][k] + A[k][j]:
        print(-1)
        exit()
      if A[i][j] == A[i][k] + A[k][j]:
        break
    else:
      ans += A[i][j]

print(ans)

Submission status: Time Limit Exceeded

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

L = []
for i in range(N):
  for j in range(i + 1, N):
    L.append([A[i][j], i, j])

D = [[0] * N for i in range(N)]

for i in range(N):
  for j in range(N):
    D[i][j] = A[i][j]
    D[j][i] = A[i][j]

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

ans = 0
for i in range(N - 1):
  for j in range(i + 1, N):
    if A[i][j] > D[i][j]:
      print(-1)
      exit()
    for k in range(N):
      if i == k: continue
      if j == k: continue
      if D[i][j] == D[i][k] + D[k][j]:
        break
    else:
      ans += D[i][j]

print(ans)

Submission status: Time Limit Exceeded

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

L = []
for i in range(N):
  for j in range(i + 1, N):
    L.append([A[i][j], i, j])

L.sort()

class Tree:
  def __init__(s, N):
    s.T = [-1] * N
  def root(s, x):
    if s.T[x] < 0:
      return x, -s.T[x]
    r, d = s.root(s.T[x])
    s.T[x] = r
    return r, d
  def merge(s, a, b):
    ar, ad = s.root(a)
    br, bd = s.root(b)
    if ar == br:
      return True
    if ad < bd:
      s.T[ar] = -max(ad, bd + 1)
      s.T[br] = ar
    else:
      s.T[br] = -max(bd, ad + 1)
      s.T[ar] = br
    return False

class Data():
  class Node():
    def __init__(s):
      s.R = {}
      s.reset()
    def reset(s):
      s.done = False
      s.cos = -1
    def set(s, a, x):
      s.R[a] = x

  def __init__(s, N):
    s.nodes = [s.Node() for _ in range(N)]
  def set(s, a, b, x):
    s.nodes[a].set(b, x)
    s.nodes[b].set(a, x)
  def dist(s, a, b, f):
    if f:
      s.dijk(a)
    return s.nodes[b].cos
  def dijk(s, a):
    for n in s.nodes:
      n.reset()
    s.nodes[a].cos = 0
    while True:
      dn = None
      for n in s.nodes:
        if n.done or n.cos < 0: continue
        if dn == None or n.cos < dn.cos:
          dn = n
      if dn == None:
        break
      dn.done = True
      for k, v in dn.R.items():
        n = s.nodes[k]
        if n.done: continue
        if n.cos == -1 or n.cos > dn.cos + v:
          n.cos = dn.cos + v
t = Tree(N)
d = Data(N)
ans = 0
for i in range(len(L)):
  x, a, b = L[i]
  if t.merge(a, b):
    if d.dist(a, b, True) != x:
      d.set(a, b, x)
      ans += x
  else:
    d.set(a, b, x)
    ans += x

for i in range(N - 1):
  if d.dist(i, i + 1, True) != A[i][i + 1]:
    break
  for j in range(i + 2, N):
    if d.dist(i, j, False) != A[i][j]:
      break
  else:
    continue
  break
else:
  print(ans)
  exit()

print(-1)

Submission status: Time Limit Exceeded

Solution code:
N= int(input())

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

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)