Advertisement
Guest User

Untitled

a guest
Sep 11th, 2019
149
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.26 KB | None | 0 0
  1. import sys
  2. input = sys.stdin.readline
  3.  
  4. n, r = map(int, input().split(' '))
  5. adj = [ [] for i in range(n+1) ]
  6. vis = [False for i in range(n+1)]
  7. prev = [-1 for i in range(n+1)]
  8. bunnies = [-1 for i in range(n+1)]
  9.  
  10. for i in range(n-1):
  11. x, y = list(map(int, input().split(' ')))
  12. adj[x].append(y)
  13. adj[y].append(x)
  14.  
  15. b = []
  16. for i in range(r):
  17. x = int(input())
  18. b.append(x)
  19. bunnies[x] = 0
  20.  
  21. #while len(b) > 0:
  22. # node = b.pop(0)
  23. # for i in range(0, len(adj[node-1])):
  24. # if bunnies[adj[node-1][i]-1] == False:
  25. # bunnies[adj[node-1][i]-1] = bunnies[node-1] + 1
  26. # b.append(bunnies[adj[node-1][i]])
  27. while len(b) > 0:
  28. cur = b.pop(0)
  29. for neighbor in adj[cur]:
  30. if bunnies[neighbor] == -1:
  31. bunnies[neighbor] = bunnies[cur] + 1
  32. b.append(neighbor)
  33.  
  34. start, end = list(map(int, input().split(' ')))
  35.  
  36. queue = [start]
  37. vis[start] = True
  38. while len(queue) > 0:
  39. node = queue.pop(0)
  40. for neighbor in adj[node]:
  41. if vis[neighbor] == False:
  42. vis[neighbor] = True
  43. queue.append(neighbor)
  44. prev[neighbor] = node
  45. cur, minrab = end, 1000000000
  46. while cur != -1:
  47. minrab = min(minrab, bunnies[cur])
  48. cur = prev[cur]
  49.  
  50. print(minrab)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement