93432024-02-20 17:12:11AblablablaA lehető legkevesebb metróval utazás (40 pont)cpp17Time limit exceeded 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";
}
SubtaskSumTestVerdictTimeMemory
base32/40
1Accepted0/03ms1816 KiB
2Accepted0/08ms3224 KiB
3Accepted2/23ms2220 KiB
4Accepted2/23ms2460 KiB
5Accepted2/23ms2604 KiB
6Accepted2/23ms2664 KiB
7Accepted2/24ms3160 KiB
8Accepted2/24ms3504 KiB
9Accepted2/26ms3972 KiB
10Accepted2/24ms3932 KiB
11Accepted2/24ms3620 KiB
12Accepted2/28ms4592 KiB
13Accepted2/28ms4720 KiB
14Accepted2/28ms4804 KiB
15Time limit exceeded0/2564ms14388 KiB
16Time limit exceeded0/2570ms14716 KiB
17Time limit exceeded0/2586ms14880 KiB
18Time limit exceeded0/2554ms14872 KiB
19Accepted2/26ms5952 KiB
20Accepted2/27ms6192 KiB
21Accepted2/24ms5828 KiB
22Accepted2/28ms6664 KiB