89482024-02-07 17:58:03NagyLeoA lehető legkevesebb metróval utazás (40 pont)python3Runtime error 6/4090ms67008 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()

SubtaskSumTestVerdictTimeMemory
base6/40
1Accepted0/017ms11500 KiB
2Runtime error0/043ms14644 KiB
3Accepted2/217ms12116 KiB
4Accepted2/217ms12160 KiB
5Accepted2/217ms12624 KiB
6Runtime error0/218ms12720 KiB
7Runtime error0/219ms14080 KiB
8Runtime error0/219ms14376 KiB
9Runtime error0/223ms15420 KiB
10Runtime error0/223ms15320 KiB
11Runtime error0/219ms14572 KiB
12Runtime error0/250ms17144 KiB
13Runtime error0/250ms17324 KiB
14Runtime error0/245ms17048 KiB
15Runtime error0/290ms67008 KiB
16Runtime error0/287ms66796 KiB
17Runtime error0/287ms66676 KiB
18Runtime error0/287ms66476 KiB
19Runtime error0/239ms15888 KiB
20Runtime error0/241ms16372 KiB
21Runtime error0/232ms15712 KiB
22Runtime error0/243ms17272 KiB