248022026-02-15 14:37:44miszorimarciA lehető legkevesebb metróval utazás (40 pont)cpp17Accepted 40/40293ms6568 KiB
#include <bits/stdc++.h>

using namespace std;

bool a[201][201];
int d[201];       
int p[201];       
vector<int> v[10001]; 

int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    int N, M, S, E; cin >> N >> M >> S >> E;

    vector<int> sl, el;

    for (int i = 1; i <= N; ++i) {
        int k; cin >> k;
        while (k--) {
            int s; cin >> s;
            if (s == S) sl.push_back(i);
            if (s == E) el.push_back(i);

            for (int x : v[s]) a[i][x] = a[x][i] = 1;
            v[s].push_back(i);
        }
    }

    queue<int> q;
    for (int i = 1; i <= N; ++i) d[i] = -1;

    for (int l : sl) {
        d[l] = 1; p[l] = 0; q.push(l);
    }

    int res = -1;
    while (!q.empty()) {
        int c = q.front(); q.pop();

        bool found = 0;
        for (int t : el) if (c == t) { res = c; found = 1; break; }
        if (found) break;

        for (int n = 1; n <= N; ++n) {
            if (a[c][n] && d[n] == -1) {
                d[n] = d[c] + 1;
                p[n] = c;
                q.push(n);
            }
        }
    }

    if (res == -1) cout << -1 << endl;
    else {
        cout << d[res] << "\n";
        vector<int> path;
        for (int i = res; i != 0; i = p[i]) path.push_back(i);
        for (int i = path.size() - 1; i >= 0; --i)
            cout << path[i] << (i == 0 ? "" : " ");
        cout << endl;
    }

    return 0;
}
SubtaskSumTestVerdictTimeMemory
base40/40
1Accepted0/01ms760 KiB
2Accepted0/03ms820 KiB
3Accepted2/21ms564 KiB
4Accepted2/21ms564 KiB
5Accepted2/21ms564 KiB
6Accepted2/21ms564 KiB
7Accepted2/22ms564 KiB
8Accepted2/22ms564 KiB
9Accepted2/22ms820 KiB
10Accepted2/22ms592 KiB
11Accepted2/21ms712 KiB
12Accepted2/23ms992 KiB
13Accepted2/24ms1028 KiB
14Accepted2/23ms828 KiB
15Accepted2/2280ms6568 KiB
16Accepted2/2293ms6452 KiB
17Accepted2/2293ms6488 KiB
18Accepted2/2279ms6460 KiB
19Accepted2/23ms820 KiB
20Accepted2/23ms820 KiB
21Accepted2/22ms820 KiB
22Accepted2/23ms820 KiB