244102026-02-11 10:33:14Pedri26A lehető legkevesebb metróval utazás (40 pont)cpp17Accepted 40/40280ms6196 KiB
// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;
int n, m, erk, ind;
bool a[201][10001], b[201][201];
int elso[201], utolso[201], helso, hutolso;
int tav[201], elozo[201], valasz[201];

void szbejar(int i)
{
    bool l[201]={0};
    int velso=1, vutolso=1, vsor[201];
    vsor[velso]=i;
    l[i]=true;
    elozo[i]=i;
    for(int j=1;j<=n;j++)
    {
        tav[j]=0;
        elozo[j]=0;
    }
    while(velso<=vutolso)
    {
        tav[vsor[velso]]=tav[elozo[vsor[velso]]]+1;
        for(int j=1;j<=n;j++)
        {
            if((b[vsor[velso]][j] || b[j][vsor[velso]]) && !l[j])
            {
                vutolso++;
                vsor[vutolso]=j;
                //cout<<j<<" ";
                elozo[vsor[vutolso]]=vsor[velso];
                l[j]=true;
            }
        }
        velso++;
    }
}

int main() {
    cin>>n>>m>>ind>>erk;
    for(int i=1;i<=n;i++)
    {
        int c;
        cin>>c;
        for(int j=1;j<=c;j++)
        {
            int d;
            cin>>d;
            a[i][d]=true;
        }
    }
    for(int i=1;i<n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            if(!b[i][j]){
                for(int k=1;k<=m;k++)
                {
                    if(a[i][k] && a[j][k])
                    {
                        b[i][j]=true;
                        b[j][i]=true;
                        //cout<<i<<"-"<<j<<endl;
                        break;
                    }
                }
            }
        }
    }
    /*for(int i=1;i<n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            if(b[i][j])
            {
                cout<<i<<"-"<<j<<endl;
            }
        }
    }*/
    for(int i=1;i<=n;i++)
    {
        if(a[i][ind])
        {
            helso++;
            elso[helso]=i;
        }
        if(a[i][erk])
        {
            hutolso++;
            utolso[hutolso]=i;
        }
    }
    int mintav=INT_MAX, mintavindex;
    for(int i=1;i<=helso;i++)
    {
        szbejar(elso[i]);
        //cout<<elso[i]<<"->";
        for(int j=1;j<=n;j++)
        {
            if(tav[j]>0 && tav[j]<mintav && a[j][erk])
            {
                mintav=tav[j];
                mintavindex=j;
                //cout<<mintavindex<<" "<<elozo[mintavindex]<<endl;
                int g=0;
                while(mintavindex!=0)
                {
                    valasz[mintav-g]=mintavindex;
                    g++;
                    mintavindex=elozo[mintavindex];
                }
            }
        }
        //cout<<endl;
    }
    if(mintav<INT_MAX)
    {
        cout<<mintav<<endl;
        for(int i=1;i<=mintav;i++)cout<<valasz[i]<<" ";
    }else cout<<"-1";

    return 0;
}
SubtaskSumTestVerdictTimeMemory
base40/40
1Accepted0/01ms316 KiB
2Accepted0/0145ms1208 KiB
3Accepted2/21ms316 KiB
4Accepted2/21ms316 KiB
5Accepted2/21ms316 KiB
6Accepted2/21ms316 KiB
7Accepted2/22ms316 KiB
8Accepted2/22ms436 KiB
9Accepted2/24ms424 KiB
10Accepted2/24ms416 KiB
11Accepted2/23ms432 KiB
12Accepted2/2145ms1156 KiB
13Accepted2/2143ms1016 KiB
14Accepted2/2142ms1216 KiB
15Accepted2/2279ms2252 KiB
16Accepted2/2277ms6196 KiB
17Accepted2/2280ms2352 KiB
18Accepted2/2275ms2188 KiB
19Accepted2/286ms1076 KiB
20Accepted2/2119ms1076 KiB
21Accepted2/259ms1076 KiB
22Accepted2/2144ms1200 KiB