8953 2024. 02. 07 18:05:43 NagyLeo A lehető legkevesebb metróval utazás (40 pont) pypy3 Futási hiba 32/40 97ms 100880 KiB
def main3():
    N, M, Dep, Arr = map(int, input().split())
    metro = []
    Dep_index = set()
    Arr_index = set()
    for i in range(N):
        asd = list(map(int, input().split()))

        metro.append(set(asd[1:]))
        if Dep in metro[i]:
            Dep_index.add(i)
        if Arr in metro[i]:
            Arr_index.add(i)
        if i in Arr_index and i in Dep_index:
            print(1)
            print(i+1)
            return

    graph={}

    for i in range(N-1):
        for j in range(i+1, N):
            if not metro[i].isdisjoint(metro[j]):
                try:
                    graph[i].append(j)
                except:
                    graph[i] = [j]
                try:
                    graph[j].append(i)
                except:
                    graph[j] = [i]

    touched = Dep_index.copy()
    current_res = [0]*N
    for i in Dep_index:
        current_res[i]=[i]
    while Dep_index:
        tmp=[]
        for i in Dep_index:
            if i not in graph:
                continue
            for j in graph[i]:
                if j not in touched:
                    tmp.append(j)
                    touched.add(j)
                    current_res[j]=current_res[i]+[j]
                    if j in Arr_index:
                        print(len(current_res[j]))
                        [print(x+1, end=" ") for x in current_res[j]]
                        return
        Dep_index=tmp

    print("-1")

main3()
Részfeladat Összpont Teszt Verdikt Idő Memória
base 32/40
1 Elfogadva 0/0 57ms 87904 KiB
2 Elfogadva 0/0 76ms 95720 KiB
3 Elfogadva 2/2 54ms 87808 KiB
4 Elfogadva 2/2 50ms 87740 KiB
5 Elfogadva 2/2 46ms 87580 KiB
6 Elfogadva 2/2 50ms 87772 KiB
7 Elfogadva 2/2 54ms 94800 KiB
8 Elfogadva 2/2 61ms 94516 KiB
9 Elfogadva 2/2 57ms 94844 KiB
10 Elfogadva 2/2 54ms 94964 KiB
11 Elfogadva 2/2 65ms 94880 KiB
12 Elfogadva 2/2 82ms 96232 KiB
13 Elfogadva 2/2 90ms 96176 KiB
14 Elfogadva 2/2 82ms 96184 KiB
15 Futási hiba 0/2 97ms 100880 KiB
16 Futási hiba 0/2 94ms 100612 KiB
17 Futási hiba 0/2 86ms 100700 KiB
18 Futási hiba 0/2 96ms 100692 KiB
19 Elfogadva 2/2 85ms 96044 KiB
20 Elfogadva 2/2 75ms 95960 KiB
21 Elfogadva 2/2 83ms 95876 KiB
22 Elfogadva 2/2 86ms 96372 KiB