133682025-01-07 17:21:45BucsMateA lehető legkevesebb metróval utazás (40 pont)cpp17Elfogadva 40/40317ms11148 KiB
#include <iostream>
#include <vector>
#include <queue>
#include <stack>

using namespace std;

int main()
{
    int N, M, IND, ERK;
    cin >> N >> M >> IND >> ERK;
    vector<vector<int>> allomasbol_metro(M+1), metrobol_allomas(N+1);

    for(int i = 1; i <= N; i++){
        int db;
        cin >> db;
        for(int j = 1; j <= db; j++){
            int temp;
            cin >> temp;
            allomasbol_metro[temp].push_back(i);
            metrobol_allomas[i].push_back(temp);
        }
    }

    vector<int> allomas_tav(M+1, -1), elozo_allomas(M+1), elozo_metro(M+1);
    vector<bool> visited_metro(N+1, false);

    queue<int> q;
    q.push(IND);
    allomas_tav[IND] = 0;

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

        for(int uj_metro : allomasbol_metro[jelenlegi_allomas]){
            if(visited_metro[uj_metro]){
                continue;
            }
            visited_metro[uj_metro] = true;

            for(int uj_allomas : metrobol_allomas[uj_metro]){
                if(allomas_tav[uj_allomas] != -1){
                    continue;
                }
                allomas_tav[uj_allomas] = allomas_tav[jelenlegi_allomas] + 1;
                elozo_allomas[uj_allomas] = jelenlegi_allomas;
                elozo_metro[uj_allomas] = uj_metro;
                q.push(uj_allomas);
            }
        }
    }
    if(allomas_tav[ERK] == -1){
        cout << -1 << endl;
        return 0;
    }

    stack<int> st;
    int allomas = ERK;
    while(allomas != IND){
        st.push(elozo_metro[allomas]);
        allomas = elozo_allomas[allomas];
    }
    cout << st.size() << endl;
    while(!st.empty()){
        cout << st.top() << " ";
        st.pop();
    }
    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base40/40
1Elfogadva0/01ms316 KiB
2Elfogadva0/06ms1076 KiB
3Elfogadva2/21ms316 KiB
4Elfogadva2/21ms316 KiB
5Elfogadva2/21ms316 KiB
6Elfogadva2/21ms508 KiB
7Elfogadva2/22ms564 KiB
8Elfogadva2/22ms564 KiB
9Elfogadva2/24ms784 KiB
10Elfogadva2/24ms564 KiB
11Elfogadva2/22ms564 KiB
12Elfogadva2/27ms1240 KiB
13Elfogadva2/27ms1080 KiB
14Elfogadva2/26ms1100 KiB
15Elfogadva2/2310ms11148 KiB
16Elfogadva2/2317ms11040 KiB
17Elfogadva2/2310ms11060 KiB
18Elfogadva2/2314ms11124 KiB
19Elfogadva2/24ms824 KiB
20Elfogadva2/26ms1044 KiB
21Elfogadva2/23ms568 KiB
22Elfogadva2/26ms964 KiB