156462025-02-21 13:51:59999A lehető legkevesebb metróval utazás (40 pont)cpp17Elfogadva 40/40317ms6636 KiB
// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize("O3,unroll-loops,fast-math") 
//#pragma GCC target("avx2,popcnt,lzcnt")  

const int INF=-1;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n,m,ind,erk;cin>>n>>m>>ind>>erk;
    vector<vector<int>> boo(n+5,vector<int>(n+5));
    vector<vector<int>> a(m+5);
    ind--;erk--;
    for(int i = 0;i<n;i++){
        int x;cin>>x;
        for(int j = 0;j<x;j++){
            int b;cin>>b;
            a[--b].push_back(i);
        }
    } 
    for(int i = 0;i<m;i++){
        if(a[i].size()<=1)continue;
        for(int j = 0;j<a[i].size();j++){
            for(int k = 0;k<j;k++){
                boo[a[i][j]][a[i][k]]=1;
                boo[a[i][k]][a[i][j]]=1;
            }
        }
    }/*
    cout<<ind<<' '<<erk<<endl;
    for(int i = 0;i<=m;i++){
        for(int j = 0;j<a[i].size();j++){
            cout<<a[i][j];
        }cout<<endl;
    }*/
    queue<int> q;
    vector<int> dis(n+5,INF),hon(n+5,-1);
    for(int i : a[ind]){
        q.push(i);
        dis[i]=1;
    }//return 1;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i = 0;i<n;i++){
            if(dis[i]==INF&&boo[i][u]){
                dis[i]=dis[u]+1;
                hon[i]=u;
                q.push(i);
            }
        }
    }//for(int i : dis)cout<<i<<' ';cout<<endl;
    int ans=INT_MAX,mely=-1;
    for(int i : a[erk]){
        if(dis[i]==INF){
            cout<<-1;return 0;
        }
        if(ans>dis[i]){
            mely=i;
            ans=dis[i];
        }
    }//return 1;
    vector<int> temp;
    while(mely!=-1){
        temp.push_back(mely);
        mely=hon[mely];
    }cout<<ans<<endl;
    reverse(temp.begin(),temp.end());
    for(int i : temp)cout<<i+1<<' ';
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base40/40
1Elfogadva0/01ms316 KiB
2Elfogadva0/04ms1092 KiB
3Elfogadva2/21ms512 KiB
4Elfogadva2/21ms316 KiB
5Elfogadva2/21ms500 KiB
6Elfogadva2/21ms316 KiB
7Elfogadva2/22ms316 KiB
8Elfogadva2/22ms564 KiB
9Elfogadva2/22ms716 KiB
10Elfogadva2/22ms756 KiB
11Elfogadva2/21ms508 KiB
12Elfogadva2/24ms1076 KiB
13Elfogadva2/24ms1024 KiB
14Elfogadva2/24ms1152 KiB
15Elfogadva2/2316ms6588 KiB
16Elfogadva2/2314ms6636 KiB
17Elfogadva2/2317ms6592 KiB
18Elfogadva2/2317ms6452 KiB
19Elfogadva2/23ms820 KiB
20Elfogadva2/23ms1076 KiB
21Elfogadva2/22ms764 KiB
22Elfogadva2/24ms1040 KiB