• API
• FAQ
• Tools
• Archive
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(' ')))
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
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.

Top