-
Notifications
You must be signed in to change notification settings - Fork 0
/
ccc_2018_J5.py
52 lines (47 loc) · 1.03 KB
/
ccc_2018_J5.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
N = int(input())
book = []
book.append([])
visited = []
visited.append(1)
minPath = N+1
dist = [minPath]
for i in range(N):
pp = input().split()
if int(pp[0]) == 0:
visited.append(0)
book.append([0])
dist.append(minPath)
continue
curlist = []
for j in range(1, len(pp), 1):
curlist.append(int(pp[j]))
book.append(curlist)
visited.append(0)
dist.append(minPath)
stacklist = [1]
visited[1] = 1
dist[1] = 1
while len(stacklist) > 0:
n = stacklist.pop()
p = dist[n]
for x in book[n]:
if x == 0:
if minPath > p:
minPath = p
else:
if p+1 < dist[x]:
dist[x] = p+1
visited[x] = 0
if visited[x] == 0:
stacklist.append(x)
visited[x] = 1
allvisited = True
for x in visited:
if x == 0:
allvisited = False
break
if allvisited:
print("Y")
else:
print("N")
print(minPath)