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