# -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81``` ```""" 6 0 2 4 -1 -1 -1 2 0 9 7 -1 -1 4 9 0 8 1 -1 -1 7 8 0 3 1 -1 -1 1 3 0 2 -1 -1 -1 1 2 0 6 1 6 0 2 1 -1 -1 -1 2 0 9 7 -1 -1 1 9 0 8 4 -1 -1 7 8 0 3 1 -1 -1 4 3 0 5 -1 -1 -1 1 5 0 """ INF = 10000001 N= int(input()) W = [] for i in range(N): row = list(map(int, input().split())) W.append(row) for i in range(N): for j in range(N): if W[i][j] < 0: W[i][j] = INF ''' print ( "Весовая матрица графа: " ) for i in range(N): for j in range(N): if W[i][j] == INF: print ( " *", end="" ) else: print ( "%4d" %W[i][j], end="" ) print(); ''' ''' P = [] for i in range(N): P.append([i]*N) P[i][i] = 0 ''' for k in range(N): for i in range(N): for j in range(N): if W[i][k] + W[k][j] < W[i][j]: W[i][j] = W[i][k] + W[k][j] #P[i][j] = P[k][j] for i in range(N): W[i]=max(W[i]) print(max(W)) ''' print ("\nМатрица кратчайших расстояний:"); for i in range(N): for j in range(N): print ( "%4d" %(W[i][j]), end="" ) print(); ''' ''' print ( "\nВспомогательная матрица:"); for i in range(N): for j in range(N): print( "%4d" %P[i][j], end="" ) print() print() for i in range(N): print ("Кратчайшие маршруты из вершины:", i+1) for k in range(N): if k != i: j = k while j != -1: print ( "%2d" %(j+1), end="" ) if j != i: print ( " <= ", end="" ); j = P[i][j]; print(); ''' ```