233992026-01-21 17:54:06BikficcA lehető legkevesebb metróval utazás (40 pont)cpp17Accepted 40/40126ms11240 KiB
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m, k, ind, erk, nr;
    cin >> n >> m >> ind >> erk;
    vector<vector<int>> sz(n+m+1);
    int x;
    for (int i=1; i<=n; i++)
    {
        cin >> nr;
        for (int j=0; j<nr; j++)
        {
            cin >> x;
            sz[x].push_back(m+i);
            sz[m+i].push_back(x);
        }
    }
    vector<int> lat(n+m+1, false);
    queue<int> sor;
    sor.push(ind);
    lat[ind] = true;
    vector <int> ut(n+m+1);
    ut.push_back(ind);
    int csp;
    while (!sor.empty())
    {
        x = sor.front();
        sor.pop();
        for (int csp : sz[x])
        {
            if (!lat[csp])
            {
                lat[csp] = true ;
                sor.push(csp);
                ut[csp] = x;
            }
        }
    }
    if (!lat[erk])
    {
        cout << -1;
        return 0;
    }
    vector<int> e;
    x=erk;
    while (x!=ind)
    {
        if (x > m )
        {
            e.push_back(x - m);
        }
        x = ut[x];
    }
    cout << e.size() << endl;
    reverse(e.begin(), e.end());
    for (int x: e)
    {
        cout << x << " ";
    }
    return 0;
}
SubtaskSumTestVerdictTimeMemory
base40/40
1Accepted0/01ms500 KiB
2Accepted0/04ms1076 KiB
3Accepted2/21ms316 KiB
4Accepted2/21ms316 KiB
5Accepted2/21ms316 KiB
6Accepted2/21ms316 KiB
7Accepted2/21ms564 KiB
8Accepted2/22ms572 KiB
9Accepted2/23ms820 KiB
10Accepted2/22ms564 KiB
11Accepted2/22ms380 KiB
12Accepted2/24ms1076 KiB
13Accepted2/24ms1076 KiB
14Accepted2/24ms960 KiB
15Accepted2/2126ms11100 KiB
16Accepted2/2126ms11184 KiB
17Accepted2/2126ms11240 KiB
18Accepted2/2123ms11176 KiB
19Accepted2/23ms840 KiB
20Accepted2/23ms1076 KiB
21Accepted2/22ms524 KiB
22Accepted2/24ms1076 KiB