240962026-02-04 11:00:39ercseferencA lehető legkevesebb metróval utazás (40 pont)cpp17Elfogadva 40/40118ms11220 KiB
#include <bits/stdc++.h>
using namespace std;
int main()
{
    //ifstream f("szamok.txt");
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m,kezd,veg;
    cin>>n>>m>>kezd>>veg;
    vector<vector<int>>a(n+m+1);
    for(int i=1; i<=n; i++){
        int x; cin>>x;
        for(int j=0; j<x; j++){
            int y; cin>>y;
            a[y].push_back(m+i);
            a[m+i].push_back(y);}}
    vector<int>tav(n+m+1,1e9);
    vector<int>ut(n+m+1);
    queue<int>q;
    q.push(kezd);
    tav[kezd]=0;
    while(!q.empty()){
        int x=q.front();
        for(int i:a[x]){
            if(tav[i]>tav[x]+1){
                tav[i]=tav[x]+1;
                q.push(i);
                ut[i]=x;}}
        q.pop();}
    vector<int>nyom;
    if(tav[veg]==1e9){
        cout<<-1;}
    else{
        int t=veg;
        while(t!=kezd){
            t=ut[t];
            if(t>m)nyom.push_back(t-m);}
        reverse(nyom.begin(), nyom.end());
    cout<<nyom.size()<<endl;
    for(int i:nyom)cout<<i<<" ";}
    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base40/40
1Elfogadva0/01ms316 KiB
2Elfogadva0/03ms1076 KiB
3Elfogadva2/21ms316 KiB
4Elfogadva2/21ms316 KiB
5Elfogadva2/21ms316 KiB
6Elfogadva2/21ms316 KiB
7Elfogadva2/22ms580 KiB
8Elfogadva2/22ms564 KiB
9Elfogadva2/23ms820 KiB
10Elfogadva2/22ms564 KiB
11Elfogadva2/21ms564 KiB
12Elfogadva2/24ms1076 KiB
13Elfogadva2/24ms1076 KiB
14Elfogadva2/23ms1076 KiB
15Elfogadva2/2115ms11136 KiB
16Elfogadva2/2115ms11036 KiB
17Elfogadva2/2118ms11092 KiB
18Elfogadva2/2118ms11220 KiB
19Elfogadva2/23ms820 KiB
20Elfogadva2/23ms1076 KiB
21Elfogadva2/22ms748 KiB
22Elfogadva2/24ms916 KiB