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 |