93392024-02-20 16:19:28AblablablaA lehető legkevesebb metróval utazás (40 pont)cpp17Hibás válasz 18/40340ms62988 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>> megallok(m);
    for(int i = 0; i < n; i++){
        int db;
        cin >> db;

        while(db--){
            int a;
            cin >> a;
            a--;

            megallok[a].push_back(i);
        }
    }

    vector<vector<int>> eler(n, vector<int>(n, 0));
    for(int i = 0; i < m; i++){
        for(int j = 0; j < megallok[i].size(); j++){
            for(int k = j + 1; k < megallok[i].size(); k++){
                eler[megallok[i][j]].push_back(megallok[i][k]);
                eler[megallok[i][k]].push_back(megallok[i][j]);
            }
        }
    }


    queue<pii> bejar;
    for(int i = 0; i < megallok[ind].size(); i++){
        bejar.push({megallok[ind][i], -1});
    }

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

    bool eleri = 0;
    int utolso = 0;
    vector<int> elozok(n, 0);
    vector<bool> bejart(n, 0);

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

        if(bejart[akt]) continue;

        bejart[akt] = 1;
        elozok[akt] = elozo;
        if(cel.count(akt)){
            utolso = akt;
            eleri = 1;
            break;
        }

        for(int x : eler[akt]){
            if(bejart[x]) continue;

            bejar.push({x, akt});
        }
    }

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

        cout << megoldas.size() << "\n";
        reverse(megoldas.begin(), megoldas.end());
        for(int x : megoldas){
            cout << x + 1 << " ";
        }
        cout << "\n";
    } else{
        cout << "-1\n";
    }
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base18/40
1Elfogadva0/03ms1808 KiB
2Elfogadva0/08ms4056 KiB
3Elfogadva2/23ms2720 KiB
4Elfogadva2/23ms2764 KiB
5Elfogadva2/23ms3196 KiB
6Elfogadva2/23ms2892 KiB
7Hibás válasz0/24ms3420 KiB
8Elfogadva2/24ms3652 KiB
9Elfogadva2/26ms4128 KiB
10Elfogadva2/24ms3876 KiB
11Elfogadva2/24ms3756 KiB
12Hibás válasz0/28ms5512 KiB
13Hibás válasz0/28ms5620 KiB
14Hibás válasz0/28ms5788 KiB
15Futási hiba0/2326ms62988 KiB
16Futási hiba0/2340ms62928 KiB
17Futási hiba0/2328ms62924 KiB
18Futási hiba0/2326ms62904 KiB
19Hibás válasz0/26ms5388 KiB
20Hibás válasz0/27ms5796 KiB
21Hibás válasz0/24ms5396 KiB
22Elfogadva2/28ms6132 KiB