94882024-02-22 11:31:59Vkrisztian01A lehető legkevesebb metróval utazás (40 pont)cpp11Elfogadva 40/40126ms25356 KiB
#include <iostream>
#include<vector>
#include<queue>

using namespace std;

int metro,allomas,start,finish,a,b,node;

vector<vector<int> > vonalak;
vector<vector<int> > allomasok;
vector<bool>hasznaltmetro;
vector<pair<int,int> > honnan;
queue<int>seged;
vector<int>ki;

int main()
{
    cin.tie(0);
	ios::sync_with_stdio(false);

    cin>>metro>>allomas>>start>>finish;
    vonalak.resize(metro+1);
    allomasok.resize(allomas+1);
    honnan.assign(allomas+1,make_pair(-1,-1));
    hasznaltmetro.assign(metro+1,false);
    for(int i=1;i<=metro;i++)
    {
        cin>>a;
        while(a--)
        {
            cin>>b;
            vonalak[i].push_back(b);
            allomasok[b].push_back(i);
        }
    }
    seged.push(start);
    honnan[start]=make_pair(0,0);
    while(!seged.empty())
    {
        node=seged.front();
        seged.pop();
        if(node==finish) break;
        for(auto me:allomasok[node])
        {
            if(hasznaltmetro[me]) continue;
            hasznaltmetro[me]=true;
            for(auto celallomas:vonalak[me])
            {
                if(honnan[celallomas].first!=-1) continue;
                honnan[celallomas]=make_pair(node,me);
                seged.push(celallomas);
            }
        }
    }
    if(honnan[finish].first==-1)
    {
        cout<<-1;
        return 0;
    }
    while(finish!=start)
    {
        ki.push_back(honnan[finish].second);
        finish=honnan[finish].first;
    }
    cout<<ki.size()<<endl;
    for(int i=ki.size()-1;i>=0;i--) cout<<ki[i]<<" ";
    return 0;
}