89502024-02-07 18:00:10NagyLeoA lehető legkevesebb metróval utazás (40 pont)pypy3Futási hiba 6/40116ms101388 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]

    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:
            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ÖsszpontTesztVerdiktIdőMemória
base6/40
1Elfogadva0/061ms87472 KiB
2Futási hiba0/0108ms97376 KiB
3Elfogadva2/250ms87620 KiB
4Elfogadva2/254ms87468 KiB
5Elfogadva2/257ms87684 KiB
6Futási hiba0/282ms95224 KiB
7Futási hiba0/281ms96696 KiB
8Futási hiba0/287ms96544 KiB
9Futási hiba0/289ms96488 KiB
10Futási hiba0/290ms96492 KiB
11Futási hiba0/282ms96496 KiB
12Futási hiba0/2107ms97544 KiB
13Futási hiba0/2116ms97560 KiB
14Futási hiba0/2104ms97352 KiB
15Futási hiba0/290ms101388 KiB
16Futási hiba0/290ms101004 KiB
17Futási hiba0/290ms101168 KiB
18Futási hiba0/2101ms101180 KiB
19Futási hiba0/2101ms97392 KiB
20Futási hiba0/298ms97364 KiB
21Futási hiba0/297ms96920 KiB
22Futási hiba0/2112ms97424 KiB