| 2847 | 2023-01-29 20:02:46 | VMGoJo | Rendőrségi őrjárat 2 | python3 | Időlimit túllépés 0/100 | 1.585s | 57172 KiB |
from sys import stdin, stdout
def main():
n,m,l = map(int,stdin.readline().split())
nodes:list[set[int]]=[]
for i in range(n):
nodes.append(set([i]))
for i in range(m):
a,b = map(int,stdin.readline().split())
nodes[a].add(b)
nodes[b].add(a)
#print(nodes)
patrols=stdin.readline().split()
patrols = [int(i) for i in patrols]
minutes:int=0
first_it_list:set[int]=[0]
#BREADTH FIRST SEARCH
def do_layer(first_it_l:set[int]) ->set[int]:
rt_set:set[int]=set([])
for i in first_it_l:
rt_set=rt_set.union(nodes[i])
return rt_set
while not first_it_list.__contains__(n-1):
minutes+=1
first_it_list=do_layer(first_it_list)
first_it_list=first_it_list.difference(set([patrols[minutes%len(patrols)]]))
stdout.write(str(minutes))
main()| Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
|---|---|---|---|---|---|---|---|
| subtask1 | 0/0 | ||||||
| 1 | Elfogadva | 18ms | 11436 KiB | ||||
| 2 | Elfogadva | 17ms | 11692 KiB | ||||
| subtask2 | 0/30 | ||||||
| 3 | Elfogadva | 90ms | 13008 KiB | ||||
| 4 | Elfogadva | 28ms | 13056 KiB | ||||
| 5 | Elfogadva | 93ms | 13496 KiB | ||||
| 6 | Elfogadva | 127ms | 13772 KiB | ||||
| 7 | Elfogadva | 86ms | 13680 KiB | ||||
| 8 | Elfogadva | 39ms | 13804 KiB | ||||
| 9 | Időlimit túllépés | 1.562s | 5772 KiB | ||||
| subtask3 | 0/30 | ||||||
| 10 | Időlimit túllépés | 1.574s | 38164 KiB | ||||
| 11 | Időlimit túllépés | 1.585s | 39120 KiB | ||||
| 12 | Időlimit túllépés | 1.574s | 41436 KiB | ||||
| 13 | Időlimit túllépés | 1.57s | 43744 KiB | ||||
| 14 | Időlimit túllépés | 1.582s | 45620 KiB | ||||
| subtask4 | 0/40 | ||||||
| 15 | Időlimit túllépés | 1.582s | 47172 KiB | ||||
| 16 | Időlimit túllépés | 1.574s | 51044 KiB | ||||
| 17 | Időlimit túllépés | 1.554s | 49712 KiB | ||||
| 18 | Időlimit túllépés | 1.57s | 49620 KiB | ||||
| 19 | Időlimit túllépés | 1.55s | 49692 KiB | ||||
| 20 | Időlimit túllépés | 1.57s | 49624 KiB | ||||
| 21 | Időlimit túllépés | 1.574s | 49636 KiB | ||||
| 22 | Időlimit túllépés | 1.574s | 49632 KiB | ||||
| 23 | Időlimit túllépés | 1.562s | 57172 KiB | ||||
| 24 | Időlimit túllépés | 1.582s | 46252 KiB | ||||