229162026-01-16 08:47:29BencuA lehető legkevesebb metróval utazás (40 pont)cpp17Wrong answer 3/40426ms7024 KiB
#include <bits/stdc++.h>

using namespace std;
int n,m,x,y;
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]=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]==0) {
                L[i]=L[t]+1;
                E[i]=t;
                utolso++;
                vsor[utolso]=i;
            }
        }
        elso++;
    }
}

int main()
{
    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]=j;
            }
            //cout<<j<<"-"<<y<<endl;
            if (j==y) {
                v++;
                V[v]=j;
            }
        }
    }
    //cout<<k<<" "<<v<<" "<<x<<" "<<y<<endl;
    for (int j=1; j<=m; j++) {
        for (int i=1; i<=n; i++) {
            if (b[i][j]==1) {
                /*if (j==x) {
                    k++;
                    K[k]=j;
                }
                if (j==y) {
                    v++;
                    V[v]=j;
                }*/
                for (int p=i+1; p<=n; p++) {
                    if (b[p][j]==1) {
                        a[i][p]=1;
                        a[p][i]=1;
                    }
                }
            }
        }
    }
    /*for (int i=1; i<=n; i++) {
        for (int j=1; j<=n; j++) cout<<a[i][j]<<" ";
        cout<<endl;
    }*/
    int MIN=202,mi,MI[201];
    for (int i=1; i<=k; i++) {
        bejar(i);
        for (int j=1; j<=v; j++) {
            //cout<<L[j]<<" ";
            if (L[j]<MIN) {
                MIN=L[j];
                mi=MIN;
                for (int q=1; q<=MIN; q++) {
                    MI[MIN-q+1]=j;
                    j=E[j];
                }
            }
        }
    }
    cout<<MIN<<endl;
    for (int i=MIN; i>=1; i--) cout<<MI[i]<<" ";
    return 0;
}
SubtaskSumTestVerdictTimeMemory
base3/40
1Accepted0/01ms512 KiB
2Wrong answer0/010ms1076 KiB
3Partially correct1/21ms316 KiB
4Wrong answer0/21ms316 KiB
5Wrong answer0/21ms316 KiB
6Wrong answer0/21ms316 KiB
7Wrong answer0/22ms316 KiB
8Partially correct1/22ms316 KiB
9Partially correct1/24ms512 KiB
10Wrong answer0/24ms316 KiB
11Wrong answer0/22ms564 KiB
12Wrong answer0/212ms1076 KiB
13Wrong answer0/213ms1232 KiB
14Wrong answer0/210ms1292 KiB
15Wrong answer0/2416ms7024 KiB
16Wrong answer0/2416ms6892 KiB
17Wrong answer0/2426ms2324 KiB
18Wrong answer0/2412ms2348 KiB
19Wrong answer0/28ms1236 KiB
20Wrong answer0/210ms1228 KiB
21Wrong answer0/24ms1260 KiB
22Wrong answer0/29ms1200 KiB