229272026-01-16 09:05:50BencuA lehető legkevesebb metróval utazás (40 pont)cpp17Wrong answer 23/40430ms2356 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]=0;
    int vsor[201],elso,utolso;
    elso=1;
    utolso=1;
    vsor[elso]=g;
    //L[g]=1;
    while (elso<=utolso) {
        int t=vsor[elso];
        for (int i=1; i<=n; i++) {
            if (a[i][t]==1 && L[i]==0 && i!=g) {
                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]=i;
            }
            //cout<<j<<"-"<<y<<endl;
            if (j==y) {
                v++;
                V[v]=i;
            }
        }
    }
    //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 (i==x &&) {
                    k++;
                    K[k]=j;
                }
                if (i==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(K[i]);
        //for (int j=1; j<=n; j++) cout<<L[j]<<" ";
        for (int j=1; j<=v; j++) {
            //cout<<L[j]<<" ";
            if (L[V[j]]<MIN) {
                //cout<<V[j]<<L[V[j]]<<endl;
                MIN=L[V[j]];
                c=K[i];
                mi=MIN;
                for (int q=1; q<=MIN; q++) {
                    MI[MIN-q+1]=V[j];
                    j=E[V[j]];
                }
            }
        }
    }
    cout<<MIN+1<<endl;
    cout<<c<<" ";
    for (int i=1; i<=MIN; i++) cout<<MI[i]<<" ";
    return 0;
}
SubtaskSumTestVerdictTimeMemory
base23/40
1Accepted0/01ms316 KiB
2Wrong answer0/010ms1076 KiB
3Accepted2/21ms508 KiB
4Partially correct1/21ms316 KiB
5Accepted2/21ms316 KiB
6Wrong answer0/21ms316 KiB
7Partially correct1/22ms316 KiB
8Accepted2/22ms316 KiB
9Accepted2/24ms408 KiB
10Partially correct1/23ms316 KiB
11Partially correct1/22ms564 KiB
12Partially correct1/212ms1112 KiB
13Partially correct1/210ms1244 KiB
14Partially correct1/29ms1192 KiB
15Partially correct1/2430ms2180 KiB
16Partially correct1/2426ms2168 KiB
17Partially correct1/2428ms2280 KiB
18Partially correct1/2428ms2356 KiB
19Partially correct1/28ms1076 KiB
20Partially correct1/28ms1076 KiB
21Partially correct1/24ms1076 KiB
22Partially correct1/29ms1076 KiB