# INF 1e10 map int input split for in range row list map int input split

 ``` 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 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126``` ```INF = 1e10 N, A, B = map(int, input().split()) 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 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() ''' ''' if W[A-1][B-1] < INF: print(W[A-1][B-1]) else: print(-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() ''' Q = [] #print ("Кратчайшие маршруты из вершины:", A) if W[A-1][B-1] != 0: for k in range(B): if k != i: j = k while j != -1: if k == B-1: Q.append(j+1) j = P[A-1][j] i = len(Q)-1 while i >= 0: print(Q[i], end = ' ') i -= 1 ```