147292025-01-30 09:38:15mateA lehető legkevesebb metróval utazás (40 pont)cpp17Hibás válasz 6/40584ms32000 KiB
#include <bits/stdc++.h>
using namespace std;

vector <vector <int>> graf;
vector <set <int>> lines;
vector <vector <int>> szom;
vector <int> parent;

void bfs(int p, int ve){
    queue <int> q;
    q.push(p);
    while(!q.empty()){
        int csucs = q.front();
        q.pop();
        for(int x : szom[csucs]){
            if(parent[x] == 0){
                parent[x] = csucs;
            }
            if(x == ve){
                return;
            }
        }
    }
}


int main() {
	int n,m,kezdo,veg; cin >> n >> m >> kezdo >> veg;
    szom.resize(n+1);
    lines.resize(n+1);
    parent.resize(n+1,0);
    int kez,ve;

    for(int i = 1; i <= n; i++){
        int a,b; cin >> a;
        for(int j = 0; j < a; j++){
            cin >> b;
            if(kezdo == b){
                kez = i;
            }
            if(veg == b){
                ve = i;
            }
            lines[i].insert(b);
        }
    }
    bool kesz = 0;
    for(int i = 1; i < n; i++){
        for(int j = i + 1;  j <= n; j++){
            for(int x : lines[i]){
                if(kesz)    break;
                for(int y :lines[j]){
                    if(x == y){
                        szom[i].push_back(j);
                        szom[j].push_back(i);
                        kesz = 1;
                        break;
                    }
                }
            }
            kesz = 0;
        }
    }
    for(int i = 1; i <= n; i++){
        for(int x : szom[i]){
            cerr << x << ' ';
        }
        cerr << '\n';
    }

    bfs(kez, ve);

    if(parent[ve] == 0){
        cout << -1;
        return 0;
    }
    int k = ve;
    vector <int> ans;
    ans.push_back(k);
    while(parent[k] != 0){
        ans.push_back(parent[k]);
        k = parent[k];
    }
    reverse(ans.begin(),ans.end());
    cout << ans.size() << '\n';
    for(int x : ans){
        cout << x << ' ';
    }
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base6/40
1Elfogadva0/01ms316 KiB
2Hibás válasz0/0409ms820 KiB
3Hibás válasz0/21ms500 KiB
4Hibás válasz0/21ms316 KiB
5Hibás válasz0/26ms464 KiB
6Elfogadva2/21ms316 KiB
7Hibás válasz0/225ms552 KiB
8Elfogadva2/232ms580 KiB
9Elfogadva2/2177ms564 KiB
10Hibás válasz0/2140ms736 KiB
11Hibás válasz0/224ms316 KiB
12Időlimit túllépés0/2584ms1076 KiB
13Időlimit túllépés0/2584ms1092 KiB
14Hibás válasz0/2439ms820 KiB
15Futási hiba0/2310ms32000 KiB
16Futási hiba0/2310ms32000 KiB
17Futási hiba0/2317ms32000 KiB
18Futási hiba0/2310ms32000 KiB
19Hibás válasz0/2184ms820 KiB
20Hibás válasz0/2326ms924 KiB
21Hibás válasz0/276ms624 KiB
22Hibás válasz0/2416ms992 KiB