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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base20/40
1Elfogadva0/03ms1852 KiB
2Elfogadva0/04ms3232 KiB
3Részben helyes1/23ms2124 KiB
4Elfogadva2/22ms2156 KiB
5Elfogadva2/23ms2500 KiB
6Elfogadva2/22ms2532 KiB
7Elfogadva2/23ms2944 KiB
8Elfogadva2/23ms3104 KiB
9Elfogadva2/24ms3584 KiB
10Hibás válasz0/24ms3856 KiB
11Elfogadva2/23ms3568 KiB
12Hibás válasz0/26ms4688 KiB
13Hibás válasz0/24ms4752 KiB
14Elfogadva2/24ms4756 KiB
15Időlimit túllépés0/2601ms21012 KiB
16Időlimit túllépés0/2550ms21076 KiB
17Időlimit túllépés0/2570ms20884 KiB
18Időlimit túllépés0/2559ms21288 KiB
19Hibás válasz0/24ms4268 KiB
20Hibás válasz0/24ms4640 KiB
21Elfogadva2/24ms3984 KiB
22Részben helyes1/24ms4844 KiB