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