SHARE
TWEET

Untitled

a guest Sep 11th, 2019 101 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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)
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top