9344 2024. 02. 20 17:16:10 Ablablabla A lehető legkevesebb metróval utazás (40 pont) cpp17 Elfogadva 40/40 307ms 24824 KiB
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

struct pont{
    int a;
    int t;
    int e;
};

int main()
{
    int n, m, ind, erk;
    cin >> n >> m >> ind >> erk;
    ind--; erk--;

    vector<vector<int>> elerM(n); // vonatbol megalloba
    vector<vector<int>> elerV(m); // megallobol vonatba

    for(int i = 0; i < n; i++){
        int db;
        cin >> db;

        for(int j = 0; j < db; j++){
            int a;
            cin >> a;
            a--;

            elerM[i].push_back(a);
            elerV[a].push_back(i);
        }
    }

    queue<int> bejar;
    vector<int> elozok(n, -2);
    for(int i = 0; i < elerV[ind].size(); i++){
        bejar.push(elerV[ind][i]);
        elozok[elerV[ind][i]] = -1;
    }

    set<int> cel;
    for(int i = 0; i < elerV[erk].size(); i++){
        cel.insert(elerV[erk][i]);
    }

    int utolso = -1;
    vector<bool> bejart(n, 0);
    vector<bool> bejartM(m, 0);

    while(!bejar.empty()){
        int akt = bejar.front();
        bejar.pop();

        if(bejart[akt]) continue;

        bejart[akt] = 1;

        if(cel.count(akt)){
            utolso = akt;
            break;
        }

        for(int hely : elerM[akt]){
            if(bejartM[hely]) continue;

            bejartM[hely] = 1;

            for(int x : elerV[hely]){
                if(bejart[x]) continue;
                if(elozok[x] != -2) continue;

                elozok[x] = akt;
                bejar.push(x);
            }
        }
    }

    if(utolso == -1){
        cout << "-1\n";
        return 0;
    }

    vector<int> megoldas;
    while(utolso != -1){
        megoldas.push_back(utolso + 1);
        utolso = elozok[utolso];
    }

    reverse(megoldas.begin(), megoldas.end());

    cout << megoldas.size() << "\n";
    for(int x : megoldas){
        cout << x << " ";
    }
    cout << "\n";
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 40/40
1 Elfogadva 0/0 3ms 1816 KiB
2 Elfogadva 0/0 7ms 3224 KiB
3 Elfogadva 2/2 3ms 2244 KiB
4 Elfogadva 2/2 3ms 2452 KiB
5 Elfogadva 2/2 3ms 2836 KiB
6 Elfogadva 2/2 3ms 2840 KiB
7 Elfogadva 2/2 4ms 3116 KiB
8 Elfogadva 2/2 4ms 3164 KiB
9 Elfogadva 2/2 6ms 3520 KiB
10 Elfogadva 2/2 4ms 3396 KiB
11 Elfogadva 2/2 4ms 3084 KiB
12 Elfogadva 2/2 8ms 4172 KiB
13 Elfogadva 2/2 8ms 4384 KiB
14 Elfogadva 2/2 8ms 4468 KiB
15 Elfogadva 2/2 307ms 24736 KiB
16 Elfogadva 2/2 307ms 24824 KiB
17 Elfogadva 2/2 307ms 24824 KiB
18 Elfogadva 2/2 307ms 24576 KiB
19 Elfogadva 2/2 6ms 4628 KiB
20 Elfogadva 2/2 7ms 4752 KiB
21 Elfogadva 2/2 4ms 4396 KiB
22 Elfogadva 2/2 7ms 5232 KiB