93442024-02-20 17:16:10AblablablaA lehető legkevesebb metróval utazás (40 pont)cpp17Accepted 40/40307ms24824 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";
}
SubtaskSumTestVerdictTimeMemory
base40/40
1Accepted0/03ms1816 KiB
2Accepted0/07ms3224 KiB
3Accepted2/23ms2244 KiB
4Accepted2/23ms2452 KiB
5Accepted2/23ms2836 KiB
6Accepted2/23ms2840 KiB
7Accepted2/24ms3116 KiB
8Accepted2/24ms3164 KiB
9Accepted2/26ms3520 KiB
10Accepted2/24ms3396 KiB
11Accepted2/24ms3084 KiB
12Accepted2/28ms4172 KiB
13Accepted2/28ms4384 KiB
14Accepted2/28ms4468 KiB
15Accepted2/2307ms24736 KiB
16Accepted2/2307ms24824 KiB
17Accepted2/2307ms24824 KiB
18Accepted2/2307ms24576 KiB
19Accepted2/26ms4628 KiB
20Accepted2/27ms4752 KiB
21Accepted2/24ms4396 KiB
22Accepted2/27ms5232 KiB