248022026-02-15 14:37:44miszorimarciA lehető legkevesebb metróval utazás (40 pont)cpp17Elfogadva 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base40/40
1Elfogadva0/01ms760 KiB
2Elfogadva0/03ms820 KiB
3Elfogadva2/21ms564 KiB
4Elfogadva2/21ms564 KiB
5Elfogadva2/21ms564 KiB
6Elfogadva2/21ms564 KiB
7Elfogadva2/22ms564 KiB
8Elfogadva2/22ms564 KiB
9Elfogadva2/22ms820 KiB
10Elfogadva2/22ms592 KiB
11Elfogadva2/21ms712 KiB
12Elfogadva2/23ms992 KiB
13Elfogadva2/24ms1028 KiB
14Elfogadva2/23ms828 KiB
15Elfogadva2/2280ms6568 KiB
16Elfogadva2/2293ms6452 KiB
17Elfogadva2/2293ms6488 KiB
18Elfogadva2/2279ms6460 KiB
19Elfogadva2/23ms820 KiB
20Elfogadva2/23ms820 KiB
21Elfogadva2/22ms820 KiB
22Elfogadva2/23ms820 KiB