задача 97

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
n = int(input())
graph = [list(map(int, input().split())) for i in range(n)]
for k in range(n):
for i in range(n):
for j in range(n):
graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
mybool = False
for i in range(n):
if graph[i][i] < 0:
mybool = True
break
else:
graph[i][i] = 1000000000000
if mybool:
print(-1)
exit()
max = min
print(max([max(i) for i in graph]))