133662025-01-07 17:19:46BucsMateA lehető legkevesebb metróval utazás (40 pont)cpp17Futási hiba 38/40321ms32000 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);
            }
        }
    }
    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
base38/40
1Elfogadva0/01ms316 KiB
2Elfogadva0/06ms1076 KiB
3Elfogadva2/21ms316 KiB
4Elfogadva2/21ms500 KiB
5Elfogadva2/22ms316 KiB
6Futási hiba0/246ms32000 KiB
7Elfogadva2/23ms564 KiB
8Elfogadva2/23ms752 KiB
9Elfogadva2/24ms904 KiB
10Elfogadva2/24ms820 KiB
11Elfogadva2/22ms564 KiB
12Elfogadva2/27ms1076 KiB
13Elfogadva2/27ms1192 KiB
14Elfogadva2/26ms1076 KiB
15Elfogadva2/2319ms15668 KiB
16Elfogadva2/2319ms15500 KiB
17Elfogadva2/2321ms16000 KiB
18Elfogadva2/2319ms15788 KiB
19Elfogadva2/24ms820 KiB
20Elfogadva2/26ms1076 KiB
21Elfogadva2/23ms564 KiB
22Elfogadva2/26ms1160 KiB