задача 6

 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
n,s,f=[int(j) for j in input().split()]
b,c,d,e,visited,a=[],[100*100]*n,10000,s-1,[False]*n,[-1]*n
for i in range(n):
a=[int(j) for j in input().split()]
b.append(a)
c[s-1],visited[s-1]=0,True
for i in range(n):
if b[s-1][i]>0:
c[i]=b[s-1][i]
a[i]=s-1
for j in range(n):
for i in range(n):
if c[i]<d and c[i]>0 and i!=e and not visited[i]:
d=c[i]
e=i
for k in range(n):
if b[e][k]>0 and c[e]+b[e][k]<c[k]:
c[k]=c[e]+b[e][k]
a[k]=e
visited[e]=True
d=10000
if c[f-1]<10000:
x,y=[f],f-1
while y!=s-1:
x.append(a[y]+1)
y=a[y]
for elem in x[::-1]:
print(elem,end=' ')
else:
print(-1)