96312024-02-23 15:44:27zeytonxA lehető legkevesebb metróval utazás (40 pont)cpp17Time limit exceeded 2/40600ms63304 KiB
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<ll> vll;
typedef set<ll> sll;
typedef queue<ll> qll;
typedef priority_queue<ll> pqll;
typedef vector<vll> v2ll;
typedef map<ll,ll> mll;
typedef vector<pll> vpll;
typedef map<pll,ll> mpll;
typedef vector<vpll> v2pll;
#define fs first
#define sc second
#define pb push_back

const ll MOD = 1e9+7;

ll ind, erk;
v2pll g;
ll ans = 1e10;
vll vans;
vll used;

void dfs(ll n, vll lines)
{
    if(n == erk-1)
    {
        if(ans > lines.size())
        {
            ans = lines.size();
            vans = lines;
            return;
        }
    }
    used[n] = 1;
    for(pll i : g[n])
        if(!used[i.fs])
        {
            if(lines.empty() || lines[lines.size()-1] != i.sc)
                lines.pb(i.sc);
            dfs(i.fs, lines);
        }
    used[n] = 0;
}

void solve()
{
    ll n, m;
    cin >> n >> m >> ind >> erk;
    g.resize(m);
    used.resize(m, 0);
    for(ll i = 0; i < n; i++)
    {
        ll pc;
        cin >> pc;
        vll line(pc);
        for(ll &j : line)
        {
            cin >> j;
            j--;
        }
        for(ll j = 1; j < pc-1; j++)
        {
            g[line[j-1]].pb({line[j], i});
            g[line[j]].pb({line[j-1], i});
            g[line[j+1]].pb({line[j], i});
            g[line[j]].pb({line[j+1], i});
        }
    }
    dfs(ind-1, vector<ll>());
    cout << ans << "\n";
    for(ll i : vans)
        cout << i+1 << " ";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    ll t = 1;
    //cin >> t;
    while(t--)
        solve();
    cout << endl;
    return 0;
}
SubtaskSumTestVerdictTimeMemory
base2/40
1Accepted0/03ms1700 KiB
2Time limit exceeded0/0600ms5164 KiB
3Wrong answer0/23ms2228 KiB
4Accepted2/23ms2188 KiB
5Time limit exceeded0/2600ms2704 KiB
6Wrong answer0/23ms2400 KiB
7Time limit exceeded0/2600ms2256 KiB
8Time limit exceeded0/2578ms2388 KiB
9Time limit exceeded0/2549ms3660 KiB
10Time limit exceeded0/2565ms3112 KiB
11Time limit exceeded0/2574ms2800 KiB
12Time limit exceeded0/2578ms10824 KiB
13Time limit exceeded0/2535ms11148 KiB
14Time limit exceeded0/2558ms9544 KiB
15Runtime error0/279ms63304 KiB
16Runtime error0/287ms63276 KiB
17Runtime error0/279ms63032 KiB
18Runtime error0/286ms63016 KiB
19Time limit exceeded0/2578ms4756 KiB
20Time limit exceeded0/2524ms5788 KiB
21Time limit exceeded0/2569ms4340 KiB
22Time limit exceeded0/2582ms9884 KiB