9488 2024. 02. 22 11:31:59 Vkrisztian01 A lehető legkevesebb metróval utazás (40 pont) cpp11 Elfogadva 40/40 126ms 25356 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 Összpont Teszt Verdikt Idő Memória
base 40/40
1 Elfogadva 0/0 3ms 1824 KiB
2 Elfogadva 0/0 4ms 3400 KiB
3 Elfogadva 2/2 3ms 2268 KiB
4 Elfogadva 2/2 3ms 2448 KiB
5 Elfogadva 2/2 3ms 2752 KiB
6 Elfogadva 2/2 3ms 2756 KiB
7 Elfogadva 2/2 3ms 3280 KiB
8 Elfogadva 2/2 4ms 3708 KiB
9 Elfogadva 2/2 4ms 3920 KiB
10 Elfogadva 2/2 4ms 3980 KiB
11 Elfogadva 2/2 3ms 3512 KiB
12 Elfogadva 2/2 4ms 4636 KiB
13 Elfogadva 2/2 6ms 4688 KiB
14 Elfogadva 2/2 4ms 4836 KiB
15 Elfogadva 2/2 122ms 24760 KiB
16 Elfogadva 2/2 126ms 24920 KiB
17 Elfogadva 2/2 126ms 24984 KiB
18 Elfogadva 2/2 122ms 25356 KiB
19 Elfogadva 2/2 4ms 4472 KiB
20 Elfogadva 2/2 4ms 4768 KiB
21 Elfogadva 2/2 4ms 4120 KiB
22 Elfogadva 2/2 4ms 4836 KiB