152772025-02-17 20:20:03antiA lehető legkevesebb metróval utazás (40 pont)cpp17Hibás válasz 22/40345ms4404 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 << " ";
            }
        }

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

    }
    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base22/40
1Elfogadva0/01ms316 KiB
2Elfogadva0/056ms316 KiB
3Hibás válasz0/21ms500 KiB
4Elfogadva2/21ms316 KiB
5Elfogadva2/22ms316 KiB
6Hibás válasz0/21ms316 KiB
7Hibás válasz0/24ms316 KiB
8Hibás válasz0/24ms412 KiB
9Hibás válasz0/223ms316 KiB
10Hibás válasz0/217ms424 KiB
11Hibás válasz0/24ms316 KiB
12Elfogadva2/279ms464 KiB
13Elfogadva2/279ms508 KiB
14Elfogadva2/259ms464 KiB
15Elfogadva2/2331ms4368 KiB
16Elfogadva2/2328ms4256 KiB
17Elfogadva2/2340ms4404 KiB
18Elfogadva2/2345ms4404 KiB
19Elfogadva2/228ms640 KiB
20Hibás válasz0/246ms648 KiB
21Elfogadva2/213ms316 KiB
22Hibás válasz0/257ms472 KiB