156362025-02-21 12:54:25999A lehető legkevesebb metróval utazás (40 pont)cpp17Futási hiba 2/40500ms32000 KiB
// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;

const int INF=1e12;

int main() {
    int n,m,ind,erk;cin>>n>>m>>ind>>erk;
    vector<vector<int>> v(n+5);
    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++){
        for(int j = 0;j<a[i].size();j++){
            for(int k = 0;k<j;k++){
                if(boo[a[i][j]][a[i][k]])continue;
                boo[a[i][j]][a[i][k]]=1;
                v[a[i][k]].push_back(a[i][j]);
                v[a[i][j]].push_back(a[i][k]);
            }
        }
    }
    queue<int> q;
    vector<int> dis(n+5,INF),hon(n+5,-1);
    for(int i : a[ind]){
        q.push(i);
        dis[i]=1;
        hon[i]=0;
    }
    hon[0]=-1;
    int cnt=0;
    while(!q.empty()){
        cnt++;
        if(cnt>n*n+1000)return 1;
        int u=q.front();
        q.pop();
        for(int i : v[u]){
            if(dis[i]==INF){
                dis[i]=dis[u]+1;
                hon[i]=u;
                q.push(i);
            }
        }
    }
    int ans=-1,mely=-1;
    for(int i : a[erk]){
        if(ans<dis[i]){
            mely=i;
            ans=dis[i];
        }
    }
    cout<<ans<<endl;
    if(ans!=-1){
        vector<int> temp;
        while(mely>=0){
            temp.push_back(mely);
            mely=hon[mely];
        }
        reverse(temp.begin(),temp.end());
        for(int i : temp)cout<<i+1<<' ';
    }
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base2/40
1Elfogadva0/01ms500 KiB
2Futási hiba0/064ms32000 KiB
3Hibás válasz0/21ms316 KiB
4Elfogadva2/21ms316 KiB
5Hibás válasz0/21ms316 KiB
6Hibás válasz0/21ms316 KiB
7Futási hiba0/250ms32000 KiB
8Futási hiba0/261ms32000 KiB
9Futási hiba0/252ms32000 KiB
10Futási hiba0/252ms32000 KiB
11Futási hiba0/261ms32000 KiB
12Futási hiba0/265ms32000 KiB
13Futási hiba0/265ms32000 KiB
14Futási hiba0/263ms32000 KiB
15Futási hiba0/2486ms32000 KiB
16Futási hiba0/2500ms32000 KiB
17Futási hiba0/2497ms32000 KiB
18Futási hiba0/2488ms32000 KiB
19Futási hiba0/263ms32000 KiB
20Futási hiba0/263ms32000 KiB
21Futási hiba0/250ms32000 KiB
22Futási hiba0/263ms32000 KiB