89552024-02-07 18:22:37NagyLeoA lehető legkevesebb metróval utazás (40 pont)python3Runtime error 32/4090ms66884 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)]

    for i in range(N-1):
        for j in range(i+1, N):
            if not metro[i].isdisjoint(metro[j]):
                graph[i].append(j)
                graph[j].append(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:
            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]))
                        for x in current_res[j]:
                            print(x+1, end=" ")
                        return
        Dep_index=tmp

    print("-1")

main3()
SubtaskSumTestVerdictTimeMemory
base32/40
1Accepted0/018ms11572 KiB
2Accepted0/043ms14176 KiB
3Accepted2/218ms11924 KiB
4Accepted2/217ms12372 KiB
5Accepted2/217ms12600 KiB
6Accepted2/218ms12676 KiB
7Accepted2/218ms13804 KiB
8Accepted2/219ms13948 KiB
9Accepted2/221ms14924 KiB
10Accepted2/223ms14144 KiB
11Accepted2/219ms13836 KiB
12Accepted2/250ms16556 KiB
13Accepted2/248ms16488 KiB
14Accepted2/243ms16428 KiB
15Runtime error0/290ms66884 KiB
16Runtime error0/289ms66804 KiB
17Runtime error0/287ms66856 KiB
18Runtime error0/289ms66692 KiB
19Accepted2/237ms15904 KiB
20Accepted2/239ms16688 KiB
21Accepted2/229ms15588 KiB
22Accepted2/241ms17124 KiB