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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base40/40
1Elfogadva0/03ms1824 KiB
2Elfogadva0/04ms3400 KiB
3Elfogadva2/23ms2268 KiB
4Elfogadva2/23ms2448 KiB
5Elfogadva2/23ms2752 KiB
6Elfogadva2/23ms2756 KiB
7Elfogadva2/23ms3280 KiB
8Elfogadva2/24ms3708 KiB
9Elfogadva2/24ms3920 KiB
10Elfogadva2/24ms3980 KiB
11Elfogadva2/23ms3512 KiB
12Elfogadva2/24ms4636 KiB
13Elfogadva2/26ms4688 KiB
14Elfogadva2/24ms4836 KiB
15Elfogadva2/2122ms24760 KiB
16Elfogadva2/2126ms24920 KiB
17Elfogadva2/2126ms24984 KiB
18Elfogadva2/2122ms25356 KiB
19Elfogadva2/24ms4472 KiB
20Elfogadva2/24ms4768 KiB
21Elfogadva2/24ms4120 KiB
22Elfogadva2/24ms4836 KiB