Advertisement
Guest User

Untitled

a guest
Dec 15th, 2018
57
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.76 KB | None | 0 0
  1. nodes = list()
  2. N = int(input())
  3. for i in range(N):
  4. nodes.append(list(map(int, input().split())))
  5. S, F = map(int, input().split())
  6. dist = [-1] * N
  7.  
  8.  
  9. def DFS(N, S, F, nodes):
  10. global dist
  11. dist[S - 1] = 0
  12. stack = [S - 1]
  13. prev = [-1] * N
  14. way = list()
  15. way.append(F)
  16. while stack:
  17. v = stack.pop(0)
  18. for i in range(N):
  19. if i == F + 2:
  20. break
  21. if nodes[v][i] == 1 and dist[i] == -1:
  22. stack.append(i)
  23. dist[i] = dist[v] + 1
  24. prev[i] = v + 1
  25. if dist[F - 1] == -1:
  26. print(-1)
  27. else:
  28. print(dist[F - 1])
  29. while F != S:
  30. F = prev[F - 1]
  31. way.append(F)
  32. print(*way[::-1])
  33.  
  34.  
  35. DFS(N, S, F, nodes)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement