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

Submission status: Time Limit Exceeded

Solution code:
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))

Submission status: Time Limit Exceeded

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

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

print(solve(n, v))

Submission status: Time Limit Exceeded

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(n, v))

Submission status: Time Limit Exceeded

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

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

                d = A[i][k] + A[k][j]
                if d == A[i][j] :
                    cost = 0
                elif d < A[i][j] :
                    print(-1)
                    exit()
            ans += cost
    print(ans)

main()

Submission status: Time Limit Exceeded

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

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

wf = [[A[i][j] for j in range(n)] for i in range(n)]
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 = wf[i][k] + wf[k][j]
            if d == wf[i][j] :
                ans -= d
            elif d < wf[i][j] :
                print(-1)
                exit()

print(ans//2)

Submission status: Time Limit Exceeded

Solution code:
#to solve this first implemnent floyd-warshal

def solve(n,dis,tt):
	for k in range(n):
		for i in range(n):
			for j in range(n):
				if dis[i][j] > dis[i][k] + dis[k][j]:
					return -1
						
				elif  i!=k and j!=k and dis[i][j]==dis[i][k]+dis[k][j]:
					tt[i][j]=False
	
	ans=0
	for i in range(n):
		for j in range(n):
			if tt[i][j]:
				ans+=dis[i][j]
	
	return ans//2

n=int(input())
dis=[[0]*n for i in range(n)]
for i in range(n):
	l=[int(x) for x in input().split()]
	for j in range(n):
		dis[i][j]=l[j]
tt=[[True]*n for i in range(n)]
print(solve(n,dis,tt))

Submission status: Time Limit Exceeded

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

INF = 10 ** 9 + 1
for i in range(N):
    A[i][i] = INF

ans = 0
for i in range(N):
    Ai = A[i]
    for j in range(i):
        Aj = A[j]
        d = INF * 2
        for k in range(N):
            d = min(d, Ai[k] + Aj[k])

        if A[i][j] > d:
            print('-1')
            exit()
        elif A[i][j] < d:
            ans += A[i][j]

print(ans)

Submission status: Time Limit Exceeded

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

INF = 10 ** 9 + 1
for i in range(N):
    A[i][i] = INF

ans = 0
for i in range(N):
    for j in range(i):
        d = INF * 2
        for k in range(N):
            d = min(d, A[i][k] + A[k][j])

        if A[i][j] > d:
            print('-1')
            exit()
        elif A[i][j] < d:
            ans += A[i][j]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(raw_input())
A = [map(int, raw_input().split(' ')) for n in [0]*N]
for i in xrange(N): A[i][i] = 1000000000

answer = 0
for i, Ai in enumerate(A):
  for j, Aj in enumerate(A[:i]):
    Aij = Ai[j]
    no_other_route = 1
    for k in xrange(N):
      L = Ai[k] + Aj[k]
      if Aij >= L:
        if Aij > L:
          print -1
          exit()
        no_other_route = 0
    answer += Aij * no_other_route

print answer

Submission status: Time Limit Exceeded

Solution code:
N = int(raw_input())
A = [map(int, raw_input().split(' ')) for n in xrange(N)]

answer = 0
for i in xrange(N):
  Ai = A[i]
  for j in xrange(i):
    Aj = A[j]
    Aij = Ai[j]
    no_other_route = 1
    for k in xrange(N):
      L = Ai[k] + Aj[k]
      if Aij >= L:
        if Aij > L:
          print -1
          exit()
        if k == i or k == j: continue
        no_other_route = 0
    answer += Aij * no_other_route

print answer

Submission status: Time Limit Exceeded

Solution code:
def solve():
    INF = float('inf')
    N = int(input())
    a = []
    for i in range(N):
        a.append(list(map(int, input().split())))
        flag = 0
        length = 0

    for i in range(N):
        a[i][i] = INF
        

    for i in range(N):
        for j in range(i+1, N):
            muda = 0
            for k in range(N):
                mix = a[i][k] + a[k][j]
                if a[i][j] > mix:
                    print(-1)
                    exit()
                elif a[i][j] == mix:
                    muda = 1
                    continue
            if muda == 1:
                continue
            length += a[i][j]

    if (flag == 0):
        length = int(length)
    else:
        length = -1
    print(length)

solve()

Submission status: Time Limit Exceeded

Solution code:
import copy
import sys
import numpy as np
import heapq

from math import *
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

class node_cost:
    def __init__(self, point, cost):
        self.point = point
        self.cost = cost

    def __lt__(self, other):
        return self.cost < other.cost

class warshall_floyd:
    def __init__(self):
        self.A = []

    def execute(self, adj_mat):
        self.A = copy.deepcopy(adj_mat)
        for k in range(len(self.A)):
            for i in range(len(self.A)):
                if self.A[i][k] < sys.maxint:
                    for j in range(len(self.A)):
                        if self.A[k][j] < sys.maxint:
                            self.A[i][j] = min(self.A[i][j], self.A[i][k] + self.A[k][j])



##class Dijkstra:
##    def __init__(self):
##        self.table = {}
##
##    def execute(self, adj_list, start):
##        confirm_set = set()
##        cost_dict = {}
##        cost_dict[start] = 0
##        #heapq.heapify
##
##        n = node_cost(start, 0)
##        node_list = [n]
##        while len(node_list) > 0:
##            n = heapq.heappop(node_list)
##            if n.point in confirm_set:
##                continue;
##            confirm_set.add(n.point)
##            self.table[(start, n.point)] = n.cost
##            #self.table[(n.point, start)] = n.cost
##            for v in adj_list[n.point]:
##                if v[0] not in confirm_set:
##                    if v[0] not in cost_dict:
##                        cost_dict[v[0]] = n.cost + v[1]
##                        heapq.heappush(node_list, node_cost(v[0], cost_dict[v[0]]))
##                    else:
##                        if n.cost + v[1] < cost_dict[v[0]]:
##                            cost_dict[v[0]] = n.cost + v[1]
##                            heapq.heappush(node_list, node_cost(v[0], cost_dict[v[0]]))

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N] = [int(input_raw[0])]

    adj_list = {}
    dist_mat = [[0 for i in range(N)] for j in range(N)]
    for i in range(N):
        input_raw = read_func().strip().split()
        cost_list = (list(input_raw))
        for j in range(N):
            dist_mat[i][j] = int(cost_list[j])
##            if i != j:
##                if i not in adj_list:
##                    adj_list[i] = []
##                adj_list[i].append((j, int(cost_list[j])))

##
##    D = Dijkstra()
##    for v in range(N):
##        D.execute(adj_list, v)

 

    W = warshall_floyd()
    W.execute(dist_mat)


    is_exist = True
    dist_sum = 0
    for i in range(N):
        for j in range(i + 1, N):
            if dist_mat[i][j] <= W.A[i][j]:
                is_min_pass = True
                for k in range(N):
                    if k != i and k != j:
                        if W.A[i][j] == W.A[i][k] + W.A[k][j]:
                            is_min_pass =False
                            break;
                if is_min_pass == True:
                    dist_sum += dist_mat[i][j]

            else:
                is_exist = False

    if is_exist == True:
        print dist_sum

    else:
        print "-1"

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

# Warshall-Floyd法
dist = [list(A[i]) for i in range(N)]
via = [[None for i in range(N)] for j in range(N)]
for k in range(N):
    for i in range(N):
        for j in range(N):
            d = dist[i][k] + dist[k][j]
            if dist[i][j] >= d:
                dist[i][j] = d
                if i != k and j != k:
                    via[i][j] = k

ans = 0
for i in range(N):
    for j in range(i):
        if dist[i][j] < A[i][j]:
            ans = -1
            break

        if via[i][j] == None:
            ans += dist[i][j]

    if ans == -1:
        break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy
import sys
import numpy as np
import heapq

from math import *
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

class node_cost:
    def __init__(self, point, cost):
        self.point = point
        self.cost = cost

    def __lt__(self, other):
        return self.cost < other.cost

class Dijkstra:
    def __init__(self):
        self.table = {}

    def execute(self, adj_list, start):
        confirm_set = set()
        cost_dict = {}
        cost_dict[start] = 0
        #heapq.heapify

        n = node_cost(start, 0)
        node_list = [n]
        while len(node_list) > 0:
            n = heapq.heappop(node_list)
            if n.point in confirm_set:
                continue;
            confirm_set.add(n.point)
            self.table[(start, n.point)] = n.cost
            #self.table[(n.point, start)] = n.cost
            for v in adj_list[n.point]:
                if v[0] not in confirm_set:
                    if v[0] not in cost_dict:
                        cost_dict[v[0]] = n.cost + v[1]
                        heapq.heappush(node_list, node_cost(v[0], cost_dict[v[0]]))
                    else:
                        if n.cost + v[1] < cost_dict[v[0]]:
                            cost_dict[v[0]] = n.cost + v[1]
                            heapq.heappush(node_list, node_cost(v[0], cost_dict[v[0]]))

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N] = [int(input_raw[0])]

    adj_list = {}
    dist_mat = [[0 for i in range(N)] for j in range(N)]
    for i in range(N):
        input_raw = read_func().strip().split()
        cost_list = (list(input_raw))
        for j in range(N):
            dist_mat[i][j] = int(cost_list[j])
            if i != j:
                if i not in adj_list:
                    adj_list[i] = []
                adj_list[i].append((j, int(cost_list[j])))


    D = Dijkstra()
    for v in range(N):
        D.execute(adj_list, v)
        

    is_exist = True
    dist_sum = 0
    for i in range(N):
        for j in range(i + 1, N):
            if dist_mat[i][j] <= D.table[(i, j)]:
                is_min_pass = True
                for k in range(N):
                    if k != i and k != j:
                        if D.table[(i, j)] == D.table[(i, k)] + D.table[(j, k)]:
                            is_min_pass =False
                            break;
                if is_min_pass == True:
                    dist_sum += dist_mat[i][j]

            else:
                is_exist = False

    if is_exist == True:
        print dist_sum

    else:
        print "-1"

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(raw_input())
A = []
B = []
for n in xrange(N):
  A.append(map(int, raw_input().split(' ')))
  B.append(A[-1]+[])

for i in xrange(N):
  for j in xrange(i):
    for k in xrange(j):
      L1 = A[i][k] + A[k][j]
      L2 = A[k][j] + A[j][i]
      L3 = A[j][i] + A[i][k]
      if A[i][j] > L1 or A[k][i] > L2 or A[j][k] > L3:
        print -1
        exit()
      if A[i][j] == L1: B[i][j] = B[j][i] = 0
      if A[k][i] == L2: B[k][i] = B[i][k] = 0
      if A[j][k] == L3: B[j][k] = B[k][j] = 0

print sum(map(sum, B))/2

Submission status: Time Limit Exceeded

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

adj = [{} for i in range(N)]
for i in range(N):
    for j in range(i + 1, N):
        adj[i][j] = A[i][j]
        adj[j][i] = A[j][i]

import heapq

def Dijkstra(numV, v_st):

    cost = [float('inf') for i in range(numV)]
    cost[v_st] = 0
    num = [0 for i in range(numV)]

    pq = []
    heapq.heappush(pq, (0, v_st))

    while pq:
        c_min, v_now = heapq.heappop(pq)

        if cost[v_now] < c_min:
            continue

        for v, c in adj[v_now].items():
            if cost[v_now] + c < cost[v]:
                cost[v] = cost[v_now] + c
                num[v] = num[v_now] + 1
                heapq.heappush(pq, (cost[v], v))
            elif cost[v_now] + c == cost[v]:
                if num[v] == 1:
                    del adj[v_st][v]
                    del adj[v][v_st]
                elif num[v_now] + 1 == 1:
                    del adj[v_now][v]
                    del adj[v][v_now]
                num[v] = max(num[v], num[v_now] + 1)

    return cost

dist = [[] for i in range(N)]
for i in range(N):
    dist[i] = Dijkstra(N, i)

ans = sum(sum(adj[i].values()) for i in range(N)) // 2
for i in range(N):
    for j in range(N):
        if dist[i][j] < A[i][j]:
            ans = -1
            break
    if ans == -1:
        break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(raw_input())
A = []
for n in xrange(N):
  A.append(map(int, raw_input().split(' ')))

answer = 0
for i in xrange(N):
  for j in xrange(i):
    other_route = False
    for k in xrange(N):
      if k == i or k == j:
        continue
      L = A[i][k] + A[k][j]
      if A[i][j] == L:
        other_route = True
      elif A[i][j] > L:
        print -1
        exit()
    if not other_route:
      answer += A[i][j]

print answer

Submission status: Time Limit Exceeded

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

    dist = [[a[i][j] for j in range(n)] for i in range(n)]
    total = sum([sum(a[i]) for i in range(n)])
    for k in range(n):
        for i in range(n):
            if k==i:
                continue
            for j in range(n):
                if i == j or k ==j:
                    continue
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    print(-1)
                    exit()
                if dist[i][j] == dist[i][k] + dist[k][j]:
                    total -= dist[i][j]
    print(total//2)
    

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

import heapq

def Dijkstra(numV, v_st):

    cost = [float('inf') for i in range(numV)]
    cost[v_st] = 0
    num = [0 for i in range(numV)]

    pq = []
    heapq.heappush(pq, (0, v_st))

    while pq:
        c_min, v_now = heapq.heappop(pq)

        if cost[v_now] < c_min:
            continue

        for v in range(numV):
            if v == v_now:
                continue
            if cost[v_now] + adj[v_now][v] < cost[v]:
                cost[v] = cost[v_now] + adj[v_now][v]
                num[v] = num[v_now] + 1
                heapq.heappush(pq, (cost[v], v))
            elif cost[v_now] + adj[v_now][v] == cost[v]:
                num[v] = max(num[v], num[v_now] + 1)

    return (cost, num)


dist = [[] for i in range(N)]
num = [[] for i in range(N)]
for i in range(N):
    (dist[i], num[i]) = Dijkstra(N, i)

ans = sum(sum(adj[i]) for i in range(N)) // 2
for i in range(N):
    for j in range(i + 1, N):

        if dist[i][j] < adj[i][j]:
            ans = -1
            break

        if num[i][j] > 1:
            if dist[i][j] == adj[i][j]:
                ans -= dist[i][j]

    if ans == -1:
        break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
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)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import heapq
import math
import sys

class Dijkstra(object):
    def dijkstra(self, adj, start, goal):
        num = len(adj)          # グラフのノード数
        dist = [float('inf') for i in range(num)] # 始点から各頂点までの最短距離を格納する

        dist[start] = 0
        q = []                  # プライオリティキュー．各要素は，(startからある頂点vまでの仮の距離, 頂点vのID)からなるタプル
        heapq.heappush(q, (0, start)) # 始点をpush

        while len(q) != 0:
            prov_cost, src = heapq.heappop(q) # pop

            # プライオリティキューに格納されている最短距離が，現在計算できている最短距離より大きければ，distの更新をする必要はない
            if dist[src] < prov_cost:
                continue

            # 他の頂点の探索
            for dest in range(num):
                cost = adj[src][dest]
                if cost != float('inf') and dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost # distの更新
                    heapq.heappush(q, (dist[dest], dest)) # キューに新たな仮の距離の情報をpush
        return dist[goal]

N = int(input())

distances = []
for i in range(N):
    tmp = input()
    As = [int(a) for a in tmp.split()]
    for j, a in enumerate(As):
        if i == j: continue
        distances.append([i, j, a])
distances = sorted(distances, key=lambda x: x[2])

adj = [[0.0 if i == j else float('inf') for i in range(N)] for j in range(N)]
sum_d = 0
dij = Dijkstra()
for i, j, d in distances:
    di = dij.dijkstra(adj, i, j)
    if di == d:
        adj[i][j], adj[j][i] = d, d
    elif di > d:
        sum_d += d
        adj[i][j], adj[j][i] = d, d
    else:
        print(-1)
        sys.exit()
print(int(sum_d))

Submission status: Time Limit Exceeded

Solution code:
N = int(raw_input())
A = []
for n in xrange(N):
  A.append(map(int, raw_input().split(' ')))

memo = {}
def route(f, t, now, arrived):
  if now == t:
    return 0
  if (t, now, tuple(arrived)) in memo:
    return memo[(t, now, tuple(arrived))]
  min_dist = float('inf')
  for k in xrange(N):
    if k in arrived or (k == t and len(arrived) == 1):
      continue
    min_dist = min(route(f, t, k, arrived|set([k]))+A[now][k], min_dist)
  memo[(t, now, tuple(arrived))] = min_dist
  return min_dist

answer = 0
for i in xrange(N):
  for j in xrange(i):
    L = route(i, j, i, set([i]))
    if A[i][j] == L:
      pass
    elif A[i][j] > L:
      print -1
      exit()
    else:
      answer += A[i][j]

print answer

Submission status: Time Limit Exceeded

Solution code:
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)

Submission status: Time Limit Exceeded

Solution code:
import heapq


def dijkstra(graph, root, goal, limit):
    # print('dijkstra',root, goal, limit)
    # print(graph)
    dist = [float('inf')] * len(graph)
    dist[root] = 0
    q = [(0, root)]
    while q:
        d, v = heapq.heappop(q)
        # print(d,v)
        if dist[v] < d:
            continue
        if d == goal:
            return dist

        limit_over = True
        for cost, target in graph[v]:
            # print(d,v, cost, target, dist)
            if dist[target] > dist[v] + cost:
                dist[target] = dist[v] + cost
                heapq.heappush(q, (dist[target], target))
                # print('heapq',q)
            if dist[v] + cost <= limit:
                limit_over = False
        if limit_over:
            # print('limit')
            return dist
    return dist

def main():
    n = int(input())
    a = [list(map(int, input().split())) for i in range(n)]

    h = []
    for i in range(n):
        for j in range(i+1, n):
            heapq.heappush(h, (a[i][j], i, j))

    graph = [[] for i in range(n)]
    total = 0
    while h:
        cost, s, t = heapq.heappop(h)
        dist = dijkstra(graph, s, t, cost)
        if dist[t] < cost:
            print(-1)
            exit()
        elif dist[t] > cost:
            total += cost
            # print(total, s, t, cost, dist[t])
            graph[s].append((cost, t))
            graph[t].append((cost, s))
            dist = dijkstra(graph, s, t, cost)

    # print(*graph, sep = '\n')
    print(total)
        
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
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)

Submission status: Time Limit Exceeded

Solution code:
N = int(raw_input())
A = []
for n in xrange(N):
  A.append(map(int, raw_input().split(' ')))

def route(f, t, now, arrived):
  if now == t:
    return 0
  min_dist = float('inf')
  for k in xrange(N):
    if k in arrived or (k == t and len(arrived) == 1):
      continue
    min_dist = min(route(f, t, k, arrived|set([k]))+A[now][k], min_dist)
  return min_dist

answer = 0
for i in xrange(N):
  for j in xrange(i):
    L = route(i, j, i, set([i]))
    if A[i][j] == L:
      pass
    elif A[i][j] > L:
      print -1
      exit()
    else:
      answer += A[i][j]

print answer