Advertisement
Guest User

Untitled

a guest
Dec 10th, 2018
63
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.90 KB | None | 0 0
  1. import sys
  2. sys.setrecursionlimit(0x10000000)
  3.  
  4.  
  5. def add(a, b):
  6. g[a].append(b)
  7. g[b].append(a)
  8.  
  9.  
  10. def bfs(st):
  11. q = []
  12. q.append(st)
  13. used[st] = True
  14. while len(q) != 0:
  15. v = q.pop(0)
  16. for i in g[v]:
  17. if not used[i]:
  18. used[i] = True
  19. q.append(i)
  20. parent[i] = v
  21. d[i] = d[v] + 1
  22.  
  23.  
  24. n = int(input())
  25. used = [False] * (n + 10)
  26. parent = [-1] * (n + 10)
  27. d = [0] * n
  28. g = []
  29. for i in range(n):
  30. g.append([])
  31. for i in range(n):
  32. l = list(map(int, input().split()))
  33. for j in range(i + 1, n):
  34. if l[j] == 1:
  35. add(i, j)
  36. st, en = list(map(int, input().split()))
  37. bfs(st - 1)
  38. if not used[st - 1]:
  39. print(-1)
  40. else:
  41. path = []
  42. v = en - 1
  43. while v != -1:
  44. path.append(v + 1)
  45. v = parent[v]
  46. print(len(path) - 1)
  47. print(*reversed(path))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement