229472026-01-16 09:26:48BencuA lehető legkevesebb metróval utazás (40 pont)cpp17Elfogadva 40/40246ms2356 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;
    }
RészfeladatÖsszpontTesztVerdiktIdőMemória
base40/40
1Elfogadva0/01ms316 KiB
2Elfogadva0/08ms1076 KiB
3Elfogadva2/21ms316 KiB
4Elfogadva2/21ms316 KiB
5Elfogadva2/21ms316 KiB
6Elfogadva2/21ms316 KiB
7Elfogadva2/21ms316 KiB
8Elfogadva2/21ms316 KiB
9Elfogadva2/22ms316 KiB
10Elfogadva2/22ms564 KiB
11Elfogadva2/21ms492 KiB
12Elfogadva2/28ms1260 KiB
13Elfogadva2/28ms1076 KiB
14Elfogadva2/28ms1076 KiB
15Elfogadva2/2246ms2308 KiB
16Elfogadva2/2240ms2356 KiB
17Elfogadva2/2243ms2196 KiB
18Elfogadva2/2239ms2356 KiB
19Elfogadva2/26ms1260 KiB
20Elfogadva2/27ms1076 KiB
21Elfogadva2/24ms1276 KiB
22Elfogadva2/28ms1076 KiB