# INF float inf int input for in range row list map int input split appe

 ``` 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``` ```INF = float("inf") N = int(input()) W = [] for i in range(N): row = list(map(int, input().split())) W.append(row) A, B = map(int, input().split()) for i in range(N): for j in range(N): if W[i][j] <= 0 and i != j: 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] = -1 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] print ("\nМатрица кратчайших расстояний:"); for i in range(N): for j in range(N): print ( "%4d" %(W[i][j]), end="" ) print() print(W[A-1][B-1]) ''' 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() ''' 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() ```