93432024-02-20 17:12:11AblablablaA lehető legkevesebb metróval utazás (40 pont)cpp17Időlimit túllépés 32/40586ms14880 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);

    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]){
            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
base32/40
1Elfogadva0/03ms1816 KiB
2Elfogadva0/08ms3224 KiB
3Elfogadva2/23ms2220 KiB
4Elfogadva2/23ms2460 KiB
5Elfogadva2/23ms2604 KiB
6Elfogadva2/23ms2664 KiB
7Elfogadva2/24ms3160 KiB
8Elfogadva2/24ms3504 KiB
9Elfogadva2/26ms3972 KiB
10Elfogadva2/24ms3932 KiB
11Elfogadva2/24ms3620 KiB
12Elfogadva2/28ms4592 KiB
13Elfogadva2/28ms4720 KiB
14Elfogadva2/28ms4804 KiB
15Időlimit túllépés0/2564ms14388 KiB
16Időlimit túllépés0/2570ms14716 KiB
17Időlimit túllépés0/2586ms14880 KiB
18Időlimit túllépés0/2554ms14872 KiB
19Elfogadva2/26ms5952 KiB
20Elfogadva2/27ms6192 KiB
21Elfogadva2/24ms5828 KiB
22Elfogadva2/28ms6664 KiB