229322026-01-16 09:13:09BencuA lehető legkevesebb metróval utazás (40 pont)cpp17Hibás válasz 36/40435ms2364 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;
                int d=V[j];
                for (int q=1; q<=MIN; q++) {
                    MI[MIN-q+1]=d;
                    d=E[d];
                }
            }
        }
    }
    if (MIN==0) 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
base36/40
1Elfogadva0/01ms316 KiB
2Elfogadva0/010ms1076 KiB
3Hibás válasz0/21ms316 KiB
4Elfogadva2/21ms316 KiB
5Hibás válasz0/21ms316 KiB
6Elfogadva2/21ms524 KiB
7Elfogadva2/22ms376 KiB
8Elfogadva2/22ms316 KiB
9Elfogadva2/24ms316 KiB
10Elfogadva2/24ms396 KiB
11Elfogadva2/22ms688 KiB
12Elfogadva2/212ms1244 KiB
13Elfogadva2/212ms1244 KiB
14Elfogadva2/210ms1224 KiB
15Elfogadva2/2430ms2280 KiB
16Elfogadva2/2428ms2364 KiB
17Elfogadva2/2435ms2184 KiB
18Elfogadva2/2430ms2328 KiB
19Elfogadva2/28ms1076 KiB
20Elfogadva2/28ms1076 KiB
21Elfogadva2/24ms1076 KiB
22Elfogadva2/210ms1076 KiB