28472023-01-29 20:02:46VMGoJoRendőrségi őrjárat 2python3Time limit exceeded 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()
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted18ms11436 KiB
2Accepted17ms11692 KiB
subtask20/30
3Accepted90ms13008 KiB
4Accepted28ms13056 KiB
5Accepted93ms13496 KiB
6Accepted127ms13772 KiB
7Accepted86ms13680 KiB
8Accepted39ms13804 KiB
9Time limit exceeded1.562s5772 KiB
subtask30/30
10Time limit exceeded1.574s38164 KiB
11Time limit exceeded1.585s39120 KiB
12Time limit exceeded1.574s41436 KiB
13Time limit exceeded1.57s43744 KiB
14Time limit exceeded1.582s45620 KiB
subtask40/40
15Time limit exceeded1.582s47172 KiB
16Time limit exceeded1.574s51044 KiB
17Time limit exceeded1.554s49712 KiB
18Time limit exceeded1.57s49620 KiB
19Time limit exceeded1.55s49692 KiB
20Time limit exceeded1.57s49624 KiB
21Time limit exceeded1.574s49636 KiB
22Time limit exceeded1.574s49632 KiB
23Time limit exceeded1.562s57172 KiB
24Time limit exceeded1.582s46252 KiB