85962024-01-22 21:38:35zeytonxA lehető legkevesebb metróval utazás (40 pont)cpp17Time limit exceeded 32/40601ms22072 KiB
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define endl "\n"
#define pll pair<ll,ll>
#define vll vector<ll>
#define mll map<ll,ll>
#define fs first
#define sc second

const ll MOD = 1e9+7;


void solve()
{
	ll n, m, ind, erk;
	cin >> n >> m >> ind >> erk;
    ind--; erk--;
	vector<set<ll>> l(n);
    vector<set<ll>> s(m);
    vector<set<ll>> e(n);
    vector<ll> erk_stat(n);
    for(ll i = 0; i < n; i++)
    {
        ll k;
        cin >> k;
        for(ll j = 0; j < k; j++)
        {
            ll inp;
            cin >> inp;
            inp--;
            if(inp == erk)
                erk_stat[i] = 1;
            l[i].insert(inp);
            for(ll p : s[inp])
            {
                e[i].insert(p);
                e[p].insert(i);
            }
            s[inp].insert(i);
        }
    }
    vector<ll> ans(n), ans_v(n);
    queue<ll> q;
    for(ll i : s[ind])
    {
        q.push(i);
        ans[i] = 1;
        ans_v[i] = -1;
    }
    while(!q.empty())
    {
        ll p = q.front();
        q.pop();
        if(erk_stat[p] != 1)
            for(ll p2 : e[p])
            {
                if(ans[p2] == 0 || ans[p2] > ans[p]+1)
                {
                    ans[p2] = ans[p]+1;
                    ans_v[p2] = p;
                    q.push(p2);
                }
            }
    }
    ll min_v = LLONG_MAX;
    ll min_index = 0;
    for(ll i : s[erk])
    {
        if(ans[i] < min_v && ans[i] != 0)
        {
            min_v = ans[i];
            min_index = i;
        }
    }

    if(min_v == LLONG_MAX)
    {
        cout << -1 << endl;
        return;
    }

    cout << min_v << endl;
    vector<ll> rans;
    while(min_index != -1)
    {
        rans.push_back(min_index);
        min_index = ans_v[min_index];
    }
    for(ll i = rans.size()-1; i >= 0; i--)
    {
        cout << rans[i]+1 << " ";
    }
    cout << endl;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    ll t = 1;
    //cin >> t;
    while(t--)
        solve();
    return 0;
}
SubtaskSumTestVerdictTimeMemory
base32/40
1Accepted0/03ms1832 KiB
2Accepted0/08ms5464 KiB
3Accepted2/23ms2256 KiB
4Accepted2/23ms2464 KiB
5Accepted2/23ms3120 KiB
6Accepted2/22ms2772 KiB
7Accepted2/24ms3696 KiB
8Accepted2/24ms3852 KiB
9Accepted2/26ms4964 KiB
10Accepted2/24ms4892 KiB
11Accepted2/24ms3984 KiB
12Accepted2/28ms6728 KiB
13Accepted2/28ms6680 KiB
14Accepted2/28ms6808 KiB
15Time limit exceeded0/2601ms21988 KiB
16Time limit exceeded0/2572ms21808 KiB
17Time limit exceeded0/2575ms21940 KiB
18Time limit exceeded0/2579ms22072 KiB
19Accepted2/27ms5844 KiB
20Accepted2/28ms6516 KiB
21Accepted2/24ms5048 KiB
22Accepted2/28ms6920 KiB