94832024-02-22 11:08:49Vkrisztian01A lehető legkevesebb metróval utazás (40 pont)cpp11Részben helyes 20/40601ms21288 KiB
#include <iostream>
#include<vector>
#include<queue>

using namespace std;

int vonalszam,allomasszam,start,finish,a,b,aktualis,elozo,hogyan;
vector<vector<int> > vonalak;
vector<vector<int> > allomasok;
vector<int>honnan;
vector<int>melyikvonal;
vector<bool>hasznaltvonal;
vector<int>ki;
queue<pair<int,int> >seged;

int main()
{
    cin.tie(0);
	ios::sync_with_stdio(false);
    cin>>vonalszam>>allomasszam>>start>>finish;
    vonalak.resize(vonalszam+1);
    allomasok.resize(allomasszam+1);
    honnan.assign(allomasszam+1,-1);
    hasznaltvonal.assign(vonalszam+1,false);
    melyikvonal.resize(allomasszam+1);
    for(int i=1;i<=vonalszam;i++)
    {
        cin>>a;
        while(a--)
        {
            cin>>b;
            vonalak[i].push_back(b);
            allomasok[b].push_back(i);
        }
    }
    seged.push(make_pair(start,0));
    while(!seged.empty())
    {
        aktualis=seged.front().first;
        elozo=seged.front().second;
        seged.pop();
        honnan[aktualis]=elozo;
        if(aktualis==finish) break;
        for(auto v:allomasok[aktualis])
        {
            if(hasznaltvonal[v]) continue;
            hasznaltvonal[v]=true;
            for(auto to:vonalak[v])
            {
                if(honnan[to]!=-1) continue;
                melyikvonal[to]=v;
                seged.push(make_pair(to,aktualis));
            }
        }
    }
    if(honnan[finish]==-1)
    {
        cout<<-1;
        return 0;
    }
    while(finish!=start)
    {
        ki.push_back(melyikvonal[finish]);
        finish=honnan[finish];
    }
    cout<<ki.size()<<endl;
    for(int i=ki.size()-1;i>=0;i--) cout<<ki[i]<<" ";

    return 0;
}