28472023-01-29 20:02:46VMGoJoRendőrségi őrjárat 2python3Időlimit túllépés 0/1001.585s57172 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ÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva18ms11436 KiB
2Elfogadva17ms11692 KiB
subtask20/30
3Elfogadva90ms13008 KiB
4Elfogadva28ms13056 KiB
5Elfogadva93ms13496 KiB
6Elfogadva127ms13772 KiB
7Elfogadva86ms13680 KiB
8Elfogadva39ms13804 KiB
9Időlimit túllépés1.562s5772 KiB
subtask30/30
10Időlimit túllépés1.574s38164 KiB
11Időlimit túllépés1.585s39120 KiB
12Időlimit túllépés1.574s41436 KiB
13Időlimit túllépés1.57s43744 KiB
14Időlimit túllépés1.582s45620 KiB
subtask40/40
15Időlimit túllépés1.582s47172 KiB
16Időlimit túllépés1.574s51044 KiB
17Időlimit túllépés1.554s49712 KiB
18Időlimit túllépés1.57s49620 KiB
19Időlimit túllépés1.55s49692 KiB
20Időlimit túllépés1.57s49624 KiB
21Időlimit túllépés1.574s49636 KiB
22Időlimit túllépés1.574s49632 KiB
23Időlimit túllépés1.562s57172 KiB
24Időlimit túllépés1.582s46252 KiB