90902024-02-13 20:08:10NagyLeoA lehető legkevesebb metróval utazás (40 pont)python3Futási hiba 32/4097ms67372 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]=-1
    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]=i
                    if j in Arr_index:
                        #print(len(current_res[j]))
                        #for x in current_res[j]:
                        #    print(x+1, end=" ")
                        res=[j]
                        while current_res[j] != -1:
                            j=current_res[j]
                            res.append(j)
                        print(len(res))
                        for x in range(len(res)-1,-1,-1):
                            print(res[x]+1, end=" ")
                        #print(j+1)
                        return
        Dep_index=tmp

    print("-1")

main3()
RészfeladatÖsszpontTesztVerdiktIdőMemória
base32/40
1Elfogadva0/019ms11788 KiB
2Elfogadva0/041ms14364 KiB
3Elfogadva2/217ms12104 KiB
4Elfogadva2/218ms12016 KiB
5Elfogadva2/217ms11952 KiB
6Elfogadva2/217ms12736 KiB
7Elfogadva2/220ms13740 KiB
8Elfogadva2/219ms13752 KiB
9Elfogadva2/223ms14780 KiB
10Elfogadva2/223ms14216 KiB
11Elfogadva2/219ms13632 KiB
12Elfogadva2/250ms16208 KiB
13Elfogadva2/250ms16220 KiB
14Elfogadva2/243ms16072 KiB
15Futási hiba0/286ms67372 KiB
16Futási hiba0/294ms67228 KiB
17Futási hiba0/297ms67236 KiB
18Futási hiba0/289ms67172 KiB
19Elfogadva2/237ms15260 KiB
20Elfogadva2/239ms15984 KiB
21Elfogadva2/230ms15356 KiB
22Elfogadva2/243ms16836 KiB