229482026-01-16 09:28:08BencuA lehető legkevesebb metróval utazás (40 pont)cpp17Accepted 40/40241ms2384 KiB
#include <bits/stdc++.h>
using namespace std;
int n,m,x,y,c;bool b[201][10001],a[200][200];int k,v,K[201],V[201],L[201],E[201];void bejar (int g) {for (int i=1; i<=n; i++) L[i]=202;L[g]=0;int vsor[201],elso,utolso;elso=1;utolso=1;vsor[elso]=g;while (elso<=utolso) {int t=vsor[elso];for (int i=1; i<=n; i++) {if (a[i][t]==1 && L[i]==202 && i!=g) {L[i]=L[t]+1;E[i]=t;utolso++;vsor[utolso]=i;}}elso++;}}int main(){ios::sync_with_stdio(0);cin.tie(0);cin>>n>>m>>x>>y;for (int i=1; i<=n; i++) {int t;cin>>t;for (int p=1; p<=t; p++) {int j;cin>>j;b[i][j]=1;if (j==x) {k++;K[k]=i;}if (j==y) {v++;V[v]=i;}}}for (int j=1; j<=m; j++) {for (int i=1; i<=n; i++) {if (b[i][j]==1) {for (int p=i+1; p<=n; p++) {if (b[p][j]==1) {a[i][p]=1;a[p][i]=1;}}}}}int MIN=202,mi,MI[201];for (int i=1; i<=k; i++) {bejar(K[i]);for (int j=1; j<=v; j++) {if (L[V[j]]<MIN) {MIN=L[V[j]];c=K[i];mi=MIN;int d=V[j];for (int q=1; q<=MIN; q++) {MI[MIN-q+1]=d;d=E[d];}}}}if (MIN==202) cout<<-1;else {cout<<MIN+1<<endl;cout<<c<<" ";for (int i=1; i<=MIN; i++) cout<<MI[i]<<" ";}return 0;}
SubtaskSumTestVerdictTimeMemory
base40/40
1Accepted0/01ms532 KiB
2Accepted0/07ms1076 KiB
3Accepted2/21ms316 KiB
4Accepted2/21ms316 KiB
5Accepted2/21ms316 KiB
6Accepted2/21ms316 KiB
7Accepted2/21ms508 KiB
8Accepted2/21ms396 KiB
9Accepted2/22ms536 KiB
10Accepted2/22ms560 KiB
11Accepted2/21ms564 KiB
12Accepted2/28ms1280 KiB
13Accepted2/28ms1076 KiB
14Accepted2/27ms1076 KiB
15Accepted2/2241ms2356 KiB
16Accepted2/2240ms2304 KiB
17Accepted2/2241ms2356 KiB
18Accepted2/2240ms2384 KiB
19Accepted2/26ms1068 KiB
20Accepted2/27ms1076 KiB
21Accepted2/24ms1080 KiB
22Accepted2/27ms1076 KiB