246882026-02-13 19:25:47szjA lehető legkevesebb metróval utazás (40 pont)cpp17Elfogadva 40/40128ms11440 KiB
#include <bits/stdc++.h>

using namespace std;

int main()
{
    //ifstream cin("f.txt");
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, m, i, j, ind, erk, a, b;
    cin >> n >> m >> ind >> erk;
    ind--;
    erk--;
    vector<vector<int>> all(m);
    vector<vector<int>> vona(n);
    for(i=0; i<n; i++)
    {
        cin >> a;
        for(j=0; j<a; j++)
        {
            cin >> b;
            b--;
            vona[i].push_back(b);
            all[b].push_back(i);
        }
    }
    int el[m];
    fill(el, el+m, -1);
    bool volt[n]={};
    int vonatel[n];
    queue<int>q;
    for(auto i: all[ind])
    {
        volt[i]=1;
        vonatel[i]=-1;
        q.push(i);
    }
    while(!q.empty())
    {
        a=q.front();
        q.pop();
        for(auto i:vona[a])
        {
            if(el[i]==-1)
            {
                el[i]=a;
                for(auto j : all[i])
                {
                    if(!volt[j])
                    {
                        q.push(j);
                        volt[j]=1;
                        vonatel[j]=a;
                    }
                }
            }
        }
    }
    vector<int> vec;
    if(el[erk]==-1)
    {
        cout << -1;
        return 0;
    }
    a=el[erk];
    while(a!=-1)
    {
        vec.push_back(a);
        a=vonatel[a];
    }
    cout <<vec.size() << endl;
    for(i=vec.size()-1; i>=0; i--)
    {
        cout << vec[i]+1 << " ";
    }
    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base40/40
1Elfogadva0/01ms316 KiB
2Elfogadva0/04ms1076 KiB
3Elfogadva2/21ms548 KiB
4Elfogadva2/21ms316 KiB
5Elfogadva2/22ms500 KiB
6Elfogadva2/21ms316 KiB
7Elfogadva2/22ms756 KiB
8Elfogadva2/22ms616 KiB
9Elfogadva2/22ms820 KiB
10Elfogadva2/23ms756 KiB
11Elfogadva2/22ms756 KiB
12Elfogadva2/24ms1076 KiB
13Elfogadva2/24ms1076 KiB
14Elfogadva2/23ms1080 KiB
15Elfogadva2/2123ms11060 KiB
16Elfogadva2/2123ms11072 KiB
17Elfogadva2/2123ms11176 KiB
18Elfogadva2/2128ms11440 KiB
19Elfogadva2/23ms828 KiB
20Elfogadva2/23ms820 KiB
21Elfogadva2/22ms564 KiB
22Elfogadva2/23ms1076 KiB