152782025-02-17 20:21:11antiA lehető legkevesebb metróval utazás (40 pont)cpp17Accepted 40/40300ms4408 KiB
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    int n, m, ind, erk;
    cin >> n >> m >> ind >> erk;
    vector<vector<int>> vonalak(n);
    for(int i=0; i<n; i++){
        int a;
        cin >> a;
        vonalak[i].resize(a);
        for(int j=0; j<a; j++){
            cin >> vonalak[i][j];
        }
    }

    vector<vector<int>> graf(n);
    for(int i=0; i<n; i++){
        for(int j=i+1; j<n; j++){
            bool kozos = false;
            for(int allomas : vonalak[i]){
                if(find(vonalak[j].begin(), vonalak[j].end(), allomas) != vonalak[j].end()){
                    kozos = true;
                    break;
                }
            }
            if(kozos){
                graf[i].push_back(j);
                graf[j].push_back(i);
            }
        }
    }

    vector<int> start_vonalak, end_vonalak;
    for(int i=0; i<n; i++){
        if(find(vonalak[i].begin(), vonalak[i].end(), ind) != vonalak[i].end()){
            start_vonalak.push_back(i);
        }
        if(find(vonalak[i].begin(), vonalak[i].end(), erk) != vonalak[i].end()){
            end_vonalak.push_back(i);
        }
    }

    queue<int> q;
    vector<int> elozo(n, -1);
    vector<bool> v(n, false);

    for(int vonal : start_vonalak){
        q.push(vonal);
        v[vonal] = true;
    }

    while(!q.empty()){
        int akt_vonal = q.front();
        q.pop();

        if(find(end_vonalak.begin(), end_vonalak.end(), akt_vonal) != end_vonalak.end()){
            vector<int> ut;
            for(int v=akt_vonal; v!=-1; v = elozo[v]){
                ut.push_back(v);
            }
            reverse(ut.begin(), ut.end());

            cout << ut.size() << endl;
            for(int i : ut){
                cout << i+1 << " ";
            }
            return 0;
        }

        for(int szomszed : graf[akt_vonal]){
            if(!v[szomszed]){
                q.push(szomszed);
                elozo[szomszed] = akt_vonal;
                v[szomszed] = true;
            }
        }

    }
    cout << -1;
    return 0;
}
SubtaskSumTestVerdictTimeMemory
base40/40
1Accepted0/01ms316 KiB
2Accepted0/034ms316 KiB
3Accepted2/21ms316 KiB
4Accepted2/21ms508 KiB
5Accepted2/22ms404 KiB
6Accepted2/21ms316 KiB
7Accepted2/23ms316 KiB
8Accepted2/24ms404 KiB
9Accepted2/214ms432 KiB
10Accepted2/210ms428 KiB
11Accepted2/23ms316 KiB
12Accepted2/246ms316 KiB
13Accepted2/246ms472 KiB
14Accepted2/235ms500 KiB
15Accepted2/2294ms4232 KiB
16Accepted2/2291ms4408 KiB
17Accepted2/2300ms4404 KiB
18Accepted2/2298ms4404 KiB
19Accepted2/217ms316 KiB
20Accepted2/228ms456 KiB
21Accepted2/28ms316 KiB
22Accepted2/235ms468 KiB